Split Closure and Intersection Cuts
Kent Andersen6
, Gérard Cornuéjols6
and Yanjun Li6 
| (6) |
Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA, USA |
Abstract
In the seventies, Balas introduced intersection cuts for a Mixed Integer Linear Program (MILP), and showed that these cuts
can be obtained by a closed form formula from a basis of the standard linear programming relaxation. In the early nineties,
Cook, Kannan and Schrijver introduced the split closure of an MILP, and showed that the split closure is a polyhedron. In
this paper, we show that the split closure can be obtained using only intersection cuts. We give two different proofs of this
result, one geometric and one algebraic. Furthermore, the result is used to provide a new proof of the fact that the split
closure is a polyhedron. Finally, we extend the result to more general two-term disjunctions.
Supported by NSF grant DMI-0098427 and ONR grant N00014-97-1-0196.
References secured to subscribers.