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: |