Integer Linear Programming (ILP) 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 \leq 52 \)
2. \( 3x_1 - 2x_2 \leq 9 \)
3. \( x_1, x_2 \geq 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 \geq 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:
   \( 7x_1 + 16x_2 = 52 \)
   \( 3x_1 - 2x_2 = 9 \)
   - 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), \quad 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 \leq 1 \)
2. Subproblem 2: \( x_2 \geq 2 \)

Subproblem 1 (\( x_2 \leq 1 \))

• New Constraints:
  - \( 7x_1 + 16x_2 \leq 52 \)
  - \( 3x_1 - 2x_2 \leq 9 \)
  - \( x_2 \leq 1 \)

Solution:
- Intersection of \( 3x_1 - 2x_2 = 9 \) and \( x_2 = 1 \):
\( 3x_1 - 2(1) = 9 \implies 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 \leq 3 \)

• New Solution: \( (3, 1) \), \( Z = 13 \)
  - Feasible Integer Solution!
  - Current Best: \( Z = 13 \)

Branch \( x_1 \geq 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 \geq 2 \))

• New Constraints:
  - \( 7x_1 + 16x_2 \leq 52 \)
  - \( 3x_1 - 2x_2 \leq 9 \)
  - \( x_2 \geq 2 \)

Solution:
- Intersection of \( 7x_1 + 16x_2 = 52 \) and \( x_2 = 2 \):
\( 7x_1 + 16(2) = 52 \implies 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 \leq 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 \geq 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 \leq 52 \), \( 3(2) - 2(2) = 2 \leq 9 \))

Best Integer Solution:
\( (x_1, x_2) = (2, 2), \quad Z = 14 \)

Final Answer

The optimal integer solution is:

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