Two row mixed integer cuts via lifting
Recently, Andersen et al. , Borozan and Cornuéjols  and Cornuéjols and Margot  characterized extreme inequalities of a system of two rows with two free integer variables and nonnegative continuous variables. These inequalities are either split cuts or intersection cuts derived using maximal lattice-free convex sets. In order to use these inequalities to obtain cuts from two rows of a general simplex tableau, one approach is to extend the system to include all possible nonnegative integer variables (giving the two-row mixed integer infinite-group problem), and to develop lifting functions giving the coefficients of the integer variables in the corresponding inequalities. In this paper, we study the characteristics of these lifting functions. We begin by observing that functions giving valid coefficients for the nonnegative integer variables can be constructed by lifting a subset of the integer variables and then applying the fill-in procedure presented in Johnson . We present conditions for these 'general fill-in functions" to be extreme for the two-row mixed integer infinite-group problem. We then show that there exists a unique 'trivial' lifting function that yields extreme inequalities when starting from a maximal lattice-free triangle with multiple integer points in the relative interior of one of its sides, or a maximal lattice-free triangle with integral vertices and one integer point in the relative interior of each side. In all other cases (maximal lattice-free triangle with one integer point in the relative interior of each side and non-integral vertices, and maximal lattice-free quadrilaterals), non-unique lifting functions may yield distinct extreme inequalities. For the case of a triangle with one integer point in the relative interior of each side and non-integral vertices, we present sufficient conditions to yield an extreme inequality for the two-row mixed integer infinite-group problem.
|Date of creation:||01 May 2008|
|Date of revision:|
|Contact details of provider:|| Postal: Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium)|
Fax: +32 10474304
Web page: http://www.uclouvain.be/core
More information through EDIRC
When requesting a correction, please mention this item's handle: RePEc:cor:louvco:2008030. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Alain GILLIS)
If references are entirely missing, you can add them using this form.