A computational study of cutting-plane methods for multi-stage stochastic integer programs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916235307909120 |
|---|---|
| author | Bansal, Akul Küçükyavuz, Simge |
| author_facet | Bansal, Akul Küçükyavuz, Simge |
| contents | We report a computational study of cutting plane algorithms for multi-stage stochastic mixed-integer programming models with the following cuts: (i) Benders', (ii) Integer L-shaped, and (iii) Lagrangian cuts. We first show that Integer L-shaped cuts correspond to one of the optimal solutions of the Lagrangian dual problem, and, therefore, belong to the class of Lagrangian cuts. To efficiently generate these cuts, we present an enhancement strategy to reduce time-consuming exact evaluations of integer subproblems by alternating between cuts derived from the relaxed and exact computation. Exact evaluations are only employed when Benders' cut from the relaxation fails to cut off the incumbent solution. Our preliminary computational results show the merit of this approach on multiple classes of real-world problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_02533 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A computational study of cutting-plane methods for multi-stage stochastic integer programs Bansal, Akul Küçükyavuz, Simge Optimization and Control Combinatorics We report a computational study of cutting plane algorithms for multi-stage stochastic mixed-integer programming models with the following cuts: (i) Benders', (ii) Integer L-shaped, and (iii) Lagrangian cuts. We first show that Integer L-shaped cuts correspond to one of the optimal solutions of the Lagrangian dual problem, and, therefore, belong to the class of Lagrangian cuts. To efficiently generate these cuts, we present an enhancement strategy to reduce time-consuming exact evaluations of integer subproblems by alternating between cuts derived from the relaxed and exact computation. Exact evaluations are only employed when Benders' cut from the relaxation fails to cut off the incumbent solution. Our preliminary computational results show the merit of this approach on multiple classes of real-world problems. |
| title | A computational study of cutting-plane methods for multi-stage stochastic integer programs |
| topic | Optimization and Control Combinatorics |
| url | https://arxiv.org/abs/2405.02533 |