Talks

Abstract: Breaking symmetries is a popular way of speeding up the branch-and-bound method for symmetric integer programs. We study symmetry-breaking polyhedra, more precisely, fundamental domains.

In this talk, I will introduce the necessary mathematical concepts to understand the implications of symmetries in polyhedral objects.

In particular, we will derive several general geometric properties of fundamental domains and how these geometric considerations can affect the power for breaking symmetries. I will also mention some recent results for constructing more general fundamental domains ("On the Geometry of Symmetry Breaking Inequalities" IPCO 2021). Finally, I will focus on several open questions regarding fundamental domains, their geometric properties, and how they could help us better understand the capabilities and limitations of symmetry-breaking systems.

This is joint with Matías Villagra (U Columbia) and Leonard von Niederhäusern (UOH & CMM).