 |
Center for Nonlinear Studies |
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.
Host: Hristo Djidjev, CCS-3, 667-7589