EECS Joint Colloquium Distinguished Lecture Series

Wednesday, October 9, 2002
Hewlett Packard Auditorium, 306 Soda Hall
4:00-5:00 p.m.

Professor Dimitris Bertsimas

Visiting Miller Professor, U. C. Berkeley and
Professor of Operations Research at Sloan School of Management, Massachusetts Institute of Technology


Robust Discrete Optimization, Network Flows and Dynamic Optimization




Addressing data uncertainty in mathematical programming models has long been recognized as a central problem in optimization. In this research, we propose an approach to address data uncertainty for discrete optimization, network flow problems and dynamic optimization that (a) allows to control the degree of conservatism of the solution and (b) is computationally tractable both practically and theoretically. In particular, when both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows controlling the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0-1 discrete optimization problem on n variables, then we solve the robust counterpart by solving at most n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0-1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. We also show that the robust counterpart of an NP-hard a-approximable 0-1 discrete optimization problem, remains a-approximable. We also propose an algorithm for robust network flows that solves the robust counterpart by solving a polynomial number of nominal minimum cost flow problems in a modified network. We finally apply robust optimization methods to classical dynamic optimization problems arising in supply chain management that illustrate the power of the method.


Dimitris Bertsimas is currently the Boeing Professor of Operations Research at the Sloan School of Management and the Operations Research Center at the Massachusetts Institute of Technology. For the academic year 2002-2003 he is a Miler Fellow at the University of California, Berkeley. He has received a BS in Electrical Engineering and Computer Science at the National Technical University of Athens, Greece in 1985, a MS in Operations Research at MIT in 1987, and a Ph.D in Applied Mathematics and Operations Research at MIT in 1988. Since 1988, he has been with MIT's Sloan School of Management.

His research interests include discrete, stochastic and dynamic optimization, analysis and control of stochastic systems and applications in revenue management, finance and e-commerce. He has published widely in several journals and he is area editor of Financial Engineering in Operations Research. He has co-authored two books: "Introduction to Linear Optimization" (with J. Tsitsiklis, Athena Scientific, 1997), a doctoral level textbook, and "Data, models and decisions" (with R. Freund, Southewestern, 2000), an MBA textbook. He is currently working on a graduate level textbook, "Optimization over Integers" (with R. Weismantel).

His awards include the Erlang prize (1996), the SIAM prize in optimization (1996), the Bodossaki prize (1998), the Presidential Young Investigator award (1991-1996), the Nicholson prize (1988), and the Transportation System prize (1989).