(288d) A Hybrid LP/NLP Paradigm for Global Optimization Relaxations

After their introduction in global optimization by Tawarmalani and Sahinidis over a decade ago, polyhedral relaxations have been incorporated in a variety of solvers for the global optimization of nonconvex nonlinear programs and mixed-integer nonlinear programs.  Currently, these relaxations constitute the dominant approach in global optimization practice.  In this paper, we introduce a new relaxation paradigm for global optimization.  The proposed framework combines polyhedral and convex nonlinear relaxations, along with fail-safe techniques, convexity identification at each node of the search tree, and learning heuristics for automatic sub-problem algorithm selection.  We report computational experiments with these relaxations on widely-used test problem collections from the literature, including 369 problems from GlobalLib, 250 problems from MINLPLib and 980 problems from PrincetonLib.  Results show that incorporating the proposed techniques in the BARON software leads to significant improvements in execution time, and increases the number of problems that are solvable to global optimality by 30%.