Dutch Seminar on Optimization (online series) with Jasper van Doornmalen (TU/e) and Daniel Brosch (Tilburg University)

The Dutch Seminar on Optimization is an initiative to bring together researchers from the Netherlands and beyond, with topics that are centered around Optimization in a broad sense. We would like to invite all researchers, especially also PhD students, who are working on related topics to join the events. We hereby announce the following two talks, given by PhD-students:

Speaker: Jasper van Doornmalen (TU/e)
Title: Symmetry handling in binary programs through propagation
Date: Tuesday 24th May, 4:00pm CET

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

Speaker: Daniel Brosch (Tilburg University)
Title: The Symmetries of Flag-Algebras
Date: Tuesday 24th May, 4:30pm CET

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