[Seminario] RECORDATORIO INVITACIÓN SEMINARIO AGCO, MIÉRCOLES 04 DE DICIEMBRE A LAS 14:30 HRS.

[Maria Ines Rivera]

*Estimados Académicos (as) y Alumnos(as)
*

*Se les recuerda que hoy miércoles 04 de diciembre a las 14:30 hrs. se 
realizará el Seminario  AGCO, en Av República 701, Sala 22.
*

*Seminar AGCO *

*Author: *Matías Villagra, PUC

*Where:*Av República 701,*Sala 22*.

*When:*Wednesday, December 4, *14:30*.

*Title:* An efficient symmetry breaking technique for arbitrary groups

*Abstract: *Symmetries are commonly found in Integer Linear Programs 
(ILPs) or in some of their substructures. Having many symmetric 
solutions could make common algorithms as branch-and-bound inefficient, 
hence breaking symmetries might yield important gains.

Given a group of symmetries of an ILP, a Fundamental Domain is a set of 
R^n that aims to select a unique representative of symmetric vectors, 
i.e. such that each point in the set is a unique representative under 
its G-orbit, effectively breaking all symmetries of the group. The 
canonical Fundamental Domain found in the literature, which can be 
constructed for any permutation group, is NP-hard to separate even for 
very simple groups, whose elements are disjoint involutions (Babai & 
Luks 1983).

In this talk I will introduce basic group theoretical tools to show that 
for every finite permutation group there exists a Fundamental Domain 
which has quadratic many facets on the dimension, hence the separation 
problem for this particular Fundamental Domain can be done in polynomial 
time. Even more, this implies that for a given group there exist 
different types of Fundamental Domains, some of which can be separated 
in polytime while others cannot. In particular, intersecting a given 
polytope with different Fundamental Domains (for a fixed group), might 
yield polytopes with radically different extension complexity.

This is joint work with José Verschae and Léonard von Niederhäusern.

Esperando contar con su presencia, les saluda,

Ma. Inés Rivera

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listas.dim.uchile.cl/pipermail/seminario/attachments/20191204/bd46624a/attachment.html>