Benders decomposition (or Benders' decomposition) is a technique in mathematical programming that allows the solution of very large linear programming problems that have a special block structure.
This block structure often occurs in applications such as stochastic programming as the uncertainty is usually represented with scenarios.
The strategy behind Benders decomposition can be summarized as divide-and-conquer.
That is, in Benders decomposition, the variables of the original problem are divided into two subsets so that a first-stage master problem is solved over the first set of variables, and the values for the second set of variables are determined in a second-stage subproblem for a given first-stage solution.
If the subproblem determines that the fixed first-stage decisions are in fact infeasible, then so-called Benders cuts are generated and added to the master problem, which is then re-solved until no cuts can be generated.
Since Benders decomposition adds new constraints as it progresses towards a solution, the approach is called "row generation".
Information from these subproblems is passed back to the master problem.
If constraints for a subproblem were violated, they can be added back to the master problem.
The master problem represents an initial convex set which is further constrained by information gathered from the subproblems.
Because the feasible space only shrinks as information is added, the objective value for the master function provides a lower bound on the objective function of the overall problem.
Benders Decomposition is applicable to problems with a largely block-diagonal structure.
The set of cuts will be filled in a sequence of iterations by solving the inner maximization problem of the minimax formulation.
The cuts both guide the master problem towards an optimal
starts unconstrained and we only add constraints at each iteration, meaning the feasible space can only shrink, the value of the master problem at any iteration provides a lower bound on the solution to the overall problem.
can either be a finite optimal value for which an extreme point
in the recession cone can be found, or a finding that the subproblem is infeasible.
At a high level, the procedure will iteratively consider the master problem and subproblem.
Each iteration provides an updated upper and lower bound on the optimal objective value.
The procedure terminates when it is shown that no finite optimal solution exists or when the gap between the upper and lower bound is sufficiently small.
is determined by solving the primal residual problem fixing
Formally, the procedure begins with the lower bound set to
Then the iterative procedure begins and continues until the gap between the upper and lower bound is at most
or it is shown that no finite optimal solution exists.
The first step of each iteration begins by updating the upper bound by solving the subproblem given the most recent value of
In the first case, the objective value of the subproblem is unbounded above.
This solution can be removed from the master problem by taking an extreme ray
that certifies the subproblem has unbounded objective and adding a constraint to the master asserting that
By duality theory for linear programs, the optimal value of the subproblem is equal to the optimal value of the original problem constrained on the choice of
, it also yields a new constraint that requires the master problem to consider the objective value under this particular solution by asserting that
is determined by solving the primal residual problem fixing