2
$\begingroup$

I've been dealing with Benders Decomposition and I've been wondering, if I have an unbounded solution of the dual subproblem, is it possible to find out which constraint from the original problem is violated in that case?

Obviously with the unboundedness we are able to generate the extreme rays of the dual subproblem, but from those can we make any inferences to which original constraints these correspond?

$\endgroup$

1 Answer 1

1
$\begingroup$

I assume that by "violated" you mean "cannot be satisfied". It is not typically the case that a single constraint will be infeasible; rather, it is usually a subset of constraints that are collectively infeasible.

The components of an extreme ray of the dual correspond to primal constraints in the same way that components of the dual correspond to primal constraints. The subset of primal constraints matched with nonzero components of the dual ray is collectively infeasible (but not guaranteed to be the only infeasible subset, nor even necessarily the smallest one).

$\endgroup$
1
  • $\begingroup$ Thank you! That explanation helps a lot and I was actually able to debug my problem on the base of that. $\endgroup$ Dec 8, 2023 at 12:00

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.