*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
TITLE: Split Rank of Triangle and Quadrilateral Inequalities
SPEAKER: Dr. Santanu Dey
ABSTRACT:
A simple relaxation of two rows of a simplex tableau is a mixed integer set consisting of two equations with two free integer variables and non-negative continuous variables. Recently Andersen et al. (2007) and Cornuejols and Margot (2008) showed that the facet-defining inequalities of this set are either split cuts or intersection cuts obtained from maximal lattice-free triangles and quadrilaterals. These new families of inequalities can be used to generate valid cutting planes from any two rows of a simplex tableau. Through a result by Cook et al. (1990) (and more recently in a generalization by Li and Richard (2008)) it is known that one particular class of facet-defining triangle inequality does not have a finite split rank, i.e., it cannot be obtained by repeated application of split cuts. In this talk, we show that all other facet-defining triangle and quadrilateral inequalities have a finite split-rank. The proof is constructive, i.e., for a given facet-defining triangle or quadrilateral inequality we present an explicit sequence of split inequalities that can be used to generate it.
