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

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 with 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 6 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

2010 Mathematics Subject Classifications:

• 90C51
• 90C15
• 90C06

Acknowledgments

This work has been supported by the grants MINECO/FEDER MTM2015-65362-R and MCIU/AEI/FEDER RTI2018-097580-B-I00. The second author was supported by the CONACyT (Consejo Nacional de Ciencia y Tecnologia, México) grant CVU-394291. We also thank the two anonymous reviewers, whose suggestions and comments improved the quality of the paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work has been supported by the grants Ministerio de Economía y Competitividad (MINECO)/FEDER MTM2015-65362-R and MCIU/AEI/FEDER RTI2018-097580-B-I00. The second author was supported by the Consejo Nacional de Ciencia y Tecnología, México (CONACyT) grant CVU-394291.

Notes on contributors

Jordi Castro

Jordi Castro is full professor of the Dept. of Statistics and Operations Research of the Universitat Politècnica de Catalunya. His research interests are in computational and large-scale optimization.

Paula de la Lama-Zubirán

Paula de la Lama-Zubirán about to finish her PhD in the Dept. of Statistics and Operations Research of the Universitat Politècnica de Catalunya.