I am implementing a Benders Decomposition on a large MILP, where the objective is to minimize the cost associated with the integer variables. As a result, my Benders subproblem is only a feasibility problem. This is not an issue since the dual will have an objective and I can use Benders to make feasibility cuts. However, I am not sure whether the subproblem dual should be a minimization or maximization problem. What clue should I look for that will tell me the optimization direction?
asked
leruckle |

If I understand you correctly, you have a problem of the form \[ \begin{align} \min \ & cx + 0f\\ s.t.:\ & Ax + Bf = b\\ \ & x\in \mathcal{X}\cap\{0,1\}\\ \ & f \in\mathcal{F} \end{align} \] From here you should just continue as usually. If \(\bar{x}\) is a solution to the integers variables then the subproblem becomes \[ \begin{align} c\bar{x}+\min \ & 0f\\ \ &Bf=b-A\bar{x}\\ \ &f\in\mathcal{F} \end{align}\]
answered
Sune |