  We introduce orbitopes as the convex hulls of 0/1-matrices that are
lexicographically maximal subject to a group acting on the columns. Special
cases are packing and partitioning orbitopes, which arise from restrictions to
matrices with at most or exactly one 1-entry in each row, respectively. The
goal of investigating these polytopes is to gain insight into ways of breaking
certain symmetries in integer programs by adding constraints, e.g., for a
well-known formulation of the graph coloring problem.
  We provide a thorough polyhedral investigation of packing and partitioning
orbitopes for the cases in which the group acting on the columns is the cyclic
group or the symmetric group. Our main results are complete linear inequality
descriptions of these polytopes by facet-defining inequalities. For the cyclic
group case, the descriptions turn out to be totally unimodular, while for the
symmetric group case both the description and the proof are more involved.
Nevertheless, the associated separation problem can be solved in linear time
also in this case.
