File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s11750-021-00593-2
- Scopus: eid_2-s2.0-85101129565
- WOS: WOS:000618608600001
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: A column-and-constraint generation algorithm for two-stage stochastic programming problems
Title | A column-and-constraint generation algorithm for two-stage stochastic programming problems |
---|---|
Authors | |
Keywords | Stochastic programming Column-and-constraint generation Benders decomposition Facility location |
Issue Date | 2021 |
Publisher | Springer. The Journal's web site is located at http://www.springer.com/business/operations+research/journal/11750 |
Citation | TOP, 2021, v. 29, p. 781-798 How to Cite? |
Abstract | 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. |
Persistent Identifier | http://hdl.handle.net/10722/310142 |
ISSN | 2023 Impact Factor: 1.5 2023 SCImago Journal Rankings: 0.631 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Tonissen, DD | - |
dc.contributor.author | Arts, JJ | - |
dc.contributor.author | Shen, ZJM | - |
dc.date.accessioned | 2022-01-24T02:24:28Z | - |
dc.date.available | 2022-01-24T02:24:28Z | - |
dc.date.issued | 2021 | - |
dc.identifier.citation | TOP, 2021, v. 29, p. 781-798 | - |
dc.identifier.issn | 1134-5764 | - |
dc.identifier.uri | http://hdl.handle.net/10722/310142 | - |
dc.description.abstract | 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. | - |
dc.language | eng | - |
dc.publisher | Springer. The Journal's web site is located at http://www.springer.com/business/operations+research/journal/11750 | - |
dc.relation.ispartof | TOP | - |
dc.rights | This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. | - |
dc.subject | Stochastic programming | - |
dc.subject | Column-and-constraint generation | - |
dc.subject | Benders decomposition | - |
dc.subject | Facility location | - |
dc.title | A column-and-constraint generation algorithm for two-stage stochastic programming problems | - |
dc.type | Article | - |
dc.identifier.email | Shen, ZJM: maxshen@hku.hk | - |
dc.identifier.authority | Shen, ZJM=rp02779 | - |
dc.description.nature | published_or_final_version | - |
dc.identifier.doi | 10.1007/s11750-021-00593-2 | - |
dc.identifier.scopus | eid_2-s2.0-85101129565 | - |
dc.identifier.hkuros | 331487 | - |
dc.identifier.volume | 29 | - |
dc.identifier.spage | 781 | - |
dc.identifier.epage | 798 | - |
dc.identifier.isi | WOS:000618608600001 | - |
dc.publisher.place | Germany | - |