BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Isaac Newton Institute Seminar Series
SUMMARY:Cutting Planes for First-Level RLT Relaxations of
Mixed 0-1 Programs - Kaparis\, K (Lancaster Univer
sity)
DTSTART;TZID=Europe/London:20130718T140000
DTEND;TZID=Europe/London:20130718T143000
UID:TALK46280AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/46280
DESCRIPTION:The Reformulation-Linearization Technique (RLT)\,
due to Sherali and Adams\, is used to construct hi
erarchies of linear programming relaxations of var
ious optimisation problems. We present a method fo
r generating cutting planes in the space of the fi
rst-level relaxation\, based on optimally weakenin
g valid inequalities for the second-level relaxati
on. These cutting planes can be applied to any pur
e or mixed 0-1 program with a linear or quadratic
objective function\, and any mixture of linear\, q
uadratic and convex constraint functions. In fact\
, our method results in several exponentially-larg
e families of cutting planes. We show that the sep
aration problem associated with each family can be
solved efficiently\, under mild conditions. We al
so present some encouraging computational results\
, obtained by applying the cutting planes to the q
uadratic knapsack and quadratic assignment problem
s.\n
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:Mustapha Amrani
END:VEVENT
END:VCALENDAR