Seminar: Jasper van Doornmalen (TU Eindhoven) + Daniel Brosch (Tilburg University), 2 PhD talks

Speaker: Jasper van Doornmalen (TU/e) and Daniel Brosch (Tilburg University)

Title:

Jasper van Doornmalen: Symmetry handling in binary programs through propagation

Daniel Brosch : The Symmetries of Flag-Algebras

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract of "Symmetry handling in binary programs through propagation" (Jasper van Doornmalen):
Symmetries of binary programs are known to dramatically slow down branch-and-bound procedures. A classical approach to handle permutation symmetries is to enforce that only one representative of equivalent (symmetric) solutions can be computed. In classical integer programming literature, among others, this is established by introducing symmetry handling constraints. This way, solutions that are not lexicographically maximal among the permuted solutions are cut off.

We present a propagation-based symmetry handling technique. Given a set of fixed variables (e.g., due to branching decisions), this technique identifies further variables that can be fixed to ensure that only lexicographically maximal solutions are computed. We present efficient algorithms to find such additional symmetry-based variable fixings for arbitrary sets of permutations and cyclic groups. In particular, for cyclic groups, we show that all possible fixings can be found in polynomial time even if the cyclic group has exponential order.

Our methods are implemented as a plugin in the academic integer programming solver SCIP, and we discuss the effectiveness of these methods on various symmetrical instances.

Video of the talk of Jasper van Doornmalen:

Slides of the talk of Jasper van Doornmalen:  
Slides

Abstract of "The Symmetries of Flag-Algebras" (Daniel Brosch):
Flag-Algebras, first introduced by Razborov in 2007, remain one of the most powerful tools in extremal combinatorics.  Recently a connection to polynomial optimization was discovered: We can recover Flag-Sums-of-Squares hierarchies by partially exploiting the symmetries of a polynomial optimization hierarchy. We continue from there and fully exploit the symmetries in this polynomial setting for two different hierarchies, one focusing on a low number of edges, and another focusing on a low number of vertices of appearing Flags. For the first, due to the high initial dimension of the hierarchy, a novel algorithm was needed to decompose modules of the symmetric group into irreducible submodules. We apply the reduced hierarchies to obtain outer approximations of graph-profiles, which model various open problems from extremal combinatorics.

Video of the talk of Daniel Brosch:

Slides of the talk of Daniel Brosch:
Link to Daniel's slides on his webpage