Workshop on Extended Formulations and Symmetries in Integer Programming
General Information
Dates: December 9-11, 2019
Location: Institute of Engineering Sciences, Universidad de O'Higgins (Rancagua).
Organizers: Gonzalo Muñoz (UOH), Victor Verdugo (UOH-LSE) and Jose Verschae (UOH).
About the Workshop
The goal of this workshop is to create a discussion platform for researchers interested in the Integer Programming subfields of Extended Formulations and Symmetries, two highly important topics of theoretical and practical relevance. The use of variables that can represent intricate elements beyond the original variables, i.e. extended formulations, can provide tractable alternatives to seemingly complex optimization models. However, certain problems where no efficient formulation exists, and others where systematic extended-formulation-finding procedures fail, have one thing in common: symmetries -- both a theoretical and practical seemingly undesirable feature in IP. This reveals a close relationship between these concepts which in this workshop we will explore. Our aim is to better understand their interplay and to address relevant questions regarding the role of both these features in obtaining good formulations.
Location
Rancagua (December 9-11): Universidad de O'Higgins, Campus Rancagua.
Confirmed Participants
Manuel Aprile (ULB, Belgium)
Max Deppert (Kiel U, Germany)
Samuel Fiorini (ULB, Belgium)
Christopher Hojny (Eindhoven UT, Netherlands)
Klaus Jansen (Kiel U, Germany)
Alexandra Lassota (Kiel U, Germany)
Gonzalo Muñoz (UOH, Chile)
Leonard von Niederhausern (UOH and CMM, Chile)
Kanstantsin Pashkovich (U Ottawa, Canada)
Felipe Serrano (ZIB, Germany)
Matias Villagra (PUC, Chile)
Victor Verdugo (UOH and LSE, Chile-UK)
José Verschae (UOH, Chile)
Andreas Wiese (U Chile, Chile)
José Soto (U Chile, Chile)
Claudio Telha (U Andes, Chile)
Program
Day 1
9:30 - 10:15: TBA (Felipe Serrano)
10:15 - 10:45: Coffee Break
10:15 - 11:00: Regular matroids have polynomial extension complexity (Manuel Aprile)
11:30 - 12:15: TBA (Gonzalo Muñoz)
12:15 - 13:45: Lunch
13:45 - 15:15: Crash course on Symmetry Handling (Victor Verdugo & José Verschae) Basic Notions: Groups
16:00 - 16:30: Coffee Break
15:15 - 16:00: Symretopes and Symresacks: A Framework for Deriving Generic and Problem Specific Symmetry Handling Inequalities (Christopher Hojny)
16:30 - 17:30: Open Problem Session
17:30 - 19:00: Open Discussion
19:30: Dinner
Day 2
9:30 - 11:00: Crash course on Extension Complexity (Samuel Fiorini)
11:00 - 11:30: Coffee Break
11:30 - 12:15: An efficient symmetry breaking technique for arbitrary groups (Matias Villagra)
12:00 - 13:45: Lunch
13:45 - 14:15: Open Problem Session
14:15 - 15:00: TBA (Gustavo Angulo)
15:00 - 15:45: On Integer Programming, Discrepancy, and Convolution (Klaus Jansen)
15:45 - 16:15: Coffee Break
16:15 - 18:30: Open Discussion
Day 3
9:30 - 10:15: Symmetries in Extended Formulations (Kanstantsin Pashkovich)
10:15 - 10:45: Coffee Break
10:45 - 11:30: Near-Linear Time Algorithm for n-Fold ILPs via Color Coding (Alexandra Lassota)
11:30 - 12:15: Open Discussion
12:15 - 13:45: Lunch
13:45 - 14:30: Fuzzy Chinese Remaindering (Max Deppert)
14:30 - 16:00: Open Discussion
16:00 - 16:30: Coffee Break
16:30 - 18:00: Closing session with progress reports by the groups on achieved results, outline of plans on how to continue the initiated work, closing remarks.
Hotel information
Here we leave a sample of a few hotels.
Rancagua
Hotel Doria, 1km from Campus
Hotel Diego de Almagro, 950m from Campus