Friday, September 28, 2012
3:30 pm, MC 5158

Ricardo Fukasawa
University of Waterloo

Cutting planes based on multiple rows of a simplex tableau

Cutting planes are one of the most essential components in modern mixed-integer programming solvers. One particular class of cutting planes that is well known and very important is the class of Gomory mixed-integer cuts (GMI), which are derived considering a single row of the simplex tableau.
Andersen et al. (2007) proposed a way to extend these GMI cuts by considering multiple rows of the simplex tableau. This opened up a series of results on the study of such cuts. By now a lot is known about them and several extensions have been proposed.
In this talk I will introduce the main ideas behind these multi-row cuts and survey some of the recent results on the subject. No prior knowledge will be assumed.