Alpine
A Julia/JuMP-based Global Optimization Solver for Non-convex Programs
Science Score: 54.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
✓CITATION.cff file
Found CITATION.cff file -
✓codemeta.json file
Found codemeta.json file -
○.zenodo.json file
-
✓DOI references
Found 4 DOI reference(s) in README -
○Academic publication links
-
✓Committers with academic emails
13 of 40 committers (32.5%) from academic institutions -
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (11.8%) to scientific vocabulary
Keywords
Keywords from Contributors
Repository
A Julia/JuMP-based Global Optimization Solver for Non-convex Programs
Basic Info
- Host: GitHub
- Owner: lanl-ansi
- License: other
- Language: Julia
- Default Branch: master
- Homepage: https://lanl-ansi.github.io/Alpine.jl/latest/
- Size: 5.48 MB
Statistics
- Stars: 248
- Watchers: 22
- Forks: 42
- Open Issues: 10
- Releases: 35
Topics
Metadata Files
README.md
Alpine, a global solver for non-convex MINLPs
ALPINE (glob(AL) o(P)timization for mixed-(I)nteger programs with (N)onlinear (E)quations), is a novel global optimization solver that uses an adaptive, piecewise convexification scheme and constraint programming methods to solve non-convex Mixed-Integer Non-Linear Programs (MINLPs) efficiently. MINLPs are typically "hard" optimization problems which appear in numerous applications (see MINLPLib.jl).
Alpine is entirely built upon JuMP and MathOptInterface in Julia, which provides incredible flexibility for usage and further development.
Alpine globally solves a given MINLP by:
Analyzing the problem's expressions (objective & constraints) and applies appropriate convex relaxations and polyhedral outer-approximations
Performing sequential optimization-based bound tightening (OBBT) and an iterative MIP-based adaptive partitioning scheme via piecewise polyhedral relaxations with a guarantee of global convergence
Upon Alpine's convergence, for a given relative gap tolerance ε, the user is guaranteed that the global optimal solution is in the ε-neighborhood of the solution found by the solver.
Installation
Install Alpine using the Julia package manager:
julia
import Pkg
Pkg.add("Alpine")
Usage with JuMP
Use Alpine with JuMP as follows:
julia
using JuMP, Alpine, Ipopt, HiGHS
ipopt = optimizer_with_attributes(Ipopt.Optimizer, "print_level" => 0)
highs = optimizer_with_attributes(HiGHS.Optimizer, "output_flag" => false)
model = Model(
optimizer_with_attributes(
Alpine.Optimizer,
"nlp_solver" => ipopt,
"mip_solver" => highs,
),
)
Documentation
For more details, see the online documentation.
Support problem types
Alpine can currently handle MINLPs with polynomials in constraints and/or in the objective. Currently, there is no support for exponential cones and Positive Semi-Definite (PSD) cones in MINLPs. Alpine is also a good fit for subsets of the MINLP family, for example, Mixed-Integer Quadratically Constrained Quadratic Programs (MIQCQPs), Non-Linear Programs (NLPs), etc.
For more details, check out this video on Alpine.jl at JuMP-dev 2018.
Underlying solvers
Though an MIP-based bounding algorithm implemented in Alpine is quite involved, most of the computational bottleneck arises in the underlying MIP solvers. Since every iteration of Alpine solves an MIP sub-problem, which is typically a convex MILP/MIQCQP, Alpine's run time heavily depends on the run-time of these solvers. For the best performance of Alpine, we recommend using the commercial solver Gurobi, which is available free for academic purposes. However, due to the flexibility offered by JuMP, the following MIP and NLP solvers are supported in Alpine:
| Solver | Julia Package | |--------------------------------------------------------------------------------|--------------------------------------------------------------| | Gurobi | Gurobi.jl | | CPLEX | CPLEX.jl | | HiGHS | HiGHS.jl | Cbc | Cbc.jl | | Ipopt | Ipopt.jl | | Bonmin | Bonmin.jl | | Artelys KNITRO | KNITRO.jl | | Xpress | Xpress.jl
Bug reports and support
Please report any issues via the GitHub issue tracker. All types of issues are welcome and encouraged; this includes bug reports, documentation typos, feature requests, etc.
Challenging Problems
We are seeking out hard benchmark instances for MINLPs. Please get in touch either by opening an issue or privately if you would like to share any hard instances.
Citing Alpine
If you find Alpine useful in your work, we kindly request that you cite the following papers (PDF, PDF) ```bibtex @article{alpine_JOGO2019, title = {An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs}, author = {Nagarajan, Harsha and Lu, Mowen and Wang, Site and Bent, Russell and Sundar, Kaarthik}, journal = {Journal of Global Optimization}, year = {2019}, issn = {1573-2916}, doi = {10.1007/s10898-018-00734-1}, }
@inproceedings{alpineCP2016, title = {Tightening {McCormick} relaxations for nonlinear programs via dynamic multivariate partitioning}, author = {Nagarajan, Harsha and Lu, Mowen and Yamangil, Emre and Bent, Russell}, booktitle = {International Conference on Principles and Practice of Constraint Programming}, pages = {369--387}, year = {2016}, organization = {Springer}, doi = {10.1007/978-3-319-44953-124}, } ```
If you find the underlying piecewise polyhedral formulations implemented in Alpine useful in your work, we kindly request that you cite the following papers (link-1, link-2): ```bibtex @article{alpine_ORL2021, title = {Piecewise polyhedral formulations for a multilinear term}, author = {Sundar, Kaarthik and Nagarajan, Harsha and Linderoth, Jeff and Wang, Site and Bent, Russell}, journal = {Operations Research Letters}, volume = {49}, number = {1}, pages = {144--149}, year = {2021}, publisher = {Elsevier} }
@article{alpine_OptOnline2022, title={Piecewise Polyhedral Relaxations of Multilinear Optimization}, author={Kim, Jongeun and Richard, Jean-Philippe P. and Tawarmalani, Mohit}, eprinttype={Optimization Online}, date={2022} } ```
Owner
- Name: advanced network science initiative
- Login: lanl-ansi
- Kind: organization
- Email: ansi-info@lanl.gov
- Location: Los Alamos, NM
- Website: https://lanl-ansi.github.io/
- Repositories: 79
- Profile: https://github.com/lanl-ansi
Los Alamos Advanced Network Science Initiative
Citation (CITATION.bib)
@article{alpine_JOGO2019,
author = {Nagarajan, Harsha and Lu, Mowen and Wang, Site and Bent, Russell and Sundar, Kaarthik},
title = {An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs},
journal = {Journal of Global Optimization},
year = {2019},
issn = {1573-2916},
doi = {10.1007/s10898-018-00734-1},
}
GitHub Events
Total
- Create event: 4
- Commit comment event: 2
- Release event: 1
- Watch event: 5
- Delete event: 3
- Issue comment event: 3
- Push event: 11
- Pull request event: 6
- Fork event: 2
Last Year
- Create event: 4
- Commit comment event: 2
- Release event: 1
- Watch event: 5
- Delete event: 3
- Issue comment event: 3
- Push event: 11
- Pull request event: 6
- Fork event: 2
Committers
Last synced: 7 months ago
Top Committers
| Name | Commits | |
|---|---|---|
| harshangrjn | h****n@g****m | 191 |
| jac0320 | s****w@g****u | 160 |
| Site Wang | s****w@c****u | 128 |
| Kaarthik Sundar | k****r@g****m | 52 |
| Benoît Legat | b****t@g****m | 36 |
| jac0320 | b****0@g****m | 29 |
| Oscar Dowson | o****w | 23 |
| Wang Site | W****e | 22 |
| Site Wang | s****w@S****l | 15 |
| tweisser | t****r@w****e | 12 |
| Carleton Coffrin | c****c@l****v | 11 |
| Kaarthik Sundar | k****r@p****v | 8 |
| sitew | s****w@s****n | 8 |
| Lars Hellemo | h****o@g****m | 6 |
| Harsha Nagarajan | h****a@H****l | 5 |
| Felipe Markson dos Santos Monteiro | 4****n | 5 |
| Harsha Nagarajan | h****a@p****v | 4 |
| jac0320 | s****w@d****v | 3 |
| sitew | s****w@l****v | 3 |
| Site Wang | s****w@s****n | 3 |
| sitewang | s****g@s****n | 2 |
| Site Wang | s****w@l****u | 2 |
| harsha | h****a@l****v | 2 |
| harsha | h****a@p****v | 2 |
| fatihcengil | f****l@h****m | 2 |
| Russell Bent | r****t@l****v | 2 |
| Jongeun Kim | 3****m | 2 |
| Roman Lebedev | l****i@g****m | 2 |
| Charlie van Rantwijk | c****k@g****m | 1 |
| Site Wang | s****g@s****n | 1 |
| and 10 more... | ||
Committer Domains (Top 20 + Academic)
Issues and Pull Requests
Last synced: 4 months ago
All Time
- Total issues: 67
- Total pull requests: 61
- Average time to close issues: 5 months
- Average time to close pull requests: about 1 month
- Total issue authors: 28
- Total pull request authors: 13
- Average comments per issue: 3.43
- Average comments per pull request: 1.82
- Merged pull requests: 46
- Bot issues: 0
- Bot pull requests: 7
Past Year
- Issues: 0
- Pull requests: 12
- Average time to close issues: N/A
- Average time to close pull requests: 10 days
- Issue authors: 0
- Pull request authors: 2
- Average comments per issue: 0
- Average comments per pull request: 0.92
- Merged pull requests: 11
- Bot issues: 0
- Bot pull requests: 0
Top Authors
Issue Authors
- harshangrjn (18)
- freemin7 (6)
- odow (5)
- blegat (5)
- krishpat (3)
- Vaibhavdixit02 (3)
- Shuvomoy (3)
- manojcen (2)
- kaarthiksundar (2)
- felipemarkson (2)
- OliverEvans96 (1)
- asavasci (1)
- JuliaTagBot (1)
- julbinb (1)
- ericphanson (1)
Pull Request Authors
- odow (33)
- harshangrjn (14)
- github-actions[bot] (8)
- blegat (7)
- hellemo (3)
- LebedevRI (2)
- fatihcengil (1)
- felipemarkson (1)
- tweisser (1)
- ccoffrin (1)
- jongeunkim (1)
- tkoolen (1)
- JuliaTagBot (1)
Top Labels
Issue Labels
Pull Request Labels
Packages
- Total packages: 1
-
Total downloads:
- julia 40 total
- Total dependent packages: 3
- Total dependent repositories: 0
- Total versions: 33
juliahub.com: Alpine
A Julia/JuMP-based Global Optimization Solver for Non-convex Programs
- Homepage: https://lanl-ansi.github.io/Alpine.jl/latest/
- Documentation: https://docs.juliahub.com/General/Alpine/stable/
- License: BSD-3-Clause
-
Latest release: 0.5.7
published 9 months ago