BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Cutting Planes for First-Level RLT Relaxations of Mixed 0-1 Progra
 ms - Kaparis\, K (Lancaster University)
DTSTART:20130718T130000Z
DTEND:20130718T133000Z
UID:TALK46280@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:The Reformulation-Linearization Technique (RLT)\, due to Shera
 li and Adams\, is used to construct hierarchies of linear programming rela
 xations of various optimisation problems. We present a method for generati
 ng cutting planes in the space of the first-level relaxation\, based on op
 timally weakening valid inequalities for the second-level relaxation. Thes
 e cutting planes can be applied to any pure or mixed 0-1 program with a li
 near or quadratic objective function\, and any mixture of linear\, quadrat
 ic and convex constraint functions. In fact\, our method results in severa
 l exponentially-large families of cutting planes. We show that the separat
 ion 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 quad
 ratic assignment problems.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR