skip to content

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

Presented by: 
K Kaparis Lancaster University
Thursday 18th July 2013 - 14:00 to 14:30
INI Seminar Room 1
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.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons