Extended Formulations for Packing and Partitioning Orbitopes

Simple item page
dc.creatorFaenza, Yuri
dc.creatorKaibel, Volker
dc.date2008-06-02
dc.date.accessioned2026-07-07T09:44:18Z
dc.date.available2026-07-07T09:44:18Z
dc.descriptionWe give compact extended formulations for the packing and partitioning orbitopes (with respect to the full symmetric group) described and analyzed in (Kaibel and Pfetsch, 2008). 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.
dc.description16 pages
dc.identifierhttps://arxiv.org/abs/0806.0233
dc.identifierhttp://arxiv.org/abs/0806.0233
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/162823
dc.subjectCombinatorics
dc.subjectOptimization and Control
dc.subject90C10; 90C57; 52B12
dc.titleExtended Formulations for Packing and Partitioning Orbitopes
dc.typetext

Files

Collections

arXiv