  


On solving largescale multistage stochastic problems with a new specialized interiorpoint approach
Jordi Castro(jordi.castroupc.edu) Abstract: A novel approach based on a specialized interiorpoint method (IPM) is presented for solving largescale stochastic multistage continuous optimization problems, which represent the uncertainty in strategic multistage and operational twostage scenario trees, the latter being rooted at the strategic nodes. This new solution approach considers a splitvariable formulation of the strategic and operational structures, for which copies are made of the strategic nodes and the structures are rooted in the form of nested strategicoperational twostage trees. The specialized IPM solves the normal equations of the problem's Newton system by combining Cholesky factorizations with preconditioned conjugate gradients, doing so for, respectively, the constraints of the stochastic formulation and those that equate the splitvariables. We show that, for multistage stochastic problems, the preconditioner (i) is a blockdiagonal matrix composed of as many shifted tridiagonal matrices as the number of nested strategicoperational twostage 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 largescale twostage problem. A broad computational experience is reported for large multistage stochastic supply network design (SND) and revenue management (RM) problems; the mathematical structures vary greatly for those two application types. Some of the most difficult instances of SND had 5 stages, 839 million variables, 13 million quadratic variables, 21 million constraints, and 3750 scenario tree nodes; while those of RM had 8 stages, 278 million variables, 100 million constraints, and 100,000 scenario tree nodes. For those problems, the proposed approach obtained the solution in 2.3 days using 167 gigabytes of memory for SND, and in 1.7 days using 83 gigabytes for RM; while the stateoftheart solver CPLEX v20.1 required more than 24 days and 526 gigabytes for SND, and more than 19 days and 410 gigabytes for RM. Keywords: interiorpoint methods ; multistage stochastic optimization ; strategic and operational uncertainties ; largescale optimization ; twostage structures ; preconditioned conjugate gradient Category 1: Linear, Cone and Semidefinite Programming Category 2: Stochastic Programming Citation: J. Castro, L.F. Escudero, J.F. Monge, On solving largescale multistage stochastic problems with a new specialized interiorpoint approach, Research Report UPCDEIOJC202102, Dept. of Statistics and Operations Research, Universitat Politècnica de Catalunya, Barcelona, Catalonia, 2021. Download: [PDF] Entry Submitted: 12/20/2021 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  