TITLE:  Symmetry Handling for Integer Programs

ABSTRACT:

The presence of symmetries in integer programs is well known to hurt the performance of branch-and-cut methods and several symmetry handling methods have been proposed. This talk will give an overview on these methods and investigate their computational impact. Most of these techniques perform pruning in the tree or fixing variables. As an alternative, a general polyhedral approach will be presented that is based on the convex hull of lexicographically maximal points within their orbit, so-called symretopes. While a complete description of these polytopes is only known for special symmetry groups, one can use their structure to construct efficiently solvable integer programming formulations. Computational results will show that this approach is competitive with the state-of-the-art methods based on pruning the tree.