(529a) Global Optimization of Mathematical Models with Rational Functions Using Quadratization

A variety of problems arising in chemical engineering such as pooling and blending in operations planning can be modelled as mixed-integer polynomial programs (MIPOPs) [1]. Many of these problems are nonconvex and, therefore, hard to solve to global optimality. Current state-of-the-art global optimization solvers such as BARON, ANTIGONE and SCIP can handle such problems as special cases of mixed-integer nonlinear programs (MINLPs). These solvers build mixed-integer linear (MIP) relaxations over given subdomains of the original problem and solve them repeatedly using commercial MIP solvers such as CPLEX and GUROBI as part of a spatial branch-and-bound algorithm.

Our recent work [2] has considered the reformulation of MIPOPs as mixed-integer quadratically constrained quadratic programs (MIQCQPs), then solve the resulting MIQCQPs using GUROBI (version >9). This simple approach was shown to reduce the computational time needed to solve MIPOPs by around 30% in comparison to state-of-the-art global solvers for a large number of instances in MINLPLib [3].

In this presentation, we extend the scope of our MIQCQP reformulation framework to handle rational functions too. This entails an additional step whereby the rational expressions are first converted into a set of polynomial expressions via the introduction of auxiliary variables. These symbolic manipulations are automated alongside the quadratization in the open-source library MC++ [4]. The reformulated (equivalent) MIQCQP is solved to global optimality using GUROBI after applying standard domain-reduction and local optimization heuristics. The effectiveness of this approach is tested on instances from MINLPLib [3], showing a significant reduction in the shifted geometric mean of wall times in comparison to state-of-the-art global solvers.

References:

1. Teles JP, Castro PM, Matos HA (2013) Univariate parameterization for global optimization of mixed-integer polynomial problems. Eur J Oper Res 229(3):613–625
2. Karia T, Adjiman CS, Chachuat B (2021) Global Optimization of Mixed-Integer Polynomial Programs via Quadratic Reformulation. In: 31st European Symposium on Computer Aided Process Engineering - ESCAPE'31
3. Chachuat B, Houska B, Paulen R, Perić N, Rajyaguru J, Villanueva ME (2015) Set-theoretic approaches in analysis, estimation and control of nonlinear systems. IFAC-PapersOnLine 48(8):981–995
4. GAMS Development Corp. MINLPLib: A Library of Mixed-Integer and Continuous Nonlinear Programming Instances. Available from: http://www.minlplib.org/