Polytopes associated with symmetry handling

Christopher Hojny (Corresponding author), Marc E. Pfetsch

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)

Abstract

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 almost linear 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.
Original languageEnglish
Pages (from-to)197-240
Number of pages44
JournalMathematical Programming
Volume175
Issue number1-2
DOIs
Publication statusPublished - 1 May 2019
Externally publishedYes

    Fingerprint

Cite this