Title:Intersection Cuts in 2 Dimensions
Speaker: Francois Margot, CMU
When: March 27, 12:30-13:30
Where: Porter Hall 125B
Abstract:
When solving Mixed Integer Linear Programs (MILP) with branch-and-cut algorithms a variety of cuts can be generated. The best known cuts are probably Gomory mixed integer cuts, obtained from a single row of the optimal simplex tableau for the linear relaxation of the MILP. Recently, results on generating cuts using information from two rows of the tableau have appeared. In particular, Andersen, Louveaux, Wolsey and Weismantel (2007) investigate the facets of a particular relaxation of the MILP to a problem with two integer variables and two constraints. They show that all facets are then split inequalities or intersection cuts obtained from triangles or quadrilaterals. We give the converse, determining which of these splits, triangles and quadrilaterals actually give facets. We also give the corresponding characterization for an infinite-dimensional relaxation of the relaxation of Andersen et al., similarly to the relaxation used by Gomory and Johnson in their study of the group problem. Joint work with Gerard Cornuejols.
