Integer Linear Programming (Branch and Bound Method)

University Examination Submission

Subject: Operations Research / Optimization Techniques
Topic: Integer Linear Programming (Branch and Bound Method)

1. Problem Statement

Maximize the objective function:

Subject to the constraints:

2. Step-by-Step Solution

Step 1: Solve the LP Relaxation (Node 0)

To begin the Branch and Bound method, we first ignore the integer restrictions and solve the problem as a standard continuous Linear Programming Problem (LPP). Assuming the constraints are binding at the optimal corner point:

1. 2. Substituting x_1 into the first equation:

Now, substituting x_2 back to find x_1:

Evaluating the objective function at this continuous optimum:

Initial Bounds Status:

• Upper Bound (U): 11.92 (Since no integer solution can exceed the continuous maximum)
• Lower Bound (L): -\infty (No feasible integer solution found yet)

Since both x_1 = 1.92 and x_2 = 2.69 are fractional, we must branch. We choose the variable with the largest fractional part, which is x_2 = 2.69.

Step 2: Branching Strategy

We create two mutually exclusive sub-problems by splitting the range of x_2 around its fractional value (2 < 2.69 < 3):

• Node 1: Add constraint x_2 \le 2
• Node 2: Add constraint x_2 \ge 3

Step 3: Evaluation of Node 1 (x_2 \le 2)

We introduce the constraint x_2 \le 2 to the original set of constraints. Let us evaluate the continuous LP relaxation boundary for this sub-problem to find its local upper bound:
If x_2 = 2, then:

• From Constraint 1: 6x_1 + 5(2) \le 25 \implies 6x_1 \le 15 \implies x_1 \le 2.5
• From Constraint 2: x_1 + 3(2) \le 10 \implies x_1 \le 4
  Thus, the optimal continuous solution for Node 1 occurs at (x_1, x_2) = (2.5, 2) with an objective value of:

Since x_1 = 2.5 is still fractional, we evaluate the neighborhood of feasible integer coordinates underneath this local upper bound:

x_1	x_2	Feasible to Coordinates?	Objective Value (Z = 2x_1 + 3x_2)
4	0	Yes	2(4) + 3(0) = 8
3	1	Yes	2(3) + 3(1) = 9
2	2	Yes	2(2) + 3(2) = 10
1	2	Yes	2(1) + 3(2) = 8
0	2	Yes	2(0) + 3(2) = 6
The best feasible integer solution found in this branch is (2,2) yielding Z = 10.

Step 4: Evaluation of Node 2 (x_2 \ge 3)

We introduce the constraint x_2 \ge 3 to the original set of constraints.
From Constraint 2:

If x_2 = 3, then:

Let's verify if the maximum possible integer value x_1 = 1 satisfies Constraint 1:

Evaluating this candidate integer node:

Let's check the alternative integer coordinate in this space (x_1 = 0, x_2 = 3):

The best integer solution in this branch is (1,3) yielding Z = 11.

Step 5: Node Comparison and Pruning (Fathoming) Analysis

We use the foundational rules of Branch and Bound to determine optimality:

1. Node 2 yields a completely integer-feasible solution of Z = 11. This updates our global Lower Bound (L) to 11. Node 2 is now fathomed by feasibility.
2. Node 1 yields a maximum possible integer solution of Z = 10.
3. Pruning Condition: Since the maximum potential value of Node 1 (Z = 10) is strictly less than our guaranteed global lower bound (L = 11), Node 1 can be safely pruned by bound (fathomed) because no further branching beneath it can ever beat our current best solution.

3. Branch and Bound State-Space Tree

                     [ Node 0 ]  
                   LP Relaxation  
              x₁ = 1.92, x₂ = 2.69  
                    Z = 11.92  
                        |  
             -------------------------  
             |                       |  
        (Branch: x₂ ≤ 2)        (Branch: x₂ ≥ 3)  
             |                       |  
         [ Node 1 ]              [ Node 2 ]  
        Max Integer:            Integer Feasible  
        x₁ = 2, x₂ = 2          x₁ = 1, x₂ = 3  
          Z = 10                  Z = 11  
             |                       |  
          FATHOMED                FATHOMED  
      (Pruned by Bound)     (Current Best/Optimal)  
  

4. Graphical Representation

                    x₂  
                    ↑  
  5 ──●──────────────────────────────  
      │\  
  4 ──│ \────────────────────────────  
      │  \  
3.33 ─●---\──────── Constraint 2 (x₁ + 3x₂ = 10)  
      │    \  
  3 ──│─────● (1,3) [Optimal Integer Solution: Z = 11]  
      │    ★ LP Optimum Node 0 (1.92, 2.69) [Z = 11.92]  
2.69 ─│────★─────────────────────────  
      │   /  
  2 ──│──●────● (2,2) [Node 1 Integer Peak: Z = 10]  
      │ /  
  1 ──│/  
      │  
  0 ──●──────────────────────●──────→ x₁  
     (0,0)                 (4.17,0)  
       
  Constraint 1 Line: 6x₁ + 5x₂ = 25  
  Constraint 2 Line: x₁ + 3x₂ = 10  
  

5. Final Analytical Summary

Branch / Node	Coordinates (x_1, x_2)	Solution Status	Objective Value (Z)
Node 0 (Root)	(1.92, 2.69)	Fractional LP Optimum	11.92
Node 1 (x_2 \le 2)	(2, 2)	Integer Feasible (Suboptimal)	10
Node 2 (x_2 \ge 3)	(1, 3)	Integer Feasible (Optimal)	11

6. Conclusion

Using the Branch and Bound execution rules for Integer Linear Programming, all branches have been successfully verified and fathomed. The unique, globally optimal integer solution is:
All explicit constraints, non-negativity parameters, and integer criteria (\mathbb{Z}) are fully satisfied.