2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.