Thread: branch-and-bound tree for solving IPs

max z = 4x + 3y
4x + 9y <= 26
8x + 5y <= 17
x >= 0
y >= 0

I know you branch off the x or y with a decimal answer, but this gives LP relaxation: x=0.442 , y=2.692 , z=9.846 and I don't understand which one you're supposed to branch off... Thanks!

what do you mean? Branch and bound is the method you use to find the solution, you dont know how to do this is that the problem?

No sorry maybe I didn't describe it very well. We are allowed to use software to find the solution so for example another problem gave x=5, y=2.5, z=17.5 but we want integer solutions so we branched y<=2 and y>=3 to get 2 more solutions and you keep branching until you get an optimal integer solution. But in this problem solving it gave x=0.442, y=2.692, z=0.846 so I wasn't sure how you determine if you branch off x or y since they are both noninteger solutions. I tried both but I can't seem to get any integer solutions.

Originally Posted by jlt1209

No sorry maybe I didn't describe it very well. We are allowed to use software to find the solution so for example another problem gave x=5, y=2.5, z=17.5 but we want integer solutions so we branched y<=2 and y>=3 to get 2 more solutions and you keep branching until you get an optimal integer solution. But in this problem solving it gave x=0.442, y=2.692, z=0.846 so I wasn't sure how you determine if you branch off x or y since they are both noninteger solutions. I tried both but I can't seem to get any integer solutions.

Branching off either x or y should work. I.e., you could try either

x = 0 and x >=1

or

y <= 2 and y >= 3.

If you get no integer solutions then either your problem is infeasible-- there are no integers which satisfy the constraints-- or you made a mistake somewhere. In this problem clearly (0,0) is one feasible solution, so I suspect you made a mistake somewhere along the way.