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

Santiago