University of Cambridge > > Isaac Newton Institute Seminar Series > Cutting Planes for First-Level RLT Relaxations of Mixed 0-1 Programs

Cutting Planes for First-Level RLT Relaxations of Mixed 0-1 Programs

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Mustapha Amrani.

Polynomial Optimisation

The Reformulation-Linearization Technique (RLT), due to Sherali and Adams, is used to construct hierarchies of linear programming relaxations of various optimisation problems. We present a method for generating cutting planes in the space of the first-level relaxation, based on optimally weakening valid inequalities for the second-level relaxation. These cutting planes can be applied to any pure or mixed 0-1 program with a linear or quadratic objective function, and any mixture of linear, quadratic and convex constraint functions. In fact, our method results in several exponentially-large families of cutting planes. We show that the separation problem associated with each family can be solved efficiently, under mild conditions. We also present some encouraging computational results, obtained by applying the cutting planes to the quadratic knapsack and quadratic assignment problems.

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity