1. Find solution using 0-1 Integer programming problem method
MAX Z = 300x1 + 90x2 + 400x3 + 150x4
subject to
35000x1 + 10000x2 + 25000x3 + 90000x4 <= 120000
4x1 + 2x2 + 7x3 + 3x4 <= 12
x1 + x2 <= 1
and x1,x2,x3,x4 >= 0

Solution:
To apply branch and bound method, the following 4 constraints have to be added to the LP model.
`x_1<=1`

`x_2<=1`

`x_3<=1`

`x_4<=1`

Solution steps by BigM method

Max `Z` `=` `` `300` `x_1` ` + ` `90` `x_2` ` + ` `400` `x_3` ` + ` `150` `x_4`

subject to

`` `35000` `x_1` ` + ` `10000` `x_2` ` + ` `25000` `x_3` ` + ` `90000` `x_4` ≤ `120000` `` `4` `x_1` ` + ` `2` `x_2` ` + ` `7` `x_3` ` + ` `3` `x_4` ≤ `12` `` `` `x_1` ` + ` `` `x_2` ≤ `1` `` `` `x_1` ≤ `1` `` `` `x_2` ≤ `1` `` `` `x_3` ≤ `1` `` `` `x_4` ≤ `1`

and `x_1,x_2,x_3,x_4 >= 0; `

Solution is
Max `Z_(A)=750` `(x_1=1,x_2=0,x_3=1,x_4=0.3333)`

and `Z_L=700` `(x_1=1,x_2=0,x_3=1,x_4=0)` obtainted by the rounded off solution values.

The branch and bound diagram

A `x_1=1,x_2=0,x_3=1,x_4=0.3333` `Z_A=750` `Z_L=700` Solution steps by BigM method

In Sub-problem A, `x_4(=0.3333)` must be an integer value, so two new constraints are created, `x_4=0` and `x_4=1`

Sub-problem B : Solution is found by adding `x_4=0`. Solution steps by BigM method Max `Z` `=` `` `300` `x_1` ` + ` `90` `x_2` ` + ` `400` `x_3` ` + ` `150` `x_4` subject to `` `35000` `x_1` ` + ` `10000` `x_2` ` + ` `25000` `x_3` ` + ` `90000` `x_4` ≤ `120000` `` `4` `x_1` ` + ` `2` `x_2` ` + ` `7` `x_3` ` + ` `3` `x_4` ≤ `12` `` `` `x_1` ` + ` `` `x_2` ≤ `1` `` `` `x_1` ≤ `1` `` `` `x_2` ≤ `1` `` `` `x_3` ≤ `1` `` `` `x_4` ≤ `1` `` `` `x_4` = `0` and `x_1,x_2,x_3,x_4 >= 0; ` Solution is Max `Z_(B)=700` `(x_1=1,x_2=0,x_3=1,x_4=0)` and `Z_L=700` `(x_1=1,x_2=0,x_3=1,x_4=0)` obtainted by the rounded off solution values. This Problem has integer solution, so no further branching is required.

Sub-problem C : Solution is found by adding `x_4=1`. Solution steps by BigM method Max `Z` `=` `` `300` `x_1` ` + ` `90` `x_2` ` + ` `400` `x_3` ` + ` `150` `x_4` subject to `` `35000` `x_1` ` + ` `10000` `x_2` ` + ` `25000` `x_3` ` + ` `90000` `x_4` ≤ `120000` `` `4` `x_1` ` + ` `2` `x_2` ` + ` `7` `x_3` ` + ` `3` `x_4` ≤ `12` `` `` `x_1` ` + ` `` `x_2` ≤ `1` `` `` `x_1` ≤ `1` `` `` `x_2` ≤ `1` `` `` `x_3` ≤ `1` `` `` `x_4` ≤ `1` `` `` `x_4` = `1` and `x_1,x_2,x_3,x_4 >= 0; ` Solution is Max `Z_(C)=595` `(x_1=0,x_2=0.5,x_3=1,x_4=1)` and `Z_L=550` `(x_1=0,x_2=0,x_3=1,x_4=1)` obtainted by the rounded off solution values. `Z_(C)=595 < Z_(B)=700`, so no further branching is required.

---

The branch and bound diagram

A `x_1=1,x_2=0,x_3=1,x_4=0.3333` `Z_A=750` `Z_L=700` Solution steps by BigM method
`x_4=0`		`x_4=1`
B `x_1=1,x_2=0,x_3=1,x_4=0` `Z_B=700` `Z_L=700` Solution steps by BigM method		C `x_1=0,x_2=0.5,x_3=1,x_4=1` `Z_C=595` `Z_L=550` Solution steps by BigM method

---

The 0-1 Integer programming problem algorithm thus terminated and the optimal integer solution is :
`Z_(B)=700` and `x_1=1,x_2=0,x_3=1,x_4=0`