Approximating value functions via corner Benders' cuts
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911186864308224 |
|---|---|
| author | Ota, Matheus J. Fukasawa, Ricardo Kazachkov, Aleksandr M. |
| author_facet | Ota, Matheus J. Fukasawa, Ricardo Kazachkov, Aleksandr M. |
| contents | We introduce a novel technique to generate Benders' cuts from a conic relaxation ("corner") derived from a basis of a higher-dimensional polyhedron that we aim to outer approximate in a lower-dimensional space. To generate facet-defining inequalities for the epigraph associated to this corner, we develop a computationally-efficient algorithm based on a compact reverse polar formulation and a row generation scheme that handles the redundant inequalities. Via a known connection between arc-flow and path-flow formulations, we show that our method can recover the linear programming bound of a Dantzig-Wolfe formulation using multiple cuts in the projected space. In computational experiments, our generic technique enhances the performance of a problem-specific state-of-the-art algorithm for the vehicle routing problem with stochastic demands, a well-studied variant of the classic capacitated vehicle routing problem that accounts for customer demand uncertainty. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_21758 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximating value functions via corner Benders' cuts Ota, Matheus J. Fukasawa, Ricardo Kazachkov, Aleksandr M. Optimization and Control We introduce a novel technique to generate Benders' cuts from a conic relaxation ("corner") derived from a basis of a higher-dimensional polyhedron that we aim to outer approximate in a lower-dimensional space. To generate facet-defining inequalities for the epigraph associated to this corner, we develop a computationally-efficient algorithm based on a compact reverse polar formulation and a row generation scheme that handles the redundant inequalities. Via a known connection between arc-flow and path-flow formulations, we show that our method can recover the linear programming bound of a Dantzig-Wolfe formulation using multiple cuts in the projected space. In computational experiments, our generic technique enhances the performance of a problem-specific state-of-the-art algorithm for the vehicle routing problem with stochastic demands, a well-studied variant of the classic capacitated vehicle routing problem that accounts for customer demand uncertainty. |
| title | Approximating value functions via corner Benders' cuts |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2509.21758 |