Optimization Online


Polytopes Associated with Symmetry Handling

Christopher Hojny (hojny***at***mathematik.tu-darmstadt.de)
Marc E. Pfetsch (pfetsch***at***mathematik.tu-darmstadt.de)

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 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.

Keywords: symmetry, permutation, knapsack polytope, branch-and-cut

Category 1: Integer Programming (0-1 Programming )

Citation: TU Darmstadt, Department of Mathematics, Research Group Optimization, Dolivostr. 15, 64293 Darmstadt, January 2017

Download: [PDF]

Entry Submitted: 01/26/2017
Entry Accepted: 01/26/2017
Entry Last Modified: 01/19/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society