Benders Decomposition

Abstract Benders decomposition is a solution method for solving certain large‐scale optimization problems. Instead of considering all decision variables and constraints of a large‐scale problem simultaneously, Benders decomposition partitions the problem into multiple smaller problems. Since computational difficulty of optimization problems increases significantly with the number of variables and constraints, solving these smaller problems iteratively can be more efficient than solving a single large problem. In this article, we first formally describe Benders decomposition. We then briefly describe some extensions and generalizations of Benders decomposition. We conclude our article by illustrating how the decomposition works on a problem encountered in Intensity Modulated Radiation Therapy (IMRT) treatment planning and giving a numerical example.