Abstract.
Robust-optimization models belong to a special class of stochastic programs, where the traditional expected cost minimization objective is replaced by one that explicitly addresses cost variability. This paper explores robust optimization in the context of two-stage planning systems. We show that, under arbitrary measures for variability, the robust optimization approach might lead to suboptimal solutions to the second-stage planning problem. As a result, the variability of the second-stage costs may be underestimated, thereby defeating the intended purpose of the model. We propose sufficient conditions on the variability measure to remedy this problem. Under the proposed conditions, a robust optimization model can be efficiently solved using a variant of the L-shaped decomposition algorithm for traditional stochastic linear programs. We apply the proposed framework to standard stochastic-programming test problems and to an application that arises in auctioning excess electric power.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahmed, S., Sahinidis, N.V.: Robust process planning under uncertainty. Industrial & Engineering Chemistry Research 37(5), 1883–1892 (1998)
Bai, D., Carpenter, T., Mulvey, J.M.: Making a case for robust models. Management Sci. 43, 895–907 (1997)
Bawa, V.: Optimal rules for ordering uncertain prospects. J. Financial Economics 2(1), 95–121 (1975)
Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming, Springer Verlag, 1997
Birge, J.R.: Option methods for incorporating risk into linear capacity planning models. Manufacturing & Service Operations Management 2(1), 19–31 (2000)
Fishburn, P.C.: Mean-risk analysis with risk associated with below-target returns. American Economic Rev. 67(2), 116–125 (1977)
Geoffrion, A. M.: Generalized Benders decomposition. J. Optim. Theory & Appl. 10, 237–260 (1972)
Huang, C.-F., Litzenberger, R.H.: Foundations for Financial Economics. Prentice Hall, 1988
Kall, P., Wallace, S.W.: Stochastic Programming. John Wiley & Sons, 1994
King, A.J.: Asymmetric risk measures and tracking models for portfolio optimization under uncertainty. Ann. Operations Res. 45, 165–177 (1993)
King, A.J., Takriti, S., Ahmed, S.: Issues in risk modeling for multi-stage systems. IBM Research Report, RC-20993, 1997
King, A.J.: Duality and martingales: a stochastic programming perspective on contingent claims. Math. Programming 91(3), 543–562 (2002)
Laguna, M.: Applying robust optimization to capacity expansion of one location in telecommunications with demand uncertainty. Management Sci. 44, S101–S110 (1998)
Linderoth, J., Shapiro, A., Wright, S.: The empirical behavior of sampling methods for stochastic programming. Optimization Technical Report 02-01, Computer Sciences Department, University of Wisconsin, January 2002, http://www.cs.wisc.edu/∼swright/
Luenberger, D.G.: Investment Science. Oxford University Press, 1998
Mak, W.-K., Morton, D.P., Wood, R.K.: Monte Carlo bounding techniques for determining solution quality in stochastic programs. Operations Res. Lett. 24, 47–56 (1999)
Malcolm, S.A., Zenios, S.A.: Robust optimization of power systems capacity expansion under uncertainty. J. operational res. soc. 45, 1040–1049 (1994)
Mulvey, J.M., Vanderbei, R.J., Zenios, S.A.: Robust optimization of large-scale systems. Operations Res. 43, 264–281 (1995)
Mulvey, J.M., Ruszczyński, A.: A new scenario decomposition method for large scale stochastic optimization. Operations Res. 43, 477–490 (1995)
Nawrocki, D.: A brief history of downside risk measures. J. Investing 9–26, Fall 1999
Porter, R.B.: Semivariance and stochastic dominance: A comparison, the American economic review, 64(1), 200–204 (1974)
Rockafellar, R.T.: Convex Analysis, Princeton University Press, 1970
Sen, S., Higle, J.L.: An introductory tutorial on stochastic linear programming. Interfaces 29, 33–61 (1999)
Takriti, S., Krasenbrink, B., Wu, L.S.-Y.: Incorporating fuel constraints and electricity spot prices into the stochastic unit commitment problem. Operations Research 48(2), 268–280 (2000)
van Slyke, R., Wets, R.J.-B.: L-shaped linear programs with applications to linear control and stochastic programming. SIAM J. Appl. Math. 17(4), 638–663 (1969)
Author information
Authors and Affiliations
Corresponding author
Additional information
Mathematics Subject Classification (1991): 90C15, 90C33, 90B50, 90A09, 90A43
Supported in part by NSF Grants DMI-0099726 and DMI-0133943
Rights and permissions
About this article
Cite this article
Takriti, S., Ahmed, S. On robust optimization of two-stage systems. Math. Program., Ser. A 99, 109–126 (2004). https://doi.org/10.1007/s10107-003-0373-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-003-0373-y