Title: Risk-averse Combinatorial Optimization
Speaker: Evdokia Nikolova
Venue: IEMS Seminar
Date: Tuesday Feb.22, 2011
Time: 4-5 pm

Abstract:
Optimization has played a key role in making the task of decision
making from art to science in the past century. An important challenge
that still remains is our ability to incorporate the uncertainty in
our knowledge and risk-aversion in our objective. A simple but
insightful example of this is encapsulated in the decision question:
given a number of route choices, which shall I choose?
Interestingly, this simple question (easily solvable in a
deterministic setting) becomes highly non-trivial when we incorporate
the uncertainty of delays and the individual’s risk-aversion. This
primarily stems from the combinatorial nature of the problem coupled
with the non-convexity of the objective.

In this talk I explain how to solve this reliable route planning
problem, and mention how its solution has been adapted in the MIT
CarTel system for routing, which incorporates real traffic information
(cartel.csail.mit.edu). I then show how the solution extends to a
general framework of risk-averse combinatorial optimization, for which
I present exact and approximation algorithms. These general-purpose
algorithms can also cope with combinatorial problems that are NP-hard,
whose deterministic versions we only know how to approximate. At the
end, I touch upon how the risk-averse framework provides a foundation
for studying equilibria in stochastic network games.