Several IP formulations present an highly symmetric structure, since the action of some groups on their variables do not change the value of the objective function. This is expecially true for some formulations arising from combinatorial optimization problems (e.g. coloring and covering problems). Such a symmetrical structure often harms our ability to solve them: while trying to compute the optimum via Divide and Conquer-like methods, one typically bumps into huge branching trees and useless LP bounds. One of the techniques used to deal with these problems is the insertion in the IP formulation of some constraints that cut off all equivalent solutions but (at least) one. In this context, Kaibel and Pfetsch recently introduced Orbitopes as the convex hulls of those 0-1 matrices that have exactly (resp. at most/least) one non-zero entry per row, and that are lexicographically maximal with respect to the action of some group on the columns of the matrix. After having reviewed main results on orbitopes, in this talk we will focus on recent results on the so-called Packing and Partitioning Orbitopes with respect to the full symmetric group: these are the convex hulls of 0-1 matrices with at most (resp. exactly) one non-zero element in each row, and whose columns are in lexicographically non-increasing order. In particular, we will show LP compact formulations in higher dimensional spaces, which lead to simple combinatorial algorithms and short proofs of the complete description (of exponential size) in the original space.

This is joint work with Volker Kaibel.