A Cutting-plane and Benders' Decomposition Algorithm for Two-Stage Distributionally Robust Convex programs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909813569486848 |
|---|---|
| author | Luo, Fengqiao Dey, Shibshankar Mehrotra, Sanjay |
| author_facet | Luo, Fengqiao Dey, Shibshankar Mehrotra, Sanjay |
| contents | We present a finitely convergent cutting-plane algorithm for solving a general mixed-integer convex program given an oracle for solving a general convex program. This method is extended to solve a family of two-stage mixed-integer convex programs using cutting planes, with applications to solving distributionally-robust two-stage stochastic mixed-integer convex programs. Analysis is also given for the case where convex programming oracle provides an $epsilon$-optimal solution. We combine the cut generation with a branch-and-union scheme to develop a more practical algorithm. Computational results on generated test problems show the practicality of our algorithm. Specifically, results show that in the tested problems our algorithm achieves < 5% optimality gap in 12 hours. This gap is >17% with a commercial solver. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2112_04160 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | A Cutting-plane and Benders' Decomposition Algorithm for Two-Stage Distributionally Robust Convex programs Luo, Fengqiao Dey, Shibshankar Mehrotra, Sanjay Optimization and Control 90 We present a finitely convergent cutting-plane algorithm for solving a general mixed-integer convex program given an oracle for solving a general convex program. This method is extended to solve a family of two-stage mixed-integer convex programs using cutting planes, with applications to solving distributionally-robust two-stage stochastic mixed-integer convex programs. Analysis is also given for the case where convex programming oracle provides an $epsilon$-optimal solution. We combine the cut generation with a branch-and-union scheme to develop a more practical algorithm. Computational results on generated test problems show the practicality of our algorithm. Specifically, results show that in the tested problems our algorithm achieves < 5% optimality gap in 12 hours. This gap is >17% with a commercial solver. |
| title | A Cutting-plane and Benders' Decomposition Algorithm for Two-Stage Distributionally Robust Convex programs |
| topic | Optimization and Control 90 |
| url | https://arxiv.org/abs/2112.04160 |