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

x1
+
x2

Constraints

C1
x1
+
x2
C2
x1
+
x2
Discrete Optimization & Mixed Integer Programming

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)

Step 1: Continuous LP Relaxation

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).

Step 2: Integrality Check & Branching

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⌉).

Step 3: Subproblem Evaluation & Bounding

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*).

Step 4: Systematic Pruning (Fathoming)

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.

Maximize Z = 5x₁ + 8x₂
Constraint 1: x₁ + x₂ ≤ 6
Constraint 2: 5x₁ + 9x₂ ≤ 45
Non-negativity: x₁ ≥ 0, x₂ ≥ 0
Integer restriction: x₁, x₂ ∈ ℤ (both variables must be whole numbers)

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 NodeBranch ConstraintLP Relaxation PointObjective ZBranch & Bound Action
Node 1 (Root)LP Relaxation (no integer restrictions)x₁ = 2.25, x₂ = 3.75Z = 41.25Fractional x₁ = 2.25. Branch on x₁ ≤ 2 (Node 2) and x₁ ≥ 3 (Node 3).
Node 2Add constraint: x₁ ≤ 2 (from Root)x₁ = 2.00, x₂ = 35/9 ≈ 3.89Z = 370/9 ≈ 41.11Fractional x₂ ≈ 3.89. Branch on x₂ ≤ 3 (Node 4) and x₂ ≥ 4 (Node 5).
Node 4Node 2 + constraint: x₂ ≤ 3 (x₁ ≤ 2, x₂ ≤ 3)x₁ = 2, x₂ = 3Z = 34.00All integer! Initial incumbent established: Z* = 34 at (2, 3).
Node 5Node 2 + constraint: x₂ ≥ 4 (x₁ ≤ 2, x₂ ≥ 4)x₁ = 1.80, x₂ = 4.00Z = 41.00Fractional x₁ = 1.80 (Z = 41 > 34). Branch on x₁ ≤ 1 (Node 6) and x₁ ≥ 2 (Node 7).
Node 6Node 5 + constraint: x₁ ≤ 1 (x₁ ≤ 1, x₂ ≥ 4)x₁ = 1.00, x₂ = 40/9 ≈ 4.44Z = 365/9 ≈ 40.56Fractional x₂ ≈ 4.44 (Z ≈ 40.56 > 34). Branch on x₂ ≤ 4 (Node 8) and x₂ ≥ 5 (Node 9).
Node 8Node 6 + constraint: x₂ ≤ 4 (x₁ ≤ 1, x₂ = 4)x₁ = 1, x₂ = 4Z = 37.00All integer! Since 37 > 34, update incumbent: Z* = 37 at (1, 4).
Node 9Node 6 + constraint: x₂ ≥ 5 (5x₁ + 9(5) ≤ 45 ⇒ x₁ = 0)x₁ = 0, x₂ = 5Z = 40.00All integer! Since 40 > 37, update incumbent: Z* = 40 at (0, 5) (GLOBAL OPTIMUM).
Node 7Node 5 + constraint: x₁ ≥ 2 (x₁ ≥ 2, x₂ ≥ 4)No feasible solution (5(2)+9(4) = 46 > 45)InfeasiblePruned by Infeasibility.
Node 3Add constraint: x₁ ≥ 3 (from Root)x₁ = 3, x₂ = 3Z = 39.00All 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.