Uncategorized

Operations Research Seminar

Friday, March 12, 2021 – 1:30pm to 3:00pm

Location:

Virtual Presentation – ET Remote Access – Zoom

Speaker:

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).

About the Speaker

REGISTER

Event Website:

https://econ.tepper.cmu.edu/Seminars/seminar.asp?dbaction=y&sort=1&short=Y&Restr…

For More Information, Contact:

Keywords:

Seminar Series

Similar Posts