Global Optimization
For the technical report on the current MAiNGO version click here.
The open-source beta version of MAiNGO can be found here.
McCormick-based Algorithm for mixed-integer Nonlinear Global Optimization (MAiNGO) is a deterministic global optimization software for solving mixed-integer nonlinear programs (MINLPs), which has been developed by Dominik Bongartz, Jaromil Najman, Susanne Sass and Alexander Mitsos at the institute for Process Systems Engineering (AVT.SVT). The solver is being actively developed at AVT.SVT.
Any (mixed-integer or continuous) nonlinear program with nonconvex functions can exhibit multiple local solutions. Local optimization methods can converge to any locally optimal solution and can even fail to find any feasible point for a poor choice of initial point. Heuristic methods such as genetic algorithm or simulated annealing converge to the global solution with probability one only as the runtime approaches infinity. In contrast, deterministic global methods do guarantee finite convergence to the global solution given non-zero tolerances for feasibility (\(\delta\)) and optimality (\(\epsilon\)) specified by the user.
MAiNGO can solve MINLPs of the form
\(\begin{align*} \min_{\mathbf{x},\mathbf{y}}\,\,\, &f(\mathbf{x},\mathbf{y}) \newline \text{ s.t. } &h(\mathbf{x},\mathbf{y}) = \mathbf{0} \newline &g(\mathbf{x},\mathbf{y}) \leq \mathbf{0} \newline &\mathbf{x}\in X\in\mathbb{I}\!\mathbb{R}^{n_x} \newline &\mathbf{y}\in Y \subsetneq \mathbb{Z}^{n_y} \end{align*}\)
to global optimality, guaranteeing a solution that is δ-feasible and ϵ-optimal or proving that no δ-feasible point exists, where Iℝ denotes the set of closed bounded intervals of ℝ.
One of the main algorithmic features of MAiNGO is the operation in the original variable space using McCormick relaxations [
McCormick1976
,
Mitsos2009
,
Tsoukalas2014
] (i.e., no auxiliary variables are introduced during the optimization process) through
MC++
. library. Additionally, MAiNGO uses a specialized heuristic for tightening McCormick relaxations [
Najman2019a
], as well as custom relaxations for various functions (including several functions relevant to process systems engineering) [
Najman2016
, Najman2019b]. Furthermore, MAiNGO offers significant flexibility in model formulation and is able to handle functions the algebraic form of which is not visible to the optimizer but whose function values, derivatives, relaxations and its subgradients are available at every point of the domain.
Applications:
MAiNGO has been shown to be advantageous for problems with reduced space formulations [Mitsos2009, Bongartz2017a].
Flowsheet Optimization:
Flowsheet optimization is an application that allows for reduced-space optimization formulations. These can be interpreted as hybrids between equation-based and sequential modular approaches. Compared to purely equation-based approaches that so far have been used for global optimization, this can lead to significant reductions in computational time [Bongartz2017a, Bongartz2017b, Huster2017, Bongartz2018].
Optimization with Machine Learning Models:
Optimization with machine learning models is particularly advantageous, see our dedicated tool Machine Learning models for Optimization (MeLOn).
Global Dynamic Optimization:
MAiNGO has also been applied successfully to global dynamic optimization. In particular for the special case of Hammerstein-Wiener models [Kappatou2022]. The approach followed is discretize then-relax.