This paper investigates a polyhedral approach to handle symmetries in mixed-binary programs. We study symretopes, i.e., the convex hulls of all binary vectors that are lexicographically maximal in their orbit with respect to the symmetry group. These polytopes turn out to be quite complex. For practical use, we therefore develop an integer programming formulation with ternary coefficients, based on knapsack polytopes arising from a single lexicographic order enforcing inequality. We show that for these polytopes, the optimization as well as the separation problem of minimal cover inequalities can be solved in quadratic time. We demonstrate the usefulness of this approach by computational experiments, showing that it is competitive with state-of-the-art methods and is considerably faster for specific problem classes.
Citation
TU Darmstadt, Department of Mathematics, Research Group Optimization, Dolivostr. 15, 64293 Darmstadt, January 2017