Optimization Online


Extended Formulations for Packing and Partitioning Orbitopes

Yuri Faenza(yuri.faenza***at***gmail.com)
Volker Kaibel Kaibel(kaibel***at***ovgu.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society