181874
20190316235510.0
doi
10.1287/moor.1090.0392
1526-5471
ARTICLE
Extended Formulations for Packing and Partitioning Orbitopes
2009
2009
Journal Articles
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.
polytope
symmetry
projection
shifted-column inequalities
extended formulation
246581
Faenza, Y.
229283
Kaibel, V.
34
3
686-697
Mathematics of Operations Research
263547
http://infoscience.epfl.ch/record/181874/files/0806.0233v1.pdf
n/a
n/a
252111
DISOPT
U11879
oai:infoscience.tind.io:181874
SB
article
GLOBAL_SET
229283
229283
EPFL-ARTICLE-181874
OTHER
REVIEWED
PUBLISHED
ARTICLE