A fast approximate column-and-constraint generation method for two-stage robust mixed-integer programs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918180944871424 |
|---|---|
| author | Goerigk, Marc Henke, Dorothee Kager, Johannes Schäfer, Fabian Thielen, Clemens |
| author_facet | Goerigk, Marc Henke, Dorothee Kager, Johannes Schäfer, Fabian Thielen, Clemens |
| contents | This paper presents a new column-and-constraint generation method for two-stage robust mixed-integer programs with finite uncertainty sets. Our method combines and extends speed-up techniques used in previous column-and-constraint generation methods and introduces several new techniques. In particular, it uses dual bounds for second-stage problems in order to allow a faster identification of the next promising scenario to be added to the master problem. Moreover, adaptive time limits are imposed to avoid getting stuck on particularly hard second-stage problems, and a gap propagation between master problem and second-stage problems is used to stop solving them earlier if only a given non-zero optimality gap is to be reached overall. This makes our method particularly effective for problems where solving the second-stage problem is computationally challenging. To evaluate the method's performance, we compare it to two recent column-and-constraint generation methods from the literature on two applications: a robust capacitated location routing problem and a robust integrated berth allocation and quay crane assignment and scheduling problem. The first problem features a particularly hard second stage, and we show that our method is able to solve considerably more and larger instances in a given time limit. Using the second problem, we verify the general applicability of our method, even for problems where the second stage is relatively easy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_05388 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A fast approximate column-and-constraint generation method for two-stage robust mixed-integer programs Goerigk, Marc Henke, Dorothee Kager, Johannes Schäfer, Fabian Thielen, Clemens Optimization and Control This paper presents a new column-and-constraint generation method for two-stage robust mixed-integer programs with finite uncertainty sets. Our method combines and extends speed-up techniques used in previous column-and-constraint generation methods and introduces several new techniques. In particular, it uses dual bounds for second-stage problems in order to allow a faster identification of the next promising scenario to be added to the master problem. Moreover, adaptive time limits are imposed to avoid getting stuck on particularly hard second-stage problems, and a gap propagation between master problem and second-stage problems is used to stop solving them earlier if only a given non-zero optimality gap is to be reached overall. This makes our method particularly effective for problems where solving the second-stage problem is computationally challenging. To evaluate the method's performance, we compare it to two recent column-and-constraint generation methods from the literature on two applications: a robust capacitated location routing problem and a robust integrated berth allocation and quay crane assignment and scheduling problem. The first problem features a particularly hard second stage, and we show that our method is able to solve considerably more and larger instances in a given time limit. Using the second problem, we verify the general applicability of our method, even for problems where the second stage is relatively easy. |
| title | A fast approximate column-and-constraint generation method for two-stage robust mixed-integer programs |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2501.05388 |