(206d) Deciding Which Equality Constraints to Eliminate in Mixed-Integer Nonlinear Programs for Deterministic Global Optimization

Mixed-Integer Nonlinear programs (MINLPs) are ubiquitous in Chemical Engineering and are challenging to solve to global optimality. Recent developments in deterministic global optimization (DGO) of MINLPs include the development of the open-source solvers MAiNGO (1) and EAGO (2), which employ McCormick relaxations (3-5) to solve lower bounding problems. McCormick relaxations can be beneficial for problems with fewer variables but potentially more complex nonlinear expressions (5) relative to relaxations generated using auxiliary variable method (AVM) (6). As a result, reduced space formulations (4) were proposed, in which equality constraints are eliminated, thereby resulting in a problem with lower dimensionality. In the extreme case all equality constraints are eliminated, or all that can be eliminated. However, we have already demonstrated that the extreme case is not necessarily advisable and a careful selection of equality constraints to eliminate is required (7). Solving reduced-space formulations with solvers based on McCormick relaxations often requires significantly lower computational effort than full-space problems, e.g., for problems in flowsheet optimization (7) and optimization of hybrid/data-driven models (8). In contrast, state-of-the-art DGO solvers such as BARON (9,10), ANTIGONE (11) and SCIP (12) rely on AVM (6) to construct convex relaxations. Eliminating equality constraints leads to more complex nonlinear expressions, which for AVM-based solvers leads to introduction of a different set of auxiliary variables compared to the full-space formulation. In contrast to McCormick relaxation-based solvers, for AVM-based solvers it is unclear if eliminating equality constraints is useful. In this work, we investigate whether eliminating equality constraints is beneficial for AVM-based solvers. We present an assessment of the factors that affect the choice of equality constraints to be eliminated and the impact of this choice on the computational performance of AVM-based DGO solvers. Numerical experiments are conducted on selected problems from MINLPLib (13), and on case studies from Chemical Engineering. These are used to suggest heuristics to guide the selection of equality constraints to be eliminated based on the reduction in the computational effort needed to solve the selected MINLPs to global optimality. These heuristics could potentially be integrated into existing portfolio of pre-processing strategies employed by the DGO solvers to solve MINLPs more effectively.

References:

(1) Bongartz D, Najman J, Sass S, Mitsos A. MAiNGO: McCormick based Algorithm for mixed integer Nonlinear Global Optimization. Process Systems Engineering (AVT. SVT), RWTH Aachen University 2018:1-7; Available at: http://permalink.avt.rwth-aachen.de/?id=729717.

(2) Wilhelm ME, Stuber MD. EAGO. jl: easy advanced global optimization in Julia. Optimization Methods and Software 2022;37(2):425-450.

(3) McCormick GP. Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems. Mathematical Programming 1976 Dec;10(1):147-175.

(4) Mitsos A, Chachuat B, Barton PI. McCormick-Based Relaxations of Algorithms. SIAM Journal on Optimization 2009 Jan 1,;20(2):573-601.

(5) Tsoukalas A, Mitsos A. Multivariate McCormick relaxations. Journal of Global Optimization 2014 Jul 1,;59(2-3):633-662.

(6) Smith EMB, Pantelides CC. A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Computers & Chemical Engineering 1999 May 1,;23(4):457-478.

(7) Bongartz D, Mitsos A. Deterministic global optimization of process flowsheets in a reduced space using McCormick relaxations. Journal of Global Optimization 2017 Dec 1,;69(4):761-796.

(8) Schweidtmann AM, Mitsos A. Deterministic Global Optimization with Artificial Neural Networks Embedded. Journal of Optimization Theory and Applications 2019 Mar 1,;180(3):925-948.

(9) Tawarmalani M, Sahinidis NV. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming 2005 Jun 1,;103(2):225-249.

(10) Kılınç MR, Sahinidis NV. Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON. Optimization Methods & Software 2018 May 4,;33(3):540-562.

(11) Misener R, Floudas CA. ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations. Journal of Global Optimization 2014 Jul 1,;59(2-3):503-526.

(12) Bestuzheva K, Chmiela A, Müller B, Serrano F, Vigerske S, Wegscheider F. Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8. 2023 Jan 2; Available at: https://arxiv.org/abs/2301.00587.

(13) Vigerske S. MINLPLib: A Library of Mixed-Integer and Continuous Nonlinear Programming Instances. 2018; Available at: https://minlplib.org/index.html.