×

Extended formulations for packing and partitioning orbitopes. (English) Zbl 1218.90124

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.

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.)

Citations:

Zbl 1171.90004
PDFBibTeX XMLCite
Full Text: DOI arXiv