A Hybrid LP/NLP Paradigm for Global Optimization Relaxations

After their introduction in global optimization by Tawarmalani and Sahinidis [43,44], 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 strategies for automatically selecting and switching between different relaxations and between di.erent local search algorithms in different parts of the search tree. We report computational experiments with the proposed methodology on widely-used test problem collections from the literature, including 369 problems from GlobalLib, 250 problems from MINLPLib, and 980 problems from Princeton-Lib. Results show that incorporating the proposed techniques in the BARON software leads to significant reductions in execution time, and increases by 30% the number of problems that are solvable to global optimality within 500 s on a standard workstation.