Tutte seminar - Ricardo Fukasawa

Cutting planes based on multiple rows of a simplex tableau

Abstract:

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.