Integer Programming Calculator (Branch & Bound Solver)
Solve discrete linear programming problems with integer constraints using the Branch and Bound tree search algorithm, tracking relaxed nodes and fathomed branches.
Problem Size
Objective
Objective Function — Maximize Z
Constraints
Integer Linear Programming & Branch and Bound: An Academic Guide
Understand how the Branch and Bound algorithm explores relaxation trees, prunes sub-optimal search branches, and guarantees exact integer optimums without heuristic rounding errors.
1. What Problem Does Integer Programming Solve?
Standard Linear Programming assumes decision variables are continuously divisible (real numbers). However, practical real-world operations require indivisible entities: workers assigned, aircraft scheduled, shipping containers dispatched, or boolean decisions (0-1). Integer Linear Programming (ILP) imposes the constraint that variables must belong to the set of integers (xⱼ ∈ ℤ). Because integer feasible spaces are disconnected lattice points rather than smooth convex polyhedrons, standard gradient pivots fail, necessitating systematic tree-search algorithms like Branch and Bound.
2. The Branch and Bound Algorithm (Dakin / Land-Doig)
Temporarily relax the integer requirement (allowing xⱼ ∈ ℝ) and solve the problem with standard Simplex. The continuous solution Z_LP establishes an absolute theoretical upper bound for maximization (or lower bound for minimization).
If all variables in the relaxation are integers, the solution is immediately optimal. If variable xₖ has fractional value v, branch the problem into two disjoint subproblems: Left Branch (xₖ ≤ ⌊v⌋) and Right Branch (xₖ ≥ ⌈v⌉).
Solve the continuous LP relaxation for newly created leaf nodes. Keep track of the 'incumbent'—the best valid all-integer solution found so far (with objective value Z*).
Prune (close) an active node without further branching if: (1) Infeasibility (no continuous solution exists), (2) Bound Domination (Z_node ≤ Z*), or (3) Integer Solution Achieved (update incumbent if Z_node > Z*).
3. Solved Academic Example: 2-Variable Integer Program
Observe why rounding continuous results fails and how the complete 9-node Branch & Bound tree converges to Z* = 40.
Why Naive Rounding Fails Disastrously
Solving the continuous LP relaxation yields the optimum at (x₁ = 2.25, x₂ = 3.75) with Z = 41.25. If a student naively rounds to nearest integers (2, 4), Constraint 2 yields 5(2) + 9(4) = 46 > 45 (Infeasible!). Rounding down to (2, 3) gives Z = 34, missing the true integer optimum by 6 units. Branch and Bound explores the discrete state space rigorously.
Complete Branch and Bound Search Tree Progression (DFS Traversal)
| Tree Node | Branch Constraint | LP Relaxation Point | Objective Z | Branch & Bound Action |
|---|---|---|---|---|
| Node 1 (Root) | LP Relaxation (no integer restrictions) | x₁ = 2.25, x₂ = 3.75 | Z = 41.25 | Fractional x₁ = 2.25. Branch on x₁ ≤ 2 (Node 2) and x₁ ≥ 3 (Node 3). |
| Node 2 | Add constraint: x₁ ≤ 2 (from Root) | x₁ = 2.00, x₂ = 35/9 ≈ 3.89 | Z = 370/9 ≈ 41.11 | Fractional x₂ ≈ 3.89. Branch on x₂ ≤ 3 (Node 4) and x₂ ≥ 4 (Node 5). |
| Node 4 | Node 2 + constraint: x₂ ≤ 3 (x₁ ≤ 2, x₂ ≤ 3) | x₁ = 2, x₂ = 3 | Z = 34.00 | All integer! Initial incumbent established: Z* = 34 at (2, 3). |
| Node 5 | Node 2 + constraint: x₂ ≥ 4 (x₁ ≤ 2, x₂ ≥ 4) | x₁ = 1.80, x₂ = 4.00 | Z = 41.00 | Fractional x₁ = 1.80 (Z = 41 > 34). Branch on x₁ ≤ 1 (Node 6) and x₁ ≥ 2 (Node 7). |
| Node 6 | Node 5 + constraint: x₁ ≤ 1 (x₁ ≤ 1, x₂ ≥ 4) | x₁ = 1.00, x₂ = 40/9 ≈ 4.44 | Z = 365/9 ≈ 40.56 | Fractional x₂ ≈ 4.44 (Z ≈ 40.56 > 34). Branch on x₂ ≤ 4 (Node 8) and x₂ ≥ 5 (Node 9). |
| Node 8 | Node 6 + constraint: x₂ ≤ 4 (x₁ ≤ 1, x₂ = 4) | x₁ = 1, x₂ = 4 | Z = 37.00 | All integer! Since 37 > 34, update incumbent: Z* = 37 at (1, 4). |
| Node 9 | Node 6 + constraint: x₂ ≥ 5 (5x₁ + 9(5) ≤ 45 ⇒ x₁ = 0) | x₁ = 0, x₂ = 5 | Z = 40.00 | All integer! Since 40 > 37, update incumbent: Z* = 40 at (0, 5) (GLOBAL OPTIMUM). |
| Node 7 | Node 5 + constraint: x₁ ≥ 2 (x₁ ≥ 2, x₂ ≥ 4) | No feasible solution (5(2)+9(4) = 46 > 45) | Infeasible | Pruned by Infeasibility. |
| Node 3 | Add constraint: x₁ ≥ 3 (from Root) | x₁ = 3, x₂ = 3 | Z = 39.00 | All integer, but Z = 39 ≤ Z* (40). Pruned by Bound Domination. |
Exact Integer Optimum Proved
All 9 search tree nodes fully explored or pruned. Global Integer Solution: x₁* = 0, x₂* = 5 with Maximum Z* = 40. (Identical to our Branch and Bound engine).
4. Common Student & Academic Pitfalls
Assuming the Integer Optimum Neighbors the Continuous Optimum
The true integer optimum can be geometrically distant from the continuous LP relaxation vertex. Always execute the tree search rather than testing nearby neighbors.
Failing to Prune Nodes When Dominated
Continuing to branch on a node whose upper bound is less than or equal to the best integer incumbent (Z ≤ Z*) wastes exponential iterations without finding better solutions.
Incorrect Constraint Formulation on Branches
Branches must be mutually exclusive and exhaustive over the integer gap: xₖ ≤ ⌊v⌋ and xₖ ≥ ⌈v⌉. Using strict inequalities (< or >) omits candidate integer points.