How Benders Decomposition Works Part I: Optimality Cuts

Benders decomposition is an optimization technique for problems combining strategic and operational decisions by partitioning them into a master problem and a subproblem. The master problem proposes high-level strategic choices, and the subproblem evaluates their operational costs. This iterative process improves the solution by generating Benders optimality cuts, which are derived from the dual of the subproblem's linear program. These cuts are then added back to the master problem, progressively refining its understanding of the true operational costs until an optimal solution is found.