Addressing Unboundedness in Quadratically-Constrained Mixed-Integer Problems

Abstract

Mixed-integer (MI) quadratic models subject to quadratic constraints, known as All-Quadratic MI Programs, constitute a challenging class of NP-complete optimization problems. The particular scenario of unbounded integers defines a subclass that holds the distinction of being even undecidable [Jeroslow, 1973]. This complexity suggests a possible soft-spot for Mathematical Programming (MP) techniques, which otherwise constitute a good choice to treat MI problems. We consider the task of minimizing MI convex quadratic objective and constraint functions with unbounded decision variables. Given the theoretical weakness of white-box MP solvers to handle such models, we turn to black-box meta-heuristics of the Evolution Strategies (ESs) family, and question their capacity to solve this challenge. Through an empirical assessment of all-quadratic test-cases, across varying Hessian forms and condition numbers, we compare the performance of the CPLEX solver to modern MI ESs, which handle constraints by penalty. Our systematic investigation begins where the CPLEX solver encounters difficulties (timeouts as the search-space dimensionality increases, D>=30), and we report in detail on the D=64 case. Overall, the empirical observations confirm that black-box and white-box solvers can be competitive, where CPLEX is evidently outperformed on 13% of the cases. This trend is flipped when unboundedness is amplified by a significant translation of the optima, leading to a totally inferior performance of CPLEX at 83% of the cases. We also conclude that conditioning and separability are not intuitive factors in determining the hardness degree of this class of MI problems.