DOS Seminar - Fabian Rigterink

Event Details
  • Date/Time:
    • Tuesday October 25, 2016 - Wednesday October 26, 2016
      11:00 am - 11:59 am
  • Location: Groseclose 402
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: DOS Seminar - Fabian Rigterink

Full Summary: No summary paragraph submitted.

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


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.

Additional Information

In Campus Calendar

School of Industrial and Systems Engineering (ISYE)

Invited Audience
Faculty/Staff, Public, Undergraduate students, Graduate students
No keywords were submitted.
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Oct 21, 2016 - 11:36am
  • Last Updated: Apr 13, 2017 - 5:14pm