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{equation} \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} \end{equation}
The master and subproblems are:
Master Problem
\begin{equation} \begin{split} \min &\; c^Tx + \phi\\ \text{s.t.} & \;Ax \ge d\\ & \; x\in\mathbb{X} \end{split} \label{OP1} \end{equation}
Subproblem:
\begin{equation} \begin{split} \min &\; b^Ty \\ \text{s.t.} &\; Dy \ge h- B\hat x\\ & \;y\ge0 \end{split} \label{OP3} \end{equation} 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{equation} \begin{split} \min &\; b^Ty \\ \text{s.t.} &\; Dy \ge h- B x\\ &\; x= \hat x\\ & \;y\ge0 \\ & \;x\ge0 \end{split} \label{OP7} \end{equation}
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