2
$\begingroup$

in the process of implementing my first BD algorithm, I am unsure how to proceed in the case that the subproblem is unbounded.

Obviously, it means you get an extreme ray that you can add to the RMP as a feasibility cut.

But do you also add an optimality cut in the same iteration, with the extreme point that the extreme ray is based on?

$\endgroup$

2 Answers 2

2
$\begingroup$

In each iteration of BD, you either add a feasibility cut or an optimality cut. That is due to the fact that the subproblem cannot be simultaneously feasible (and optimal) and infeasible (speaking in terms of the primal form of the subproblem).

$\endgroup$
3
  • $\begingroup$ I understand that. But let's say my dual subproblem is unbounded, thus I find a ray in the form of u1 + y*v1 with u1 being the origin of the ray and v1 the slope of the ray. Now, I can add a feasibility cut using v1. But I can also on top of that formulate an optimality cut using the origin of the ray, u1, no? $\endgroup$ Aug 18, 2023 at 9:15
  • 1
    $\begingroup$ Not sure if I understand your terminology, but how do you construct the optimality cut from u1? Also, please note that a feasibility cut is supposed to forbid the current solution to the master problem, while an optimality cut approximate the incurred cost by the subproblem due to taking the decision imposed by the master problem solution. I don't remember if we have a theory for this situation, but having both cuts added to the master problem should at best make the optimality cut redundant due to the presence of the feasibility cut, if not worsen the situation. $\endgroup$
    – Ehsan
    Aug 18, 2023 at 14:53
  • $\begingroup$ u1 is a feasible point in the dual solution space of the subproblem. Thus, I can add an optimality cut using that point. u1 is the anchor point of the extreme ray. Since v1 represents the slope of the extreme ray, it differs from u1. This procedure is also described in Nemhauser and Wolsey (1988, p. 414). $\endgroup$ Aug 23, 2023 at 9:10
1
$\begingroup$

The "anchor point" of the unbounded dual ray is a feasible solution to the dual subproblem. Optimality cuts are based on feasible solutions to the primal subproblem. If the dual is unbounded, then as Ehsan points out the primal is infeasible, meaning there is nothing on which to base the optimality cut.

$\endgroup$
4
  • $\begingroup$ Hi, sorry for the late response. The reason of my question was that in my lecture, when the dual subproblem was unbounded, we add the extreme ray to the MP via a feasibility cut. But we also used the "anchor point" of that extreme ray and added it to the set of extreme points that is used to construct the optimality cuts of the MP. (Thus, my probably incorrect terminology of adding both a feasibility and a optimality cut). Is that procedure wrong like this? $\endgroup$ Aug 23, 2023 at 9:07
  • $\begingroup$ Yes, you can take the last feasible dual solution obtained before detecting unboundedness and use it to construct a valid optimality cut. I'm not sure that cut will be very strong, though. I suppose it might prove useful in some cases. $\endgroup$
    – prubin
    Aug 23, 2023 at 15:25
  • $\begingroup$ By the way, your terminology is not incorrect. The confusion arose because people using BD typically only add optimality cuts as needed (meaning when confronted with a solution that is too good to be true). Adding cuts preemptively is uncommon but not wrong, and they would still be classified as optimality cuts. $\endgroup$
    – prubin
    Aug 23, 2023 at 15:32
  • $\begingroup$ Thank you for the explanations! I got it now. $\endgroup$ Aug 24, 2023 at 6:48

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.