2
$\begingroup$

starting off with a MIP that I want to solve using Benders.

so in Benders Decomposition, you add feasibility cuts in the following form:

$v^j (b - Ax) \geq 0$

with $j \in J$ being the set of extreme rays of the dual solution space.

While trying to understand the theory behind Benders, I am struggling to understand where the $\geq 0$ comes from.

Why do I to add these constraints to the reformulated master problem?

$\endgroup$

1 Answer 1

3
$\begingroup$

In Benders, you pass a candidate solution to the master problem into an LP subproblem, where it affects the RHS of the LP constraints. That modified RHS is also the objective coefficient vector of the dual LP. Now suppose the master solution you passed in makes the primal subproblem infeasible. That will make the dual problem unbounded. (There are some edge cases where both primal and dual are infeasible, but I don't think they come up in Benders.) If your primal is maximizing (minimizing), your dual is minimizing (maximizing), and the dual being unbounded says there is an extreme dual ray along which the objective decreases (increases) forever.

For a master solution to be feasible, the primal LP must be feasible and the dual LP must be bounded. So you create a constraint that says the rate of change along that ray of the dual objective value computed from any valid master solution has to be nonnegative (nonpositive), and add that constraint to the master problem.

$\endgroup$
1
  • $\begingroup$ Thank you! That makes it much clearer for me. $\endgroup$ Aug 9, 2023 at 9:39

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.