Summary
In many engineering applications, accurate mathematical modelling requires discrete decisions and non-linear relationships. Optimizing these models is most flexibly done using mixed-integer nonlinear programming (MINLP). Deterministic global optimization of MINLP is valuable for a range of industrial applications including and energy systems and biological and biomedical systems.
But there is an enormous gap between what should be computationally tractable and what MINLP computational tools are currently capable of addressing. Our work synthesises general mathematical advances and individualistic problem-specific knowledge into effective algorithmic protocols and computational tools for solving MINLP. Beyond creating tools, we introduce and develop innovative applications opening new domains for computational optimization.
What is the challenge?
Consider a toy MINLP with one continuous variable (x1 ∈ [0, 1]), one discrete variable (x2 ∈ {0, 1, 2, 3, 4}), a linear objective function (x1 + x2), and two nonlinear constraints:
The solution point is the green star in the upper right-hand corner; this is the point within the feasible space (denoted by dark blue lines) with the greatest value of x1 + x2. But it is possible that a local solution method may initialize at a point such as the red star in the lower left of the figure; a local search staying within the feasible space would not reach the global solution.
This is a toy problem; research has pushed the state-of-the-art to the point where ANTIGONE (Misener and Floudas, 2014) can address several bench-marks up to O(10^4) variables and equations. In practice, solving MINLP is tractable via heterogeneous algorithms pieced together into a framework; we develop and integrate complementary algorithmic components. Here’s a video discussing the research challenges:
What contributions have we made?
Given user-defined MINLP, the ANTIGONE framework we developed reformulates the model, detects special mathematical structure, solves the optimization problem, and returns the model with respect to the original variables (Misener and Floudas, 2014). We have also developed open-source code GALINI that acts as our sandpit for testing new MINLP approaches.
Following are some other items we have investigated; see our publications for more!
- Proposed automatic preprocessing reformulations including disaggregating bilinear terms and flattening the directed acyclic graph of nonlinear functions;
- Explored facet properties of low-dimensional (n ≤ 3) edge-concave aggregations admitting a vertex polyhedral convex hull and extended this analysis to higher dimensions;
- Developed a corollary to Crama’s [Math Program, 61:53–60, 1993] necessary and sufficient condition for the existence of a cut dominating the termwise relaxation of a bilinear expression; the corollary screens whether the minimum necessary difference is zero or not;
- Designed a framework for practically introducing four classes of cuts including: (1) RLT equations; (2) supporting hyperplanes for convex univariate quadratics and convex multivariable terms; (3) aBB cuts; (4) high-dimension edge-concave facets. We try to generate the computationally inexpensive cuts first;
- Investigated relaxations between levels of the traditional Lasserre hierarchy
- Strengthened cuts for MINLP with convex nonlinearities
Where do we go from here?
We have lots of challenging applications which push the limits of available solution strategies; consider working with us! We continue our drive towards developing innovative algorithms and numerical techniques for MINLP.
Collaborators
- Prof Christodoulos A Floudas (PhD advisor)
- Dr Francesco Ceccon, Dr Michael Bynum, Dr Michael Bussieck, Dr Stefan Vigerske (software development)
- Dr Anders Skjäl, Prof Tapio Westerlund (αBB Underestimators)
- Prof Chrysanthos Gounaris (piecewise linear underestimators)
- Dr Georgia Kouyialis (symmetry in mixed-integer optimization)
- Dr Radu Baltean-Lugojan, Dr Pierre Bonami, Dr Andrea Tramontani (cutting planes)
- Dr Juan Campos, Dr Panos Parpas (Lasserre hierarchy)
- Prof Jan Kronqvist (convex nonlinearities)
Software
- ANTIGONE (Solves Mixed-Integer Nonlinear Optimisation Problems)
- GALINI (Open-source software for Mixed-Integer Quadratically-Constrained Quadratic Optimisation Problems)
Video describing the GALINI software:
