Spring 2010 UMASS Amherst
Operations Research / Management Science Seminar Series
Joint Seminar with Finance

Date: Friday, April 23, 2010
Time: 11:00 AM
Location: Isenberg School of Management, Room 112

Speaker: Professor Dimitris Bertsimas

Boeing Professor of Operations Research
Sloan School of Management
Massachusetts Institute of Technology
Cambridge, MA

Biography: Dr. Dimitris Bertsimas is the Boeing Professor of Operations Research and the codirector of the Operations Research Center at the Massachusetts Institute of Technology. He received a BS in Electrical Engineering and Computer Science from the National Technical University of Athens, Greece in 1985, an MS in Operations Research from MIT in 1987, and a Ph.D in Applied Mathematics and Operations Research from MIT in 1988. Since 1988, he has been in the MIT faculty.

His research interests include optimization, stochastic systems, data mining, and their application. In recent years he has worked in robust optimization, health care and finance. He has co-authored more than 110 scientific papers and he has co-authored the following books: Introduction to Linear Optimization (with J. Tsitsiklis, Athena Scientific and Dynamic Ideas, 2008), Data, models and decisions (with R. Freund, Dynamic Ideas, 2004) and Optimization over Integers (with R. Weismantel, Dynamic Ideas, 2005). He is currently department editor in Optimization for Management Science and former area editor in Operations Research in Financial Engineering. He has supervised 42 doctoral students and he is currently supervising 10 others.

He is a member of the National Academy of Engineering. He has received numerous research awards including the Farkas prize (2008), the Erlang prize (1996), the SIAM prize in optimization (1996), the Bodossaki prize (1998) and the Presidential Young Investigator award (1991-1996).

Title: Advances in Multistage Optimization
Abstract: This talk explores several recent advances in multistage stochastic and adaptive optimization. We consider a multi-stage mixed integer stochastic optimization problems and show that a static finitely adaptable solution (it reduces to a robust solution in two stages) that can be computed in polynomial time is a good approximation to the fully-adaptable mutli-stage solution for the stochastic problem under fairly general assumptions on the uncertainty set and the probability distribution. In particular, we show that if the right hand side of the constraints is uncertain and belongs to a symmetric uncertainty set (such as hypercube, ellipsoid or norm-ball) and the probability measure is also symmetric, then the cost of the optimal fixed solution to the corresponding robust problem is at most twice the optimal expected cost of the multistage-stage stochastic problem. Furthermore, we show that the bound is tight for symmetric uncertainty sets and can be arbitrarily large if the uncertainty set is not symmetric. We refer to the ratio of the optimal cost of the robust problem and the optimal cost of the two-stage stochastic problem as the stochasticity gap. We also extend the bound on the stochasticity gap for another class of uncertainty sets referred to as positive. If both the objective coefficients and right hand side are uncertain, we show that the stochasticity gap can be arbitrarily large even if the uncertainty set and the probability measure are both symmetric. However, we prove that the adaptability gap (ratio of optimal cost of the robust problem and the optimal cost of a multi-stage fully-adaptable problem) is at most four even if both the objective coefficients and the right hand side of the constraints are uncertain and belong to a symmetric uncertainty set. The bound holds for the class of positive uncertainty sets as well. Moreover, if the uncertainty set is a hypercube (special case of a symmetric set), the adaptability gap is one under an even more general model of uncertainty where the constraint coefficients are also uncertain. A class of affine policies has been extensively studied in the literature for multistage optimization. We show that affine policies are with O(m^(1/2)) from optimal in multistage problems and the bound is tight, thus giving a tight characterization of this class of tractably computed policies.
(joint work with Vineet Goyal, MIT)
This series is organized by the UMASS Amherst INFORMS Student Chapter. Support for this series is provided by the Isenberg School of Management, the Department of Finance and Operations Management, INFORMS, and the John F. Smith Memorial Fund.

Dr. Anna Nagurney, the John F. Smith Memorial Professor of Operations Management in the Isenberg School of Management,  is the Faculty Advisor of the Speaker Series.