TITLE: Discrete optimization problems: from combinatorial properties to geometric approaches

ABSTRACT:

Discrete optimization problems naturally appear in science, engineering, and many other areas of technological everyday life. Numerous effective methods for tackling these problems build on the existence of strong convex relaxations, mainly obtained using linear (LP) and semidefinite programming (SDP). Producing these relaxations is by no means trivial, and it is the subject of much classical and recent research.

In this talk, I will show some combinatorial techniques for producing exact LP formulations, and apply them to important problems from the literature. I will also briefly talk about geometric techniques to strengthen non-exact formulations and challenging open problems in the area.

Bio: Yuri Faenza received a M.Sc. in Mathematical Engineering in 2006 from the University "Tor Vergata" of Rome, and a Ph.D. in Operations Research in 2010 from the University "Sapienza" of Rome. He has then been a post-doc in the Mathematics Departments of the University of Padua, EPFL, and University of Brussels.
In 2014 he was awarded an Ambizione fellowship from the Swiss National Science Foundation for his project Tight formulations of 0-1 optimization problems. He decided to pursue his project at EPFL, which he then re-joined in 2015.
His main research interests lie in polyhedral combinatorics, combinatorial optimization, and integer programming.