Split closure and intersection cuts

被引:47
作者
Andersen, K [1 ]
Cornuéjols, G
Li, YJ
机构
[1] Carnegie Mellon Univ, Tepper Sch Business, Pittsburgh, PA 15213 USA
[2] Purdue Univ, Grad Sch Management, W Lafayette, IN 47907 USA
基金
美国国家科学基金会;
关键词
D O I
10.1007/s10107-004-0558-z
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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 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.
引用
收藏
页码:457 / 493
页数:37
相关论文
共 10 条
[1]  
ANDERSEN K, 2004, UNPUB REDUCE SPLIT C
[2]   INTERSECTION CUTS - NEW TYPE OF CUTTING PLANES FOR INTEGER PROGRAMMING [J].
BALAS, E .
OPERATIONS RESEARCH, 1971, 19 (01) :19-+
[3]   A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming [J].
Balas, E ;
Perregaard, M .
MATHEMATICAL PROGRAMMING, 2003, 94 (2-3) :221-245
[4]  
Balas Egon., 1979, ANN OFDISCRETE MATH, V5, P3, DOI DOI 10.1016/S0167-5060(08)70342-X
[5]   Mixed-integer programming: A progress report [J].
Bixby, RE ;
Fenelon, M ;
Gu, ZH ;
Rothberg, E ;
Wunderling, R .
THE SHARPEST CUT: THE IMPACT OF MANFRED PADBERG AND HIS WORK, 2004, 4 :309-325
[6]   CHVATAL CLOSURES FOR MIXED INTEGER PROGRAMMING-PROBLEMS [J].
COOK, W ;
KANNAN, R ;
SCHRIJVER, A .
MATHEMATICAL PROGRAMMING, 1990, 47 (02) :155-174
[7]   On the rank of mixed 0,1 polyhedra [J].
Cornuéjols, G ;
Li, YJ .
MATHEMATICAL PROGRAMMING, 2002, 91 (02) :391-397
[8]   Elementary closures for integer programs [J].
Cornuéjols, G ;
Li, YJ .
OPERATIONS RESEARCH LETTERS, 2001, 28 (01) :1-8
[9]  
Gomory R., 1960, Tech. Rep. RM-2597
[10]   A RECURSIVE PROCEDURE TO GENERATE ALL CUTS FOR 0-1 MIXED INTEGER PROGRAMS [J].
NEMHAUSER, GL ;
WOLSEY, LA .
MATHEMATICAL PROGRAMMING, 1990, 46 (03) :379-390