Symmetry breaking inequalities: Geometry and Perspectives

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

game theorymachine learningmathematical softwarecomputer science theorycombinatoricsoptimization and control

Audience: researchers in the topic

---

Mixed Integer Programming Workshop 2021

Series comments: The 18th Mixed Integer Programming Workshop will be held online on May 24-27, 2021.

It will feature 21 distinguished invited speakers covering most aspects of Mathematical Optimization, an interactive, gamified MIP student poster session with 50 posters, and a casual business meeting.

Registration is free of charge. Register here: fico.zoom.us/webinar/register/2416186463858/WN_DVLhGOToQkKyvKYPiA4cQw

Find the website of MIP2021 at sites.google.com/view/mipworkshop2021/.

---