×

Computational complexity of stochastic programming problems. (English) Zbl 1134.90027

Math. Program. 106, No. 3 (A), 423-432 (2006); erratum ibid. 153, No. 2 (A), 723-725 (2015).
Summary: Stochastic programming is the subfield of mathematical programming that considers optimization in the presence of uncertainty. During the last four decades a vast quantity of literature on the subject has appeared. Developments in the theory of computational complexity allow us to establish the theoretical complexity of a variety of stochastic programming problems studied in this literature. Under the assumption that the stochastic parameters are independently distributed, we show that two-stage stochastic programming problems are P-hard. Under the same assumption we show that certain multi-stage stochastic programming problems are PSPACE-hard. The problems we consider are non-standard in that distributions of stochastic parameters in later stages depend on decisions made in earlier stages.

MSC:

90C15 Stochastic programming
90C60 Abstract computational complexity for mathematical programming problems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Birge, J.R., Louveaux, F.V.: Introduction to Stochastic Programming, Springer Verlag, New York, 1997 · Zbl 0892.90142
[2] Dempster, No article title, Math. Oper. Res., 8, 525 (1983) · Zbl 0532.90078
[3] Dyer, No article title, SIAM J. Comput., 17, 967 (1988) · Zbl 0668.68049
[4] Dyer, M.E., Frieze, A.M.: Computing the Volume of Convex Bodies: A Case where Randomness Provably Helps. In: Symposia in Applied Mathematics, volume 44, American Mathematical Society, 1991, pp. 123-169 · Zbl 0754.68052
[5] Dyer, M.E., Kannan, R., Stougie, L.: A simple randomised algorithm for convex optimization. SPOR-Report 2002-05, Department of Mathematics and Computer Science Technische Universiteit Eindhoven Eindhoven The Netherlands, 2002 http://www. win. tue.nl/math/bs/spor/2002-05. pdf <RefTarget Address=“http://www. win. tue.nl/math/bs/spor/2002-05. pdf” TargetType=“URL”/> · Zbl 1297.90116
[6] Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness, Freeman, New York, 1979 · Zbl 0411.68039
[7] Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York, 1988 · Zbl 0634.05001
[8] Kall, P., Wallace, S.W.: Stochastic Programming. Wiley, Chichester, 1994
[9] Lawrence, No article title, Math. Comput., 57, 259 (1991) · Zbl 0734.52009
[10] Papadimitriou, No article title, J. Comput. Syst. Sci., 31, 288 (1985) · Zbl 0583.68020
[11] Papadimitriou, C.H.: Computational complexity. Addison-Wesley, Reading MA, 1994 · Zbl 0833.68049
[12] Prékopa, A.: Stochastic Programming. Kluwer Academic Publishers, Dordrecht, 1995 · Zbl 0863.90116
[13] Rockafellar, R.T., Wets, R.J-B.: Variational Analysis. Springer-Verlag, New York, 1997 · Zbl 0888.49001
[14] Ruszczynski, A., Shapiro, A. (eds.): Stochastic Programming, volume 10 of Handbooks in Operations Research and Management Science. North-Holland, 2003 · Zbl 1115.90001
[15] Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester, 1986 · Zbl 0665.90063
[16] Shmoys, D.B., Swamy, C.: Approximation schemes for two-stage stochastic optimization problems. In: Proc. of the Fourty Fifth IEEE Symposium on Foundations of Computer Science, Extended version: An Approximation Scheme for Stochastic Linear Programming and its Application to Stochastic Integer Programs, 2004, pp. 228-237 http://ist. caltech.edu/ cswamy/papers/stochopt. pdf
[17] Stougie, L.: Design and analysis of algorithms for stochastic integer programming, volume 37 of CWI Tract. Centrum voor Wiskunde en Informatica Amsterdam, 1987 · Zbl 0645.90046
[18] Stougie, L., van der Vlerk, M.H.: Approximation in stochastic integer programming. In: D.S. Johnson, J.K. Lenstra, D.B. Shmoys (eds.), Approximation Algorithms. Handbooks in Operations Research and Management Science. Springer-Verlag, Berlin, to appear. http://www.win.tue.nl/math/bs/spor/2005-10.pdf · Zbl 1068.90523
[19] Toda, No article title, SIAM J. Comput., 20, 865 (1991) · Zbl 0733.68034
[20] Valiant, No article title, SIAM J. Comput., 8, 410 (1979) · Zbl 0419.68082
[21] van der Vlerk, M.H.: Stochastic programming with integer recourse. PhD thesis, University of Groningen, The Netherlands, 1995 · Zbl 0792.90053
[22] Slyke, No article title, SIAM J. Appl. Math., 17, 638 (1969) · Zbl 0197.45602
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.