Benders decomposition

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 technique is named after Jacques F. Benders.

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". In contrast, Dantzig–Wolfe decomposition uses "column generation".

Methodology

Assume a problem that occurs in two or more stages, where the decisions for the later stages rely on the results from the earlier ones. An attempt at first-stage decisions can be made without prior knowledge of optimality according to later stage decisions. This first-stage decision is the master problem. Further stages can then be analyzed as separate subproblems. 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 is then re-solved.

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 can be thought of as an upper bound on the objective function of the overall problem. Bender's Decomposition is applicable to problems with a largely block-diagonal structure, as shown below.

Mathematical Formulation

Assume a problem of the following structure:

Minimize $cx+dy$

Subject to:

$Ax+By\leq b_{1}$

$Cx\leq b_{2}$

$Gy\leq b_{3}$

$x,y\geq 0$

Where $A,B$ represent the constraints shared by both stages of variables, $C$ represents the variables unique to $x$, and $G$ represents the variables unique to $y$.

Master Problem Formulation

The decisions for the first stage problem can be described by the smaller minimization problem:

Minimize $cx$

Subject to:

$Cx\leq b_{2}$

$x\geq 0$

Solving this master problem will constitute a "first guess" at an optimal solution to the overall problem. Note that because the solution to this problem may violate one of the constraints $Ax+By\leq b_{1}$ or $Gy\leq b_{3}$, we are not guaranteed that this master problem is feasible in the space of the overall problem. However, according to the delayed constraint generation methodology, the feasible space of the problem can only shrink. This means that if our master problem's optimal solution is still feasible in the space of the entire problem, it will be optimal [No, you can not guarantee it. Note that the value of $x$ may limit the value of $y$ due to constraint $Ax+By\leq b_{1}$, and hence it is possible that you get a good $x$ but have to choose a poor $y$ such that the overall objective function $cx+dy$ is NOT minimized.].

Subproblem Formulation

We will take the suggested solution to the master problem and will plug it into each of our subproblems in order to assess feasibility of the proposed solution. Let $x^{*}$ be the current solution of the $x$ variables according to the current iteration of the master problem. Since $Ax^{*}$ is just some numeric matrix, we can use it to rephrase the subproblem so that only $y$ variables are taken into account.

Minimize: $dy$

Subject to:

$By\leq b_{1}-Ax^{*}$

$Gy\leq b_{3}$

$y\geq 0$

According to duality theory, if the dual to this optimization problem has a finite optimal solution, so does the primal solution. Furthermore, if the dual of the problem is unbounded above then the primal has no solution. We can therefore use the dual to assess the feasibility of the primal problem, thereby assessing the optimality of the master problem. The dual to this problem as it is written is:

Maximize: $p_{1}(b_{1}-Ax^{*})+p_{2}b_{3}$

Subject to:

$p_{1}'B+p_{2}'G\leq d$

$p_{1},p_{2}\leq 0$

Termination Conditions

Results from the subproblem lead us into a few potential cases for the master problem.

Case 1

The dual of the subproblem is unbounded above. In this case, the subproblem is infeasible and the dual of the subproblem formed an upward-facing cone.

Note that this does not imply that the subproblem is infeasible for all values of $x^{*}$. Recall that changing the master problem's suggestions for $x^{*}$ will amount to changing the right hand side (RHS) vector of the linear programming problem that forms the dual. In order to find an optimal solution in the primal, we must restrict the dual by making its optimum finite.

Note that according to sensitivity analysis, changing the RHS of the problem past some threshold, $\delta$, can change its optimum by changing its feasible space. This means that despite the fact that the primal is infeasible for this subproblem, it can become feasible with a different proposal for $x^{*}$. We must now restrict the feasible space of the master problem and find a new proposal for $x^{*}$.

Generating a feasibility cut: feasibility cuts are the hallmark of Bender's decomposition. We must add a new constraint to the master problem: in this case, we want to restrict the recession cone that we found in the dual of the subproblem.

Case 2

The dual of the subproblem is infeasible. Like in the previous problem, this implies that the primal subproblem is infeasible. This time, however, it has very different implications: since the dual feasible space was empty, we know that there is no change to the vector $x^{*}$ that will create a feasible primal subproblem. This can either mean that the overall problem is infeasible, or that the overall problem has an unbounded objective function. In either case, we terminate.

Case 3

The dual of the subproblem returns a finite optimum. By duality theory, the optimum of the primal subproblem is the same.

See also

• FortSP solver uses Benders decomposition for solving stochastic programming problems

References

• Benders, J. F. (Sept. 1962), "Partitioning procedures for solving mixed-variables programming problems", Numerische Mathematik 4(3): 238–252.
• Lasdon, Leon S. (2002), Optimization Theory for Large Systems (reprint of the 1970 Macmillan ed.), Mineola, New York: Dover Publications, pp. xiii+523, MR 1888251.