# How to handle bigM in sub-problem of benders decomposition?

Suppose you want to solve a MIP with Benders decomposition and the binary variables ($$y_i$$) are fixed in the master problem but these variables are used in the sub-problem with bigM like $$x_{ij} \le M.y_i \quad \lambda_{ij}$$ where $$\lambda_{ij}$$ is the dual variable of these constraints. What is the best way to define dual problem and generate optimality and feasibility cuts? If $$y_i=0$$, then $$x_{ij}=0$$, while if $$y_i=1$$, the constraint $$x_{ij} \le M.y_i$$ will be redundant.

Thanks

An alternative approach to avoid explicit big-M constraints in the subproblem is to use combinatorial (or logic-based) Benders decomposition in which the feasibility cuts are "no-good" cuts of the form $$\sum_{i\in S} y_i \le |S|-1$$. If you require optimality cuts (because the original objective involves $$x_{i,j}$$), they become big-M constraints in the master problem.
• It's also worth noting that by comp slackness if the constraint $x_{i,j} \leq M y_i$ is not binding then the corresponding dual variable is $0$ and shouldn't be included in the subproblem. Apr 29 '20 at 23:47
• Right now, most of constraints are in form of $x_{ij} < y_{i}$ and based on complementary slackness the dual variable will be zero and new cut just include a few variables in master problem. May 3 '20 at 10:31