Question

Consider the following Integer Linear Programming (ILP) model
Maximize Z = X1 + 4X2
Subject to X1 + X2 < 7 // Resource 1
–X1 + 3X2 < 3 // Resource 2
X1, X2 > 0
X1, X2 are integer
i. Consider using the Branch and Bound (B & B) technique to solve the ILP model. With the
help of Tora software, draw the B & B tree. Always give priority for X1 in branching over
X2. Clearly label the constraint on each branch.
Branch and Bound (B & B) tree:

Answer 1

ANSWER:

(i)

Max Z = x1 + 4 x2

subject to

x1 + x2 ≤ 7 - x1 + 3 x2 ≤ 3

and x1,x2≥0;

Solution is
Max ZA=14.5 (x1=4.5,x2=2.5)

and ZL=12 (x1=4,x2=2) obtainted by the rounded off solution values.

The branch and bound diagram

Ax1=4.5,x2=2.5 ZA=14.5 ZL=12

n Sub-problem A, x1(=4.5) must be an integer value, so two new constraints are created, x1≤4 and x1≥5

Sub-problem B : Solution is found by adding x1≤4. Max Z = x1 + 4 x2 subject to x1 + x2 ≤ 7 - x1 + 3 x2 ≤ 3 x1 ≤ 4 and x1,x2≥0; Solution is Max ZB=13.3333 (x1=4,x2=2.3333) and ZL=12 (x1=4,x2=2) obtainted by the rounded off solution values.

Sub-problem C : Solution is found by adding x1≥5. Max Z = x1 + 4 x2 subject to x1 + x2 ≤ 7 - x1 + 3 x2 ≤ 3 x1 ≥ 5 and x1,x2≥0; Solution is Max ZC=13 (x1=5,x2=2) and ZL=13 (x1=5,x2=2) obtainted by the rounded off solution values. This Problem has integer solution, so no further branching is required.

The branch and bound diagram

Ax1=4.5,x2=2.5 ZA=14.5 ZL=12
x1≤4		x1≥5
Bx1=4,x2=2.3333 ZB=13.3333 ZL=12		Cx1=5,x2=2 ZC=13 ZL=13

------------------------------------

DEAR STUDENT,

IF YOU HAVE ANY QUERY ASK ME IN THE COMMENT BOX,I AM HERE TO HELPS YOU.PLEASE GIVE ME POSITIVE RATINGS

*****************THANK YOU***************