Title:

Extended formulations for combinatorial optimization problems

Abstract:

Mixed-integer linear programming is one of the most popular and effective tools to solve optimization problems. Representing our problem of interest via a linear formulation is a key step crucially affecting the performance of the solver. When the original formulation is too large to be processed, one can resort to an extended formulation: while extra variables are added, the number of constraints can be dramatically reduced, allowing for a compact representation.

In this talk I will introduce my research on extended formulations and give some examples of how to construct such formulations for some classical combinatorial optimization problems, using tools from communication complexity, matroid theory and combinatorics. I will then highlight how these theoretical constructions can be effectively used in computational applications.

Bio:

Manuel Aprile has studied mathematics and computer science in Catania (Italy) and Oxford (UK). He obtained his PhD in Discrete Optimization at EPFL (Switzerland) in 2018, under the supervision of Friedrich Eisenbrand and Yuri Faenza. He has been a post-doc in Bruxelles, and he is currently a post-doc at Padua University, Italy.