Benders’ Decomposition 101: How to Crack Open a Stochastic Program That’s Too Big to Swallow Whole

Stochastic optimization problems can become computationally intractable as the number of future scenarios grows, causing the standard model to become too large to solve. The key insight behind Benders' decomposition is that if the initial, first-stage decisions were fixed, the massive problem would separate into many smaller, independent subproblems. This powerful algorithm exploits this structure by iteratively solving a simplified "master problem" to propose a solution, then solving the individual scenario subproblems. Feedback from the subproblems generates "optimality cuts" that progressively refine the master problem, allowing the algorithm to find the optimal solution without ever tackling the full, unwieldy model.