Benders' decomposition is a classical algorithm for solving two-stage stochastic programs whose deterministic equivalent grows too large for a solver to handle directly. The key insight is that fixing the first-stage (complicating) variables makes all scenario subproblems independent. LP duality is then used to extract affine lower bounds (optimality cuts) from each subproblem's dual solution, which are fed back to a small master problem. The master iteratively refines its approximation of the expected recourse cost until convergence. The post covers the block-angular structure of the constraint matrix, the piecewise-linear convexity of the value function, uni-cut vs. multi-cut variants, feasibility cuts for infeasible subproblems, practical pitfalls (slow convergence, master bottleneck, integer first stages), and pointers to SDDP for multi-stage extensions.
