{"id":26910,"date":"2023-10-01T10:31:48","date_gmt":"2023-10-01T08:31:48","guid":{"rendered":"https:\/\/cio.umh.es\/?p=26910"},"modified":"2024-02-21T10:32:29","modified_gmt":"2024-02-21T09:32:29","slug":"jordi-castro-laureano-f-escudero-juan-f-monge-2023-on-solving-large-scale-multistage-stochastic-optimization-problems-with-a-new-specialized-interior-point-approach-european-journal-of-o","status":"publish","type":"post","link":"https:\/\/cio.umh.es\/en\/2023\/10\/01\/jordi-castro-laureano-f-escudero-juan-f-monge-2023-on-solving-large-scale-multistage-stochastic-optimization-problems-with-a-new-specialized-interior-point-approach-european-journal-of-o\/","title":{"rendered":"Jordi Castro, Laureano F. Escudero, &amp; Juan F. Monge (2023). On solving large-scale multistage stochastic optimization problems with a new specialized interior-point approach. European Journal of Operational Research, 310, 268-285."},"content":{"rendered":"<p><strong>Jordi Castro (Department of Statistics and Operations Research, Universitat Polit\u00e8cnica de Catalunya, Barcelona), Laureano F. Escudero (Area of Statistics and Operations Research, Universidad Rey Juan Carlos, M\u00f3stoles, Madrid)<\/strong> <strong>and Juan F. Monge (Operations Research Center, University Miguel Hern\u00e1ndez of Elche)\u00a0<\/strong><\/p>\n<p><strong>Abstract:<\/strong><\/p>\n<p><span>A novel approach based on a specialized interior-point method (IPM) is presented for solving large-scale stochastic multistage continuous optimization problems, which represent the uncertainty in strategic multistage and operational two-stage scenario trees. This new solution approach considers a split-variable formulation of the strategic and operational structures. The specialized IPM solves the normal equations by combining Cholesky factorizations with preconditioned conjugate gradients, doing so for, respectively, the constraints of the stochastic formulation and those that equate the split-variables. We show that, for multistage stochastic problems, the preconditioner (i) is a block-diagonal matrix composed of as many shifted tridiagonal matrices as the number of nested strategic-operational two-stage trees, thus allowing the efficient solution of systems of equations; (ii) its complexity in a multistage stochastic problem is equivalent to that of a very large-scale two-stage problem. A broad computational experience is reported for large multistage stochastic supply network design (SND) and revenue management (RM) problems. Some of the most difficult instances of SND had 5 stages, 839 million linear variables, 13 million quadratic variables, 21 million constraints, and 3750 scenario tree nodes; while those of RM had 8 stages, 278 million linear variables, 100 million constraints, and 100,000 scenario tree nodes. For those problems, the proposed approach obtained the solution in 1.1 days using 174\u00a0gigabytes of memory for SND, and in 1.7 days using 83\u00a0gigabytes for RM; while CPLEX v20.1 required more than 53 days and 531\u00a0gigabytes for SND, and more than 19 days and 410\u00a0gigabytes for RM.<\/span><\/p>","protected":false},"excerpt":{"rendered":"<p>Jordi Castro (Department of Statistics and Operations Research, Universitat Polit\u00e8cnica de Catalunya, Barcelona), Laureano F. Escudero (Area of Statistics and Operations Research, Universidad Rey Juan Carlos, M\u00f3stoles, Madrid) and Juan F. Monge (Operations Research Center, University Miguel Hern\u00e1ndez of Elche)\u00a0<br \/>\nAbstract:<br \/>\nA novel approach based on a specialized interior-point method (IPM) is presented for solving large-scale stochastic [&#8230;]<\/p>","protected":false},"author":11048,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_links_to":"","_links_to_target":""},"categories":[369888,75,7834],"tags":[381500],"_links":{"self":[{"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/posts\/26910"}],"collection":[{"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/users\/11048"}],"replies":[{"embeddable":true,"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/comments?post=26910"}],"version-history":[{"count":0,"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/posts\/26910\/revisions"}],"wp:attachment":[{"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/media?parent=26910"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/categories?post=26910"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/tags?post=26910"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}