# Branch and bound solution of problem

Not what you're looking for? Search our solutions OR ask your own Custom question.

Max z= 7x1+3x2

2x1+x2<=9

3x1+2x2<=13

x1,x2>=0

x1,x2 integer

https://brainmass.com/math/integrals/branch-bound-solution-problem-308707

#### Solution Preview

Branch and bound solution of problem

Max z= 7x1+3x2

2x1+x2<=9

3x1+2x2<=13

x1,x2>=0

x1,x2 integer

First solve the LP relaxation of the problem, which is the root.

(0) Max z= 7x1+3x2

2x1+x2<=9

3x1+2x2<=13

x1,x2>=0

The optimal solution is (x1, x2)=(13/3, 0) with objective value = 91/3. So 91/3=30.333 is the upper bound of the IP solution. It is not the optimal solution to IP because x1 is fractional.

So we branch on x1 =13/3=4.333 by creating two sub-problems. Sub-problem (1) is by adding x1<=4 to the root. Sub-problem (2) is by adding x1>=5 to the root. Remember that we cannot include the LP ...

#### Solution Summary

Branch and bound solution of problem is presented.

$2.49