Optimization Online


A new interior-point approach for large two-stage stochastic problems

Jordi Castro (jordi.castro***at***upc.edu)
Paula de la Lama (paula.de.la.lama***at***upc.edu)

Abstract: Two-stage stochastic models give rise to very large optimization problems. Several approaches have been devised for efficiently solving them, including interior-point methods (IPMs). However, using IPMs, the linking columns associated to first-stage decisions cause excessive fill-in for the solution of the normal equations. This downside is usually alleviated if variable splitting is applied to first-stage variables. This work presents a specialized IPM that applies variable splitting and exploits the structure of the deterministic equivalent of the stochastic problem. The specialized IPM combines Cholesky factorizations and preconditioned conjugate gradients for solving the normal equations. This specialized IPM outperforms other approaches when the number of first-stage variables is large enough. This paper provides computational results for two stochastic problems: (1) a supply chain system and (2) capacity expansion in an electric system. Both linear and convex quadratic formulations were used, obtaining instances of up to 38 million variables and six million constraints. The computational results show that our procedure is more efficient than alternative state-of-the-art IPM implementations (e.g., CPLEX) and other specialized solvers for stochastic optimization.

Keywords: interior-point methods; stochastic optimization; structured problems; large-scale optimization

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Stochastic Programming

Category 3: Optimization Software and Modeling Systems (Optimization Software Benchmark )

Citation: Research Report UPC-DEIO-JC DR 2020-01, Dept. of Statistics and Operations Research, Universitat Politècnica de Catalunya, Barcelona, Catalonia, April 2020.

Download: [PDF]

Entry Submitted: 04/09/2020
Entry Accepted: 04/09/2020
Entry Last Modified: 04/09/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society