{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:29:38Z","timestamp":1787333378550,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[1998,11]]},"abstract":"<jats:p>In this paper, an interior point algorithm for linear programs is adapted for solving multistage stochastic linear programs. The algorithm is based on Monteiro and Adler's path-following algorithm for deterministic linear programs. In practice, the complexity of the algorithm is linear with respect to the size of the sample space. The algorithm starts from a feasible solution of the problem and proceeds along a path of random vectors. The cubic polynomial complexity of the algorithm for deterministic linear programs is derived from the calculations of the Newton steps. In the algorithm developed in this paper, the probabilistic structure of the problem is taken into consideration while calculating a Newton step and the size of the sample space appears linearly in the complexity. The development of an algorithm that requires a relatively small number of arithmetic operations, in terms of the sample space size, allows the use of the algorithm for multistage stochastic linear programs with a very large number of scenarios.<\/jats:p>","DOI":"10.1137\/s105262349528456x","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"956-972","source":"Crossref","is-referenced-by-count":3,"title":["An Interior Random Vector Algorithm for MultiStage Stochastic Linear Programs"],"prefix":"10.1137","volume":"8","author":[{"given":"Eithan","family":"Schweitzer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1955.tb00191.x"},{"key":"R2","unstructured":"E.Beale, J.Forrest, C.Taylor, Multi\u2010time\u2010period stochastic programming, Academic Press, London, 1980, 387\u201340281m:90081"},{"key":"R3","unstructured":"A. J. Berger, J. M. Mulvey, E. Rothberg, and R. J. Vanderbei,\n                      Solving Multistage Stochastic Programs Using Tree Dissection\n                      , Technical Report SOR 92\u20105, Department of Civil Engineering and Operations Research, Princeton University, Princeton, NJ, 1995."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1287\/opre.33.5.989"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF00249637"},{"key":"R6","unstructured":"J. Czyzyk, R. Fourer, and S. Mehrotra,\n                      A Study of the Augmented System and Column\u2010Splitting Approaches for Solving Two\u2010Stage Stochastic Linear Programs by Interior\u2010Point Methods\n                      , Technical Report 93\u201005, Department of Industrial and Management Science, Northwestern University, Evanston, IL, 1993."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1.3-4.197"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"G. B. Dantzig,\n                      Linear Programming and Extensions\n                      , Princeton University Press, Princeton NJ, 1963.","DOI":"10.7249\/R366"},{"key":"R9","volume-title":"Numerical techniques for stochastic optimization","author":"Wets R.","year":"1988"},{"key":"R10","unstructured":"A. V. Fiacco and G. P. McCormick,\n                      Nonlinear Programming: Sequential Unconstrained Minimization Techniques\n                      , John Wiley and Sons, New York, 1968."},{"key":"R11","unstructured":"J. Higle, S. Sen, and D. S. Yakowitz,\n                      Finite Master Programs in Stochastic Decomposition\n                      , Technical Report, Dept. of Systems and Industrial Engineering, The University of Arizona, Tucson, AZ, 1990."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589349"},{"key":"R13","unstructured":"G. Infanger,\n                      Planning Under Uncertainty: Solving Large\u2010Scale Stochastic Linear Programs\n                      , Boyd and Fraser, Danvers, MA, 1994."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"F.Louveaux, Y.Smeers, Optimal investments for electricity generation: a stochastic model and a test\u2010problem, Springer Ser. Comput. Math., Vol. 10, Springer, Berlin, 1988, 445\u2013453957328","DOI":"10.1007\/978-3-642-61370-8_24"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1287\/opre.39.5.757"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01587075"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01587076"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(92)90046-6"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"L.Nazareth, R.Wets, Nonlinear programming techniques applied to stochastic programs with recourse, Springer Ser. Comput. Math., Vol. 10, Springer, Berlin, 1988, 95\u2013121957308","DOI":"10.1007\/978-3-642-61370-8_4"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Y. Nesterov and A. Nemirovskii,\n                      Interior\u2010Point Polynomial Algorithms in Convex Programming\n                      , SIAM, Philadelphia, 1994.","DOI":"10.1137\/1.9781611970791"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581267"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/S0025-5610(96)00027-5"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/0117061"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/1016053"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"RogerWets, Stochastic programming, Handbooks Oper. Res. Management Sci., Vol. 1, North\u2010Holland, Amsterdam, 1989, 573\u20136291105107","DOI":"10.1016\/S0927-0507(89)01009-1"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S105262349528456X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:54:50Z","timestamp":1787331290000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S105262349528456X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,11]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,11]]}},"alternative-id":["10.1137\/S105262349528456X"],"URL":"https:\/\/doi.org\/10.1137\/s105262349528456x","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,11]]}}}