期刊名称：CORE Discussion Papers / Center for Operations Research and Econometrics (UCL), Louvain
出版年度：2008
卷号：1
出版社：Center for Operations Research and Econometrics (UCL), Louvain
摘要：Recently, Andersen et al. [1], Borozan and Cornu¨¦jols [6] and Cornu¨¦jols and Margot [9]
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 [23]. 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.
