Solution Using Branch and Bound Method

 

Integer Linear Programming (ILP) Solution Using Branch and Bound Method

Problem Statement

We need to solve the following Integer Linear Programming (ILP) problem:

Maximize:

$$Z=3x_1+4x_2$$

Subject to:

1. $7x_1+16x_2\le 52$

2. $3x_1-2x_2\le 9$

3. $x_1,x_2\ge 0$

4. $x_1,x_2$ must be integers.

---

Solution Using Branch and Bound Method

Step 1: Solve the Linear Relaxation (Ignore Integer Constraints)

First, we solve the problem as a standard Linear Program (LP) without integer constraints.

Graphical Approach

• Constraint 1: $7x_1+16x_2=52$

  • When $x_1=0$, $x_2=3.25$

  • When $x_2=0$, $x_1\approx 7.43$

• Constraint 2: $3x_1-2x_2=9$

  • When $x_1=0$, $x_2=-4.5$ (Not feasible since $x_2\ge 0$)

  • When $x_2=0$, $x_1=3$

Feasible Corner Points:

1. $(0,0)$ → $Z=0$

2. $(0,3.25)$ → $Z=13$

3. Intersection of Constraints:

   • Solving:

     $$\begin{gathered} 7x_1+16x_2=52 \\ 3x_1-2x_2=9 \end{gathered}$$

   • Solution: $x_1=4$, $x_2=1.5$ → $Z=18$

4. $(3,0)$ → $Z=9$

Optimal LP Solution:

$$(x_1,x_2)=(4,1.5),Z=18$$

Since $x_2=1.5$ is not integer, we proceed with Branch and Bound.

---

Step 2: Branching on $x_2$

We branch on the non-integer variable $x_2=1.5$, creating two subproblems:

1. Subproblem 1: $x_2\le 1$

2. Subproblem 2: $x_2\ge 2$

Subproblem 1 ($x_2\le 1$)

• New Constraints:

  • $7x_1+16x_2\le 52$

  • $3x_1-2x_2\le 9$

  • $x_2\le 1$

Solution:

• Intersection of $3x_1-2x_2=9$ and $x_2=1$:

  $$3x_1-2(1)=9⟹x_1=\frac{11}{3}\approx 3.666$$

• Optimal LP Solution: $(3.666,1)$, $Z=15.666$

Since $x_1$ is still non-integer, we branch further on $x_1$:

Branch $x_1\le 3$

• New Solution: $(3,1)$, $Z=13$

  • Feasible Integer Solution!

  • Current Best: $Z=13$

Branch $x_1\ge 4$

• New Solution: $(4,0.75)$ → $Z=15$

  • Still non-integer, but $Z=15>13$.

  • Further branching needed, but we prune since it cannot exceed $Z=18$.

Subproblem 2 ($x_2\ge 2$)

• New Constraints:

  • $7x_1+16x_2\le 52$

  • $3x_1-2x_2\le 9$

  • $x_2\ge 2$

Solution:

• Intersection of $7x_1+16x_2=52$ and $x_2=2$:

  $$7x_1+16(2)=52⟹x_1=\frac{20}{7}\approx 2.857$$

• Optimal LP Solution: $(2.857,2)$, $Z=16.571$

Since $x_1$ is non-integer, we branch further on $x_1$:

Branch $x_1\le 2$

• New Solution: $(2,2.375)$, $Z=15.5$

  • Still non-integer, but $Z=15.5>13$.

  • Further branching possible, but we prune since it cannot exceed $Z=18$.

Branch $x_1\ge 3$

• New Solution:

  • $(3,1.9375)$, $Z=15.75$

  • Still non-integer, but $Z=15.75>13$.

  • Prune since it cannot exceed $Z=18$.

---

Step 3: Compare All Feasible Integer Solutions

From the branching steps, the feasible integer solutions found are:

1. $(3,1)$ → $Z=13$

2. $(2,2)$ → $Z=14$ (Check feasibility: $7(2)+16(2)=46\le 52$, $3(2)-2(2)=2\le 9$)

Best Integer Solution:

$$(x_1,x_2)=(2,2),Z=14$$

---

Final Answer

The optimal integer solution is:

$$\boxed{{\displaystyle (x_1,x_2)=(2,2)\text{ with }Z=14}}$$

---