Tutte seminar - Ricardo Fukasawa

Friday, September 28, 2012 3:30 pm - 4:30 pm EDT (GMT -04:00)

Cutting planes based on multiple rows of a simplex tableau

Speaker: Ricardo Fukasawa
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158


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.