The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



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

Kaparis, K (Lancaster University)
Thursday 18 July 2013, 14:00-14:30

Seminar Room 1, Newton Institute


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.


[pdf ]


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.

Back to top ∧