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:

import Pkg
Pkg.add("Alpine")

Usage with JuMP

Use Alpine with JuMP as follows:

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:

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)

@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{alpine_CP2016,
  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-1_24},
}

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):

@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}
}