Decomposition methods for multi-horizon stochastic programming
Open Access
- 10 May 2024
- journal article
- research article
- Published by Springer Nature in Computational Management Science
- Vol. 21 (1) , 1-24
Abstract
Multi-horizon stochastic programming includes short-term and long-term uncertainty in investment planning problems more efficiently than traditional multi-stage stochastic programming. In this paper, we exploit the block separable structure of multi-horizon stochastic linear programming, and establish that it can be decomposed by Benders decomposition and Lagrangean decomposition. In addition, we propose parallel Lagrangean decomposition with primal reduction that, (1) solves the scenario subproblems in parallel, (2) reduces the primal problem by keeping one copy for each scenario group at each stage, and (3) solves the reduced primal problem in parallel. We apply the parallel Lagrangean decomposition with primal reduction, Lagrangean decomposition and Benders decomposition to solve a stochastic energy system investment planning problem. The computational results show that: (a) the Lagrangean type decomposition algorithms have better convergence at the first iterations to Benders decomposition, and (b) parallel Lagrangean decomposition with primal reduction is very efficient for solving multi-horizon stochastic programming problems. Based on the computational results, the choice of algorithms for multi-horizon stochastic programming is discussed.Keywords
All Related Versions
Funding Information
- Norges Forskningsråd (296207)
- NTNU Norwegian University of Science and Technology
This publication has 10 references indexed in Scilit:
- EMPIRE: An open-source model based on multi-horizon programming for energy transition analysesSoftwareX, 2022
- Benders decomposition with adaptive oracles for large scale optimizationMathematical Programming Computation, 2020
- Bounds in multi-horizon stochastic programsAnnals of Operations Research, 2019
- On capacity expansion planning under strategic and operational uncertainties based on stochastic dominance risk averse managementComputational Management Science, 2018
- JuMP: A Modeling Language for Mathematical OptimizationSIAM Review, 2017
- Multi-horizon stochastic programmingComputational Management Science, 2013
- Introduction to Stochastic Programming2011
- Multistage stochastic programs with block-separable recourse1986
- Decomposition and Partitioning Methods for Multistage Stochastic Linear ProgramsOperations Research, 1985
- Partitioning procedures for solving mixed-variables programming problemsNumerische Mathematik, 1962