Project Details

Background

Mixed-Integer Nonlinear Programming (MINLP) is a hot research topic powered by applications from various areas, including energy generation and distribution, logistics, engineering design, manufacturing, and the chemical and biological sciences.

A general MINLP can be formulated as

min {f(x) : g(x) ≤ 0, x ∈ [x_l, x_u], x_i ∈ Z, i ∈ I },

where f : R^n → R and g : R^n → R^m are twice continuously differentiable functions, x_l, x_u ∈ R^n determine lower and upper bounds on the variables, resp., and I ⊆ {1, ..., n} denotes the set of variables with integrality requirements.

Most state-of-the-art algorithms for finding globally optimal solutions of general MINLPs are based on branch-and-bound.
For MINLPs where the functions f (x) and g(x) are convex, several software packages are available, e.g., SBB, AlphaECP, Bonmin, DICOPT, and FilMINT. Except for SBB and Bonmins B-BB algorithm, these solvers extend an LP-based branch-and-cut solver for mixed-integer linear programming (MILP) by linearizing nonlinear functions whenever appropriate. Thus, their performance highly depends on the underlying MILP solver.
For nonconvex MINLPs, there are numerous application specific approaches. Only few codes exist, however, that can handle nonconvex MINLPs in general. The state-of-the-art commercial MINLP solver BARON implements a spatial branch-and-bound algorithm that is based on a factorable reformulation of the given problem and convexifications of univariate functions. For the open-source code Bonmin, a similar method is in development in the Couenne project. Also the solver LaGO implements a convexification based branch-and-cut algorithm. Here, nonconvex quadratic terms are convexified by applying the alpha-underestimating technique from, while nonconvex nonquadratic functions are first underestimated by a quadratic function, which is then convexified.
A different methodology called branch-and-infer is pursued in the COCONUT project. Here, the idea is to embed interval arithmetic and constraint propagation techniques that reduce bounds on variables and expressions in a spatial branch-and- bound algorithm. Currently, COCONUT is able to handle only continuous global optimization problems, i.e., I is empty.
There also have been efforts to handle nonlinear aspects by combinatorial and integer linear programming techniques. For instance, piecewise linear approximations of nonlinearities proved to be successful in the optimization of gas and water networks and sheet metal production.
As has been demonstrated by the afore mentioned solvers for convex MINLPs and having recent advantages in mixed-integer linear programming in mind, a favorable way to solve nonconvex MINLPs is the extension of a MILP solver by techniques to handle nonlinear functions (e.g., by convexification and linearization).

Project Goals

The goal of this project is to bring together the expertise of the branch-cut-and-price framework SCIP and the MINLP solver LaGO for the development of a general purpose LP based branch-and-cut solver for nonconvex MINLPs. Thus, we plan to develop and implement cut generation techniques (e.g., linearizations of convexifications) to cut off infeasible points from an LP relaxation, heuristics (e.g., local search in a nonlinear program (NLP)) to find feasible solution candidates, branching- and node selection rules, and domain propagation methods.

In the beginning, we will approach the solution of the broad class of mixed-integer all-quadratic problems (MIQQP), i.e., MINLPs where f(x) and g(x) are quadratic functions. Such constraints appear, for instance, whenever different materials are mixed in technical or chemical processes. Further on, methods for the treatment of other common nonlinear functions and their composition should be developed. An important aspect which had a remarkable impact on MILP solvers but has not found much attention in existing MINLP codes so far is preprocessing. This includes reformulations and model reductions that can be deduced from the problem formulation and that are favorable for the applied algorithm. Therefore, also an adequate in-memory representation of the MINLP demands for special attention. To allow an easy applicability of the developed techniques, interfaces to the modeling systems ZIMPL and GAMS will be developed.

Applications of the developed software are, among others, in fare planning, mine production planing, and the optimization of the design and operation of complex energy conversion systems. Further, the optimization of MINLPs under uncertainties constitutes a challenging application for the developed software. While the deterministic equivalents of stochastic MINLPs are large-scale, their structure offers an interesting starting point for decomposition algorithms.