Faenza, Yuri; Kaibel, Volker Extended formulations for packing and partitioning orbitopes. (English) Zbl 1218.90124 Math. Oper. Res. 34, No. 3, 686-697 (2009). Summary: We give compact extended formulations for the packing and partitioning orbitopes (with respect to the full symmetric group) described and analyzed by V. Kaibel and M. Pfetsch [Math. Program. 114, No. 1 (A), 1–36 (2008; Zbl 1171.90004)]. 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. Cited in 17 Documents MSC: 90C10 Integer programming 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut 52B15 Symmetry properties of polytopes 52B12 Special polytopes (linear programming, centrally symmetric, etc.) Keywords:polytope; symmetry; projection; shifted-column inequalities Citations:Zbl 1171.90004 PDFBibTeX XMLCite \textit{Y. Faenza} and \textit{V. Kaibel}, Math. Oper. Res. 34, No. 3, 686--697 (2009; Zbl 1218.90124) Full Text: DOI arXiv