TY - GEN
T1 - Transitive packing
AU - Müller, Rudolf
AU - Schulz, Andreas S.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1996.
PY - 1996
Y1 - 1996
N2 - This paper is intended to give a concise understanding of the facial structure of previously separately investigated polyhedra. We introduce the notion of transitive packing and the transitive packing polytope and give cutting plane proofs for huge classes of valid inequalities of this polytope. We introduce generalized cycle, generalized clique, generalized antihole, generalized antiweb, generalized web, and odd partition inequalities. These classes subsume several known classes of valid inequalities for several of the special cases but also give many new inequalities for several others. For some of the classes we also prove a nontrivial lower bound for their Chvátal rank. Finally, we relate the concept of transitive packing to generalized (set) packing and covering as well as to balanced and ideal matrices.
AB - This paper is intended to give a concise understanding of the facial structure of previously separately investigated polyhedra. We introduce the notion of transitive packing and the transitive packing polytope and give cutting plane proofs for huge classes of valid inequalities of this polytope. We introduce generalized cycle, generalized clique, generalized antihole, generalized antiweb, generalized web, and odd partition inequalities. These classes subsume several known classes of valid inequalities for several of the special cases but also give many new inequalities for several others. For some of the classes we also prove a nontrivial lower bound for their Chvátal rank. Finally, we relate the concept of transitive packing to generalized (set) packing and covering as well as to balanced and ideal matrices.
UR - http://www.scopus.com/inward/record.url?scp=84947920583&partnerID=8YFLogxK
U2 - 10.1007/3-540-61310-2_32
DO - 10.1007/3-540-61310-2_32
M3 - Conference contribution
AN - SCOPUS:84947920583
SN - 3540613102
SN - 9783540613107
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 430
EP - 444
BT - Integer Programming and Combinatorial Optimization - 5th International IPCO Conference, 1996 Proceedings
A2 - Cunningham, William H.
A2 - McCormick, S.Thomas
A2 - Queyranne, Maurice
PB - Springer Verlag
T2 - 5th International Conference Integer Programming and Combinatorial Optimization, IPCO 1996
Y2 - 3 June 1996 through 5 June 1996
ER -