TITLE: On the strength of relaxations of the boolean quadric polytope

ABSTRACT:

In the 1989 seminal paper, The boolean quadric polytope: Some characteristics, facets and relatives [Mathematical Programming, 45(1-3):139-172, 1989], Padberg introduced five classes of valid inequalities for the boolean quadric polytope: triangle, clique, cut, generalized cut, and odd cycle inequalities. In addition to the McCormick relaxation, these inequalities give a stronger relaxation of the convex hull of the graph of a bilinear function. In this talk, we study classes of bilinear functions where the McCormick relaxation and some of the Padberg inequalities characterize the convex hull. Furthermore, we study which of the Padberg inequalities give the strongest relaxation of the convex hull. We then apply the strong inequalities to (quadratically constrained) quadratic programs from the literature to find good lower bounds fast. Finally, we demonstrate that warm starting a global optimization solver with these lower bounds can improve the solver's performance.

This is joint work with Natashia Boland, Thomas Kalinowski, and Hamish Waterer.