Friday, March 12, 2021 – 1:30pm to 3:00pm
Virtual Presentation – ET Remote Access – Zoom
JOSÉ VERSCHAE, Associate Professor https://sites.google.com/site/jverschae/home
On the geometry of symmetry breaking inequalities
Breaking symmetries is a popular way of speeding up the branch-and-bound method for symmetric integer programs. We propose a theoretical study of symmetry-breaking polyhedra, more precisely, fundamental domains. Our long-term goal is to understand the relationship between the complexity of such polyhedra and their symmetry-breaking ability.
In this talk, we will start by introducing the necessary mathematical concepts related to symmetries in polyhedral objects. In particular, we will derive properties of fundamental domains that relate the underlying group with the geometric structure of the fundamental domain. Inspired by these insights, we provide a new generalized construction for fundamental domains, which we call generalized Dirichlet domain (GDD). In particular, our construction yields that every permutation group admits a fundamental domain with linearly many facets, while the separation problem for general fundamental domains is NP-hard.
This is joint with Matías Villagra (Columbia U) and Leonard von Niederhäusern (UOH & CMM).