*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
