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?
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?