IMA Journal of Management Mathematics Advance Access published online on March 6, 2007
IMA Journal of Management Mathematics, doi:10.1093/imaman/dpm011
| ||||||||||||||||||||||||||||||||||||||||||||||||
Robust stochastic programming with uncertain probabilities
P.C. Rossin Assistant Professor, Department of Industrial and Systems Engineering, Lehigh University, Mohler Building Room 329, Bethlehem, PA 18015, USA
Email: aurelie.thiele{at}lehigh.edu.
Accepted on 2 February 2007.
 |
Abstract |
|---|
Stochastic programming has traditionally assumed the exact knowledge of the underlying scenario probabilities. In practice, however, such probabilities are difficult to estimate accurately and the optimal decision variables may be quite sensitive to the assumed distributions. This motivates the use of minimax stochastic models, where the decision maker minimizes the maximum expected cost over the set of possible probability distributions. We use ideas from the field of robust optimization to reformulate the minimax stochastic programming problem when probabilities belong to a polyhedral uncertainty set as a single convex problem, and show that it can be solved efficiently using the traditional techniques developed to address sequential decision making under uncertainty. In the two-stage setting, we describe how the Benders decomposition algorithm can be modified to solve the robust formulation. In the case of multiple stages, we build upon the recursive equations of dynamic programming to formulate an approach as tractable as the multi-stage stochastic problem where the probabilities are known exactly. Key contributions of this work are the following: (i) we show that the minimax approach is equivalent to the nominal stochastic programming problem with a penalty term, which measures the cost volatility due to the ambiguity on the probability estimates, and (ii) we provide deeper insights into the connection between the value of the recourse function in a given scenario and the worst-case probability associated with that outcome. The robust approach also allows the decision maker to adjust the parameters defining the uncertainty set in order to better capture his own trade-off between ambiguity and performance.
Keywords: robust optimization; uncertain probabilities; uncertainty sets; stochastic programming; linear programming