On the rank of mixed 0,1 polyhedra

被引:27
作者
Cornuéjols, G [1 ]
Li, YJ [1 ]
机构
[1] Carnegie Mellon Univ, Grad Sch Ind Adm, Pittsburgh, PA 15213 USA
关键词
mixed integer cut; disjunctive cut; split cut; rank; mixed; 0; 1; program;
D O I
10.1007/s101070100250
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
For a polytope in the [0, 1](n) cube. Eisenbrand and Schulz showed recently that the maximum Chvatal rank is bounded above by O(n(2)logn) and bounded below by ( 1 + is an element of)n for some is an element of > 0. Chvatal cuts are equivalent to Gomory fractional cuts, which are themselves dominated by Gomory mixed integer Cuts. What do these upper and lower bounds become when the rank is defined relative to Gomory mixed integer cuts? An upper bound of n follows from existing results in the literature. In this note, we show that the lower bound is also equal to n. This result still holds for mixed 0,1 polyhedra with n binary variables.
引用
收藏
页码:391 / 397
页数:7
相关论文
共 16 条
[1]  
[Anonymous], RM2597 RAND
[2]  
Balandin A, 2000, PHYS LOW-DIMENS STR, V1-2, P1
[3]   A LIFT-AND-PROJECT CUTTING PLANE ALGORITHM FOR MIXED 0-1 PROGRAMS [J].
BALAS, E ;
CERIA, S ;
CORNUEJOLS, G .
MATHEMATICAL PROGRAMMING, 1993, 58 (03) :295-324
[4]  
Balas E., 1975, NONLINEAR PROGRAMMIN, V2, P279, DOI DOI 10.1016/B978-0-12-468650-2.50015-8
[5]  
Balas Egon., 1979, ANN OFDISCRETE MATH, V5, P3, DOI DOI 10.1016/S0167-5060(08)70342-X
[6]  
Chvatal V., 1973, Discrete Mathematics, V4, P305, DOI 10.1016/0012-365X(73)90167-2
[7]   ON CUTTING-PLANE PROOFS IN COMBINATORIAL OPTIMIZATION [J].
CHVATAL, V ;
COOK, W ;
HARTMANN, M .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1989, 114 :455-499
[8]   On the matrix-cut rank of polyhedra [J].
Cook, W ;
Dash, S .
MATHEMATICS OF OPERATIONS RESEARCH, 2001, 26 (01) :19-30
[9]   CHVATAL CLOSURES FOR MIXED INTEGER PROGRAMMING-PROBLEMS [J].
COOK, W ;
KANNAN, R ;
SCHRIJVER, A .
MATHEMATICAL PROGRAMMING, 1990, 47 (02) :155-174
[10]  
Cook W., 1998, Combinatorial Optimization