Chvátal closures for mixed integer programming problems (Q922950): Difference between revisions

Cutting-plane techniques play an important role in the field of integer programming. Early work on this subject dates back to the sixties when Gomory proposed his well-known cutting-plane algorithm. This algorithm however turned out to be not very successful from a practical point of view, which led to a decline of interest in the subject. Recent work by a number of authors has renewed the interest and over the last decade an increasing number of fundamental contributions have been made. One such contribution is the basic principle formulated by Chvátal that for a polyhedron P and an integral vector w, if max\(\{\) wx\(|\) \(x\in P\), wx \(integer\}=t\), then wx\(\leq t\) holds for all integral vectors \(x\in P\). In the present paper the authors consider a generalization of this principle where the requirement that wx be integer is replaced by the requirement that cx be integer for some other integral vector c. The authors show that the cutting-plane proofs thus obtained can be viewed as an abstraction of Gomory's mixed-integer cutting-plane technique or as a proof version of a simple class of disjunctive cutting planes studied by Balas and Jeroslow. The authors study the extent to which this generalization preserves the features of Chvátal's cutting plane proofs, when applied to mixed-integer programming. The main result is that for a given polyhedron P, the set of vectors that satisfy every cutting plane for P with respect to a given subset of integer variables is again a polyhedron, which makes it possible to recursively generate in a finite number of steps the mixed-integer hull of a polyhedron, analogous to the integer programming case. The obtained results are discussed for a number of combinatorial optimization problems including integer programs with circular ones, fixed-charge problems, and plant location and lot-sizing problems.