Resumen de Solving large-scale two-stage stochastic optimization problems by specialized interior point methods
Paula de la Lama Zubirán
Two-stage stochastic optimization models give rise to very large linear problems (LP). Several approaches have been devised for efficiently solving them, among which are interior-point methods (IPM). However, using IPM, the linking columns that are associated with first-stage decisions cause excessive fill-ins for the solutions of the normal equations, thus making the procedure computationally expensive. We have taken a step forward on the road to a better solution by reformulating the LP through a variable splitting technique which has significantly reduced the solution time.
This work presents a specialized IPM that first applies variable splitting, then exploits the structure of the deterministic equivalent formulation of the stochastic problem. The specialized IPM works with an algorithm that combines Cholesky factorization and preconditioned conjugate gradients for solving the normal equations when computing the Newton direction for stochastic optimization problems in which the first-stages variables are large enough. Our specialized approach outperforms standard IPM.
This work provides the computational results of two stochastic problems from the literature: (1) a supply chain system and (2) capacity expansion in an electric system. Both linear and quadratic formulations were used to obtain instances of up to 39 million variables and six million constraints. When used in these applications, the computational results show that our procedure is more efficient than alternative state-of-the-art IP implementations (e.g., CPLEX) and other specialized methods for stochastic optimization.
