Skip to content
Free public beta until December 4, 2026: every course is open, no card needed. After that, the first chapter of each course stays free and full access is a one-time $39 ($19 for up to 100 founding members chosen for helpful feedback). Your progress is kept. How the beta works

Recipe

Solve an integer program by branch and bound

Use when: an LP relaxation's optimal point is fractional, and rounding cannot be trusted

Goal: the certified true integer optimum, with every possibility either solved or provably ruled out

Taught in Branch and bound

Quick recipe

  1. Solve the relaxation
  2. Check for an integer solution
  3. Branch on a fractional variable
  4. Prune when the bound cannot win
  1. 1

    Solve the current subproblem's LP relaxation and record its optimal value as this subproblem's bound.

    Example

    Root: \max\ 5x_1+4x_2 s.t. 6x_1+4x_2\le24, x_1+2x_2\le6 gives (x_1,x_2)=(3,1.5), bound 21.

    Why: the relaxation's optimum is the best value ANY integer point down this branch could reach -- a valid ceiling, since the IP's own feasible set is a subset of the relaxation's.

  2. 2

    If every variable is already integer, this point is a candidate: compare it to the incumbent and keep the better one.

    Why: a feasible integer point is a genuine candidate answer the moment it's found -- no reason to branch on it further.

  3. 3

    Pick a fractional x_j; create two subproblems, x_j\le\lfloor x_j\rfloor and x_j\ge\lceil x_j\rceil.

    Example

    x_2=1.5 is fractional. Branch into x_2\le1 and x_2\ge2.

    • the relaxation is infeasible — this branch is dead, discard it with no bound to compare.
    • the relaxation is unbounded — the original IP itself is unbounded; stop entirely.

    Why: every integer value x_j could take is covered by exactly one of these two halves -- no integer point is lost, and none is double-counted.

  4. 4

    If a subproblem's bound is no better than the current incumbent, discard it without exploring further.

    ⚡ Shortcut

    Process the subproblem with the LARGEST bound first (best-bound order) -- it tends to find a strong incumbent early, which prunes everything else faster. Order never changes the final answer, only how much work it takes to get there.

    Why: the bound is the best that branch could EVER score -- if that best is already beaten, nothing inside the branch can change the outcome.

Common mistakes

  • Pruning a branch whose bound TIES the incumbent -- a tie still might hide an equally good alternate solution, but never a BETTER one, so pruning it loses nothing and is standard practice.
  • Branching on a variable that's already integer -- there's nothing fractional to split.
  • Forgetting to compare a fresh integer candidate against the CURRENT incumbent before moving on, letting a worse solution silently overwrite a better one.
  • Stopping the search before every open subproblem is resolved or pruned, and reporting an unproven candidate as final.