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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\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
    Commented Apr 29, 2020 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$
    – Amin
    Commented May 3, 2020 at 10:31
3
$\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

Improve this answer
$\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$
    – Amin
    Commented May 3, 2020 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.