{"ID":2864930,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.21758","arxiv_id":"2509.21758","title":"Approximating value functions via corner Benders' cuts","abstract":"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.","short_abstract":"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 computationa...","url_abs":"https://arxiv.org/abs/2509.21758","url_pdf":"https://arxiv.org/pdf/2509.21758v2","authors":"[\"Matheus J. Ota\",\"Ricardo Fukasawa\",\"Aleksandr M. Kazachkov\"]","published":"2025-09-26T01:42:38Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}