TITLE:  Polyhedral methods for combinatorial problems: from 0-1 quadratic programming to Nash equilibria

ABSTRACT:

Polyhedra are central objects in linear programming, combinatorial optimization and integer programming. I will show recent results based on polyhedral methods that range from binary quadratic programming to algorithmic game theory. The goal is to relate the computational complexity of different problems to the structure of the underlying polyhedra, and to unveil new classes of polynomially solvable instances.   

In unconstrained binary programming, the use of polyhedral methods dates back to Padberg, who introduced the boolean quadric polytope. A well-known relaxation of the boolean quadric polytope is the cycle relaxation, on which one can optimize in polynomial time. I will present a characterization of the sign patterns of the objective function that always yield an integral optimal solution over the cycle relaxation.

 Next, I will explore Nash equilibrium problems. For congestion games, I will describe a polyhedral reformulation of this equilibrium problem and show that total unimodularity is a key property to find a Nash equilibrium in polynomial time.

 I will also discuss results that address more fundamental questions in linear programming. In particular, I will show a new bound on the diameter of lattice polytopes. This bound is tight if the vertices have components in {0,1,2}.

Bio

Carla Michini received a PhD in Optimization in 2012 from University of Rome La Sapienza. In 2011, she was a visiting scholar at CMU Pittsburgh, and from 2012 to 2014 she was a postdoctoral researcher at the Institute for Operations Research at ETH Zürich. Currently, she is a postdoctoral researcher in the Optimization group at the Wisconsin Institute for Discovery of UW-Madison.

Carla’s research focuses on different topics in combinatorial optimization, polyhedral combinatorics and integer programming, and spans both theoretical and algorithmic issues. She is particularly concerned with the study of structural properties of combinatorial problems and with their computational complexity.