This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by So, A. M.-C. Articles by Ye, Y.

Stochastic Combinatorial Optimization with Controllable Risk Aversion Level

Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, N. T., Hong Kong
Department of Information, Operations, and Management Sciences, Stern School of Business, New York University, New York, New York 10012
Department of Management Science and Engineering, Stanford University, Stanford, California 94305
manchoso{at}se.cuhk.edu.hk
jzhang{at}stern.nyu.edu
yinyu-ye{at}stanford.edu

Most of the recent work on 2-stage stochastic combinatorial optimization problems has focused on minimization of the expected cost or the worst-case cost of the solution. Those two objectives can be viewed as two extreme ways of handling risk. In this paper we propose to use a one-parameter family of functionals to interpolate between them. Although such a family has been used in the mathematical finance and stochastic programming literature before, its use in the context of approximation algorithms seems new. We show that under standard assumptions, a broad class of risk-adjusted 2-stage stochastic programs can be efficiently treated by the sample average approximation (SAA) method. In particular, our result shows that it is computationally feasible to incorporate some degree of robustness even when the underlying distribution can only be accessed in a black-box fashion. We also show that when combined with suitable rounding procedures, our result yields new approximation algorithms for many risk-adjusted 2-stage stochastic combinatorial optimization problems under the black-box setting.

Key Words: stochastic optimization; risk measure; sample average approximation (SAA); approximation algorithm; combinatorial optimization
History: Received: December 13, 2008; revision received: February 13, 2009;