# Benders Decomposition Type of Optimality Cut

In Bender's decomposition we use optimality cuts.

An optimality cut is $\pi^T (h-Bx)\leq\phi$ or $b^Ty'+\pi^T (x-\hat x)\leq\phi$, depending on the subproblem.

I read in the book that both cuts have the same effect. Why? Is there any proof?

For more explanation:

First the master problem is solved, which provides us with a solution vector and lower bound. We then use this vector to construct a subproblem. For a minimization problem, subproblems give an upper bound. If the upper bound is strictly greater than the lower bound, then we add a Bender's cut to remove this point.

We want to solve the below problem by Bender's method:

$$\begin{split} \min &\; c^Tx + b^Ty\\ \text{s.t.} & \; Ax \ge d\\ & \; Bx +Dy \ge h\\ & \; y\ge0,\ x\in\mathbb{X} \end{split} \label{OP}$$

The master and subproblems are:

Master Problem

$$\begin{split} \min &\; c^Tx + \phi\\ \text{s.t.} & \;Ax \ge d\\ & \; x\in\mathbb{X} \end{split} \label{OP1}$$

Subproblem:

$$\begin{split} \min &\; b^Ty \\ \text{s.t.} &\; Dy \ge h- B\hat x\\ & \;y\ge0 \end{split} \label{OP3}$$ where $\hat x$ is a solution obtained from master problem that is fixed in the subproblem.

We use this optimality cut if the upper bound is strictly greater than the lower bound: $$\pi^T (h-Bx)\leq\phi,$$ where $\pi$ is an optimal solution for the dual of the subproblem.

Now suppose the subproblem is instead

$$\begin{split} \min &\; b^Ty \\ \text{s.t.} &\; Dy \ge h- B x\\ &\; x= \hat x\\ & \;y\ge0 \\ & \;x\ge0 \end{split} \label{OP7}$$

Then the optimality cut is $b^Ty'+\pi^T (x-\hat x)\leq\phi$ , where $y'$ and $\pi$ are optimal solutions obtained from the subproblem. Why are the two cuts equal?

Thanks

• Out of curiosity, which book are you using? – David M. Jun 12 '18 at 0:42
• @David M. "stochastic programing by chung:" booklet – linkho Jun 12 '18 at 6:29
• @David M. Can there be a connection between the shadow price and the cut? – linkho Jun 12 '18 at 6:32
• Is that a textbook? Can you provide a link? – David M. Jun 13 '18 at 23:29
• @David M. Hi , no unfortunately not , and the language of this book is not English too – linkho Jun 14 '18 at 5:45