Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Extended Formulations for Packing and Partitioning Orbitopes
 
research article

Extended Formulations for Packing and Partitioning Orbitopes

Faenza, Y.  
•
Kaibel, V.
2009
Mathematics of Operations Research

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.

  • Files
  • Details
  • Metrics
Type
research article
DOI
10.1287/moor.1090.0392
Author(s)
Faenza, Y.  
Kaibel, V.
Date Issued

2009

Published in
Mathematics of Operations Research
Volume

34

Issue

3

Start page

686

End page

697

Subjects

polytope

•

symmetry

•

projection

•

shifted-column inequalities

•

extended formulation

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
DISOPT  
Available on Infoscience
October 25, 2012
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/86263
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés