A column-and-constraint generation algorithm for two-stage stochastic programming problems

Autor: Zuo-Jun Max Shen, Denise D. Tönissen, Jacobus J. Arts
Přispěvatelé: Operations Planning Acc. & Control, Operations Analytics, Dutch Railways [sponsor]
Jazyk: angličtina
Rok vydání: 2021
Předmět:
Statistics and Probability
Information Systems and Management
Computer science
Benders decomposition
0211 other engineering and technologies
Stochastic programming
Column-and-constraint generation
02 engineering and technology
Management Science and Operations Research
Column (database)
Bottleneck
Multidisciplinaire
généralités & autres [C99] [Ingénierie
informatique & technologie]
Production
distribution & supply chain management [B02] [Business & economic sciences]
Matrix (mathematics)
Méthodes quantitatives en économie & gestion [B09] [Sciences économiques & de gestion]
0502 economics and business
Discrete Mathematics and Combinatorics
Facility location
Production
distribution & gestion de la chaîne logistique [B02] [Sciences économiques & de gestion]
SDG 7 - Affordable and Clean Energy
050210 logistics & transportation
021103 operations research
05 social sciences
Multidisciplinary
general & others [C99] [Engineering
computing & technology]
Column-and-Constraint generations
Distinctive feature
Quantitative methods in economics & management [B09] [Business & economic sciences]
Bender Decomposition
Facility location problem
Zero (linguistics)
Modeling and Simulation
Stage (hydrology)
Algorithm
Zdroj: TOP, 29(3), 781-798. Springer
TOP, 29(3), 781-798. Springer Verlag
Tönissen, D D, Arts, J J & Shen, Z J M 2021, ' A column-and-constraint generation algorithm for two-stage stochastic programming problems ', TOP, vol. 29, no. 3, pp. 781-798 . https://doi.org/10.1007/s11750-021-00593-2
ISSN: 1134-5764
Popis: This paper presents a column-and-constraint generation algorithm for two-stage stochastic programming problems. A distinctive feature of the algorithm is that it does not assume fixed recourse and as a consequence the values and dimensions of the recourse matrix can be uncertain. The proposed algorithm contains multi-cut (partial) Benders decomposition and the deterministic equivalent model as special cases and can be used to trade-off computational speed and memory requirements. The algorithm outperforms multi-cut (partial) Benders decomposition in computational time and the deterministic equivalent model in memory requirements for a maintenance location routing problem. In addition, for instances with a large number of scenarios, the algorithm outperforms the deterministic equivalent model in both computational time and memory requirements. Furthermore, we present an adaptive relative tolerance for instances for which the solution time of the master problem is the bottleneck and the slave problems can be solved relatively efficiently. The adaptive relative tolerance is large in early iterations and converges to zero for the final iteration(s) of the algorithm. The combination of this relative adaptive tolerance with the proposed algorithm decreases the computational time of our instances even further.
Databáze: OpenAIRE
Externí odkaz: