Benders Decomposition: A Humanitarian Operation with Stochastic Programming Framework

Benders Decomposition (BD) is a popular large-scale optimization technique. Within an iterative framework, it attempts to solve difficult problems by fixing complicating variables. Researchers have successfully applied this exact method to a variety of challenging, large-scale optimization problems in diverse domains such as telecommunication, transportation and logistics, emergency management, sustainable energy management, healthcare, etc. Although this decomposition framework is quite general, the structural aspect of the two-stage stochastic programming (SP) models that represent data uncertainties by scenarios makes this class of problem particularly amenable to BD. The wide popularity of SP as an optimization tool for decision-making under uncertainties and the possibility of successfully applying BD to solve large-scale instances makes this technique attractive. This chapter begins with a mathematical foundation for the BD framework, followed by a step-by-step guide to iteratively solve a mixed-integer programming model by decomposing the same into a relaxed master problem and one or more subproblems. We demonstrate an application of this well-known large-scale optimization technique in stochastic settings and illustrate the concept through an example inspired by a research problem. We conclude the chapter by discussing a variety of implementation-related challenges and some contemporary implementation strategies utilizing the state-of-the-art CPLEX solver.