Seminar - Carla Michini

Event Details
  • Date/Time:
    • Monday February 22, 2016
      10:00 am
  • Location: Advisory Boardroom Groseclose 402
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact
No contact information submitted.
Summaries

Summary Sentence: Seminar - Carla Michini

Full Summary: No summary paragraph submitted.

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.

 

Additional Information

In Campus Calendar
No
Groups

H. Milton Stewart School of Industrial and Systems Engineering (ISYE)

Invited Audience
Undergraduate students, Faculty/Staff, Graduate students
Categories
Seminar/Lecture/Colloquium
Keywords
No keywords were submitted.
Status
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Feb 19, 2016 - 3:59am
  • Last Updated: Apr 13, 2017 - 5:16pm