An efficient symmetry breaking technique for arbitrary groups

Abstract:  Symmetries are commonly found in Integer Linear Programs (ILPs) or in some of their substructures. Having many symmetric solutions could make common algorithms as branch-and-bound inefficient, hence breaking symmetries might yield important gains.

Given a group of symmetries of an ILP, a Fundamental Domain is a set of R^n that aims to select a unique representative of symmetric vectors, i.e. such that each point in the set is a unique representative under its G-orbit, effectively breaking all symmetries of the group. The canonical Fundamental Domain found in the literature, which can be constructed for any permutation group, is NP-hard to separate even for very simple groups, whose elements are disjoint involutions (Babai & Luks 1983).

In this talk I will introduce basic group theoretical tools to show that for every finite permutation group there exists a Fundamental Domain which has quadratic many facets on the dimension, hence the separation problem for this particular Fundamental Domain can be done in polynomial time. Even more, this implies that for a given group there exist different types of Fundamental Domains, some of which can be separated in polytime while others cannot. In particular, intersecting a given polytope with different Fundamental Domains (for a fixed group), might yield polytopes with radically different extension complexity.

This is joint work with José Verschae and Léonard von Niederhäusern.

Posted on Dec 2, 2019 in ACGO, Seminars