0
$\begingroup$

If I need to find the integer valued solution to Linear programming problem using branch and bound method, but the non integer x value at the last iteration is less than 1, let's say 3/4. Then I have one constrain $x_1 \le 0$ and $x_1 \ge 1$. How do I proceed with the first case, when $x_1 \le 0$? I cannot add another constrain with auxiliary variable $x_1 + s_1 \le 0$, because all $x_i \ge 0$. Can I simply assume that $x_1 = 0$ and do the linear programming problem ignoring the $x_1$ variable?

$\endgroup$
1
  • $\begingroup$ It´s better to post the whole problem and not only a part of it. $\endgroup$ Mar 4 at 16:07
1
$\begingroup$

If you started with nonnegative constraint and you branch on $x_1 \le 0$ and $x_1 \ge 1$, under that branch of $$x_1 \le 0$$ and $$x_1 \ge 0,$$ you can indeed conclude that $$x_1=0.$$

The value indeed has been fixed for that branch.

$\endgroup$

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.