Orateur
Description
We introduce a novel technique that generates Benders cuts from a corner relaxation of the target higher-dimensional polyhedron. Moreover, we develop a computationally efficient method to separate facet-defining inequalities for the epigraph
associated with this corner relaxation. By leveraging 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. We validate our approach with computational experiments on the vehicle routing problem with stochastic demands (VRPSD), a well-studied variant of the classic capacitated vehicle routing problem (CVRP) that accounts for customer
demand uncertainty. Computational experiments show that our generic technique can enhance the performance of a problem-specific state-of-the-art algorithm for the VRPSD.
