TY - EJOUR
DO - 10.1287/moor.1090.0392
AB - We give compact extended formulations for the packing and partitioning orbitopes (with respect to the full symmetric group) described and analyzed in Kaibel and Pfetsch [Kaibel, V., M. E. Pfetsch. 2008. Packing and partitioning orbitopes. Math. Programming, Ser. A 114(1) 1–36]. These polytopes are the convex hulls of all 0/1-matrices with lexicographically sorted columns and at most, respectively, exactly one 1-entry per row. They are important objects for symmetry reduction in certain integer programs. Using the extended formulations, we also derive a rather simple proof of the fact established in the paper mentioned above, that basically shifted-column inequalities suffice to describe those orbitopes linearly.
T1 - Extended Formulations for Packing and Partitioning Orbitopes
IS - 3
DA - 2009
AU - Faenza, Y.
AU - Kaibel, V.
JF - Mathematics of Operations Research
SP - 686-697
VL - 34
EP - 686-697
ID - 181874
KW - polytope
KW - symmetry
KW - projection
KW - shifted-column inequalities
KW - extended formulation
SN - 1526-5471
UR - http://infoscience.epfl.ch/record/181874/files/0806.0233v1.pdf
ER -