Benders decomposition

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

Minimize ${\displaystyle cx}$

Subject to:

${\displaystyle Cx\leq b_{2}}$

${\displaystyle 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 ${\displaystyle Ax+By\leq b_{1}}$ or ${\displaystyle 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 ${\displaystyle x}$ may limit the value of ${\displaystyle y}$ due to constraint ${\displaystyle Ax+By\leq b_{1}}$, and hence it is possible that you get a good ${\displaystyle x}$ but have to choose a poor ${\displaystyle y}$ such that the overall objective function ${\displaystyle cx+dy}$ is NOT minimized.].

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 ${\displaystyle x^{*}}$ be the current solution of the ${\displaystyle x}$ variables according to the current iteration of the master problem. Since ${\displaystyle Ax^{*}}$ is just some numeric matrix, we can use it to rephrase the subproblem so that only ${\displaystyle y}$ variables are taken into account.

Minimize: ${\displaystyle dy}$

Subject to:

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

${\displaystyle Gy\leq b_{3}}$

${\displaystyle 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: ${\displaystyle p_{1}(b_{1}-Ax^{*})+p_{2}b_{3}}$

Subject to:

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

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

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 ${\displaystyle x^{*}}$. Recall that changing the master problem's suggestions for ${\displaystyle 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, ${\displaystyle \delta }$, can change its optimum by changing its feasible space.[1] This means that despite the fact that the primal is infeasible for this subproblem, it can become feasible with a different proposal for ${\displaystyle x^{*}}$. We must now restrict the feasible space of the master problem and find a new proposal for ${\displaystyle 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.

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 ${\displaystyle 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.

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