Branch and Incremental Benders cuts for two stage stochastic hub and spoke location-allocation problem

Abstract

Two-stage stochastic optimization has applications in various domains, including location-allocation, scheduling, routing, and other network flow problems. In practice, most of these problems are solved following a decomposition framework such as L-shaped algorithms based on Benders decomposition. Conventional multi-cut and single-cut Benders decomposition algorithms often struggle to reach optimality due to time constraints or the complexity of effective cut generation. In this talk, we are going to discuss an incremental Benders decomposition algorithm where we generate cuts for a subset of scenarios and then incrementally add cuts until optimality reaches for all scenarios. We incorporated our proposed framework into a branch-and-cut framework to solve stochastic hub and spoke location-allocation problems. Additionally, a set of valid inequalities and warm-up heuristics are implemented to accelerate the cut-generation process. We perform numerical studies for different test instances to compare the performance of the proposed algorithm with off-the-shelf MIP solvers and classical Bender decomposition algorithms to emphasize the efficiency of our approach.