6
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ – Ryan Cory-Wright Apr 29 '20 at 23:47
  • $\begingroup$ 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. $\endgroup$ – Katatonia May 3 '20 at 10:31
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Katatonia May 3 '20 at 10:33

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.