Classical cuts for mixed-integer programming and branch-and-cut

被引:7
作者
Padberg, M
机构
[1] 13007 Marseille, 17, Rue Vendôme
关键词
mixed-integer programming; cutting planes; Gomory cuts; branch-and-cut;
D O I
10.1007/s001860100120
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
We review classical valid linear inequalities for mixed-integer programming, i.e., Gomory's fractional and mixed-integer cuts, and discuss their use in branch-and-cut. In particular, a generalization of the recent mixed-integer rounding (MIR) inequality and a sufficient condition for the global validity of classical cuts after branching has occurred are derived.
引用
收藏
页码:173 / 203
页数:31
相关论文
共 91 条
[1]  
[Anonymous], LINEAR INTEGER PROGR
[2]  
Applegate D.L., 1998, INT C MATH, VICM III, P645
[3]   AN ADDITIVE ALGORITHM FOR SOLVING LINEAR PROGRAMS WITH 0-1 VARIABLES [J].
BALAS, E .
OPERATIONS RESEARCH, 1965, 13 (04) :517-&
[4]   INTERSECTION CUTS - NEW TYPE OF CUTTING PLANES FOR INTEGER PROGRAMMING [J].
BALAS, E .
OPERATIONS RESEARCH, 1971, 19 (01) :19-+
[5]   FACETS OF KNAPSACK POLYTOPE [J].
BALAS, E .
MATHEMATICAL PROGRAMMING, 1975, 8 (02) :146-164
[6]   Gomory cuts revisited [J].
Balas, E ;
Ceria, S ;
Cornuejols, G ;
Natraj, N .
OPERATIONS RESEARCH LETTERS, 1996, 19 (01) :1-9
[7]  
Balinski M.L., 1969, PROGR OPERATIONS RES, V3, P195
[8]   STRONG FORMULATIONS FOR MULTI-ITEM CAPACITATED LOT SIZING [J].
BARANY, I ;
VANROY, TJ ;
WOLSEY, LA .
MANAGEMENT SCIENCE, 1984, 30 (10) :1255-1261
[9]  
Beale M., 1965, OPERATIONAL RES Q, V16, P219
[10]  
BEALE M, 1958, 9 PRINC U STAT RES G