Alpine

Alpine.jl is a two-stage approach to strengthen piecewise convex relaxations for mixed-integer nonlinear programs (MINLP) with multi-linear terms. In the first stage, we exploit Constraint Programing techniques to contract the variable bounds. We apply feasibility-based bound contraction methods iteratively until a fixed point with respect to the bounds are achieved. In the second stage, we partition the variables domains using an adaptive multivariate partitioning scheme. Instead of equally partitioning the domains of variables appearing in multi-linear terms (predominantly common in the literature), we construct sparser partitions yet tighter relaxations by iteratively partitioning the variable domains in regions of interest (a parametrized partition around the current solution of lower-bounding MILP). This approach decouples the number of partitions from the size of the variable domains, leads to a significant reduction in computation time, and limits the number of binary variables that are introduced by the partitioning. We further apply polyhedral cutting plane methods to handle convex relaxations of higher-order monomial terms.

To use Alpine, external sub-solvers must be installed. See Choosing Sub-Solvers for more information.