Abstract |
: |
Recently, Andersen et al. [1] and Borozan and Cornu´ejols [3]
characterized the minimal inequalities of a system of two rows with two
free integer variables and nonnegative continuous variables. These in-
equalities are either split cuts or intersection cuts derived using maximal
lattice-free convex sets. In order to use these minimal inequalities to ob-
tain cuts from two rows of a general simplex tableau, it is necessary to ex-
tend the system to include integer variables (giving the two-dimensional
mixed integer inﬁnite group problem), and to develop lifting functions
giving the coeﬃcients of the integer variables in the corresponding in-
equalities. In this paper, we analyze the lifting of minimal inequalities
derived from lattice-free triangles.
Maximal lattice-free triangles in R2 can be classiﬁed into three cate-
gories: those with multiple integral points in the relative interior of one
of its sides, those with integral vertices and one integral point in the
relative interior of each side, and those with non integral vertices and
one integral point in the relative interior of each side. We prove that the
lifting functions are unique for each of the ﬁrst two categories such that
the resultant inequality is minimal for the mixed integer inﬁnite group
problem, and characterize them. We show that the lifting function is not
necessarily unique in the third category. For this category we show that a
ﬁll-in inequality (Johnson [11]) yields minimal inequalities for mixed in-
teger inﬁnite group problem under certain suﬃciency conditions. Finally,
we present conditions for the ﬁll-in inequality to be extreme. |