Pedro Castro gave a Special Seminar entitled "Global Optimization of Quadratically Constrained Problems (QCPS) with Mixed-Integer Programming Relaxations" at Texas A&M Energy Institute.
The invited seminar took place April, 18, 2023.
Several problems of interest to Process Systems Engineering can be formulated as non-convex quadratically constrained programs (QCPs). These appear in design and operational problems and feature constraints with bilinear terms resulting from the product of two continuous variables, e.g., flows and concentrations. The preferred method used by commercial solvers to solve QCPs to global optimality is through the spatial B&B method with linear programming (LP) relaxations. An alternative is to rely on mixed-integer programming (MIP) relaxations, which make the relaxation harder to solve but that can lead to a search process that is more efficient overall. This is especially true for MIP relaxations using logarithmic partitioning schemes relying on a base-2 numeric representation system. After giving an overview of the key procedures that can be used for global optimization, we propose a new algorithm relying extensively on MIP relaxations, for improving the dual bound and for reducing the variables domain through optimality based bound tightening (OBBT). Using a set of 54 benchmark instances from the literature, we show that the new algorithm significantly outperforms GUROBI and BARON.