Extended Formulations for Packing and Partitioning Orbitopes

Details Extended Formulations for Packing and Partitioning Orbitopes Extended Formulations for Packing and Partitioning Orbitopes

2008-06-02

arxiv.org/abs/0806.0233v1

Mathematics

Combinatorics

16 pages

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Extended Formulations for Packing and Partitioning Orbitopes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Extended Formulations for Packing and Partitioning Orbitopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extended Formulations for Packing and Partitioning Orbitopes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-631377