Many large Mixed-Integer Programs have a block structure: some variables are "complicating" (they couple different parts of the problem together), while others are easy to optimise once the complicating variables are fixed. Benders decomposition splits the problem into two: a master problem that chooses the complicating (usually integer) variables, and a subproblem that, given fixed complicating variables, optimises the remaining (usually continuous) variables as an LP.
The subproblem solves exactly and provides two types of information: optimality cuts (if feasible: the subproblem cost as a function of the master variables) and feasibility cuts (if infeasible: a constraint saying this combination of master variables is infeasible). These cuts are added to the master, which re-solves with a tighter approximation. Iteration continues until the upper bound (from the subproblem) and lower bound (from the master) meet, proving optimality.
Master problem: Choose which 3 of 10 warehouses to open (binary variables y_i). The master decides the expensive, discrete choice.
Subproblem: Given the set of open warehouses, allocate demand to them at minimum transportation cost (continuous variables x_ij = flow from warehouse i to customer j). This is a pure transportation LP.
Iteration 1: Master proposes opening warehouses A, B, D. Subproblem solves the transportation LP: if feasible, it returns the cost of serving all demand (say, 500 units × cost) — this generates an optimality cut. If infeasible (e.g., warehouses A and B together cannot serve customer 3), it returns a feasibility cut.
Convergence: Master re-solves with the cut, proposing a new set of warehouses. Subproblem solves again. After a few iterations, both bounds meet and the algorithm terminates with the provably optimal warehouse configuration.
Benders decomposition works with primal information from the LP subproblem dual. It generates valid inequalities (cuts) from subproblem feasibility/infeasibility. The master problem is solved exactly (or with branch-and-bound) at each iteration. Convergence is guaranteed by the finite number of possible cuts.
Lagrangian relaxation dualises constraints into the objective with multipliers, relaxing the problem into independent subproblems. It iterates on the multipliers (using subgradient methods) to tighten the lower bound. The subproblems decompose completely, but feasibility is not guaranteed — a heuristic step is needed to recover a feasible solution.
Benders suits problems with a clear master-subproblem structure and small integer decisions (where the master is tractable). Lagrangian suits problems where dualisation creates natural decomposition and integer feasibility is difficult to enforce.
Benders is worth implementing when fixing the integer variables makes the remaining problem easy. If the subproblem is also hard, decomposition adds overhead without payoff.