6

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

Amin
  • 2,150
  • 7
  • 20

2 Answers2

3

For classical Benders decomposition, where the integer variables appear in the master and the continuous variables appear in the subproblem, you can use the LP subproblem duals to generate the optimality and feasibility cuts. In that case, you can treat the big-M constraints like any other subproblem constraints.

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.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • 1
    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. – Ryan Cory-Wright 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. – Amin May 03 '20 at 10:31
3

The following paper discusses this sort of constraint: Codato, G. & Fischetti, M. (2006) "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming". Operations Research, 54, 756-766

prubin
  • 39,078
  • 3
  • 37
  • 104
  • Thank you so much. I used the cuts defined by A nested benders decomposition approach for telecommunication network planning,Joe Naoum‐Sawaya Samir Elhedhli, but its convergence speed is so slow. – Amin May 03 '20 at 10:33