*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Extended formulations for combinatorial optimization problems
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.
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.
