Extended Formulations for Packing and Partitioning Orbitopes

Yuri Faenza(yuri.faenzagmail.com)
Volker Kaibel Kaibel(kaibelovgu.de)

Abstract: 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 (Math. Program. 114 (1), 2008, 1-36). These polytopes are the convex hulls of all 0/1-matrices with lexicographically sorted columns and at most, resp. 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 that basically shifted-column inequalities suffice in order to describe those orbitopes linearly.

Keywords: integer programming, symmetry breaking, lexicographic representative

Category 1: Integer Programming (0-1 Programming )

Category 2: Combinatorial Optimization (Polyhedra )

Citation: Preprint 08-10, FMA, OvGU Magdeburg, June 2008

Download: [PDF]

Entry Submitted: 07/08/2008
Entry Accepted: 07/08/2008
Entry Last Modified: 07/08/2008

Modify/Update this entry