Split closure and intersection cuts. (English) Zbl 1066.90070
Summary: In the seventies, E. Balas [Oper. Res. 19, 19–39 (1971; Zbl 0219.90035)] 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, W. Cook, R, Kannan and A. Schrijver [Math. Program. 47, 155–174 (1990; Zbl 0711.90057)] introduced the split closure of a 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. The result is then used to provide a new proof of the fact that the split closure of a MILP is a polyhedron. Finally, we extend the result to more general disjunctions.
References:
| [1] | Andersen, K., Cornuéjols, G., Li, Y.: Reduce-and-split cuts: Improving the performance of mixed integer Gomory cuts. Submitted for publication, 2004 · Zbl 1232.90310 |
| [2] | Balas, E.: Intersection cuts - a new type of cutting planes for integer programming. Oper. Res. 19, 19-39 (1971) · Zbl 0219.90035 · doi:10.1287/opre.19.1.19 |
| [3] | Balas, E.: Disjunctive programming. Ann. Discrete Math. 5, 3-51 (1979) · Zbl 0409.90061 · doi:10.1016/S0167-5060(08)70342-X |
| [4] | Balas, E., Perregaard, M.: A Precise correspondence between, lift-and-project cuts, simple disjunctive cuts and mixed integer Gomory cuts for 0-1 programming. Mathematical Programming B 94, 221-245 (2003) · Zbl 1030.90068 · doi:10.1007/s10107-002-0317-y |
| [5] | Bixby, R.E., Gu, Z., Rothberg, E., Wunderling, R.: Mixed integer programming: a progress report. In: M. Grötschel (ed)., The sharpest cut: the impact of Manfred Padberg and his work, MPS/SIAM Series on Optimization 2004, pp. 309-326 · Zbl 1152.90542 |
| [6] | Cook, W., Kannan, R., Schrijver, A.: Chvátal closures for mixed integer programs. Mathematical Programming 47, 155-174 (1990) · Zbl 0711.90057 · doi:10.1007/BF01580858 |
| [7] | Cornuéjols, G., Li, Y.: Elementary closures for integer programs. Oper. Res. Lett. 28, 1-8 (2001) · Zbl 1108.90326 · doi:10.1016/S0167-6377(00)00067-5 |
| [8] | Cornuéjols, G., Li, Y.: On the rank of mixed 0, 1 polyhedra. Mathematical Programming 91, 391-397 (2002) · Zbl 1049.90040 · doi:10.1007/s101070100250 |
| [9] | Gomory, R.: An algorithm for the mixed integer problem. Techinical Report RM?2597, The Rand Coporation, 1960 · Zbl 0095.14502 |
| [10] | Nemhauser, G., Wolsey, L.: A recursive procedure to generate all cuts for 0-1 mixed integer programs. Mathematical Programming 46, 379-390 (1990) · Zbl 0735.90049 · doi:10.1007/BF01585752 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
