José Verschae (PUC) Título: A Characterization of Symmetry Breaking Inequalities based on Vector Orderings
Abstract: When solving integer linear programs (ILPs), it is common to face problems subject to symmetries. Usual IP techniques struggle with highly symmetric instances if they are not addressed appropriately. Breaking symmetries is arguably the simplest way of speeding up such methods for symmetric ILPs. However, there might be several non-equivalent ways of breaking symmetries, so it is relevant to understand the geometric differences between constructions.
In this talk I will show how the theory of vector orderings relates to symmetry breaking and how this connection conceptually simplifies the construction of symmetry-breaking inequalities found in the literature. We will be able to characterize all constructions of minimal symmetry breaking sets (i.e. fundamental domains) that arise from vector orderings by showing that, in essence, all such sets arise from choosing lexicographically minimal representative of symmetric points (after a corresponding change of basis). We will finish with several conjectures and open questions.