3
$\begingroup$

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

i want to solve it by benders decomposition method, if dual of sub problem be infeasible , What should i do? Is the algorithm terminated?

in benders decomposition suppose master problem is:

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

and sub problem is :

\begin{equation} \begin{split} \min &\; b^Ty \\ s.t.&\; Dy \ge h- Bx\\ & \;y\ge0 \end{split} \label{OP3} \end{equation}

we can write sub problem as (dual of sub problem):

\begin{equation} \begin{split} \max &\; \pi ^T (h- B x) \\ s.t.&\; \pi ^T D \le b\\ & \;\pi\ge0 \end{split} \label{OP8} \end{equation}

i think in this situation We can not continue the algorithm, is it correct?

$\endgroup$
2
$\begingroup$

You can always avoid the dual subproblem being infeasible by adding bounds to the primal variables (which, if you’re modeling something realistic, is always possible).

Suppose you have the LP

$$ \begin{array}{rl} \max\ & c^Tx \\ \text{s.t.}\ & Ax\leqslant{b} \end{array} $$

with corresponding dual

$$ \begin{array}{rl} \min\ & b^Ty \\ \text{s.t.}\ & y^TA=c^T\\ &y\geqslant0 \end{array} $$

Well, this dual may be infeasible. So what if we add some upper and lower bounds to the primal instead? Then

$$ \begin{array}{rl} \max\ & c^Tx \\ \text{s.t.}\ & Ax\leqslant{b}\\ & x\geqslant\ell \\ & x\leqslant{u} \end{array} $$

Then the dual problem is

$$ \begin{array}{rl} \min\ & b^Ty+u^Tz^+-\ell^Tz^- \\ \text{s.t.}\ & y^TA+(z^+-z^-)=c^T\\ &y\geqslant0\\ &z^\pm\geqslant0 \end{array} $$

This dual problem is guaranteed to be feasible. Do you see why?

$\endgroup$
  • $\begingroup$ How can I find these boundaries? $\endgroup$ – ken kavaza Jun 12 '18 at 3:29
  • 1
    $\begingroup$ It completely depends on the problem. For computation, it’s a bad idea to pick very large numbers without a good reason. You usually need to look at the thing you’re modeling and decide or calculate the bounds. $\endgroup$ – David M. Jun 12 '18 at 3:31
  • $\begingroup$ @ِ David M. ok , thanks . by $z^+ ,z^-$ dual problem always to be feasible because If we have a shortage, $z^+$ will be taken And if we have a surplus,$ z^-$ will count, right? $\endgroup$ – ken kavaza Jun 12 '18 at 3:37
  • $\begingroup$ That’s the idea, yes $\endgroup$ – David M. Jun 12 '18 at 3:38
  • $\begingroup$ @ David M thanks a lot , good time :-) $\endgroup$ – ken kavaza Jun 12 '18 at 3:39

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.