Branch and Bound

Searches an IPP’s feasible integer solutions by treating the LP relaxation as a search tree, splitting (branching) a fractional solution into 2 stricter subproblems and discarding (bounding) subproblems that can’t beat the best integer solution found so far.

A subproblem is the IPP’s LP relaxation with extra ≤\le or ≥\ge bound constraints on individual variables, added by earlier branching steps. The search starts with 1 subproblem: the LP relaxation with no added bounds.

Steps

  • Solve the LP relaxation of the current subproblem.
  • If the solution is integral, it’s a candidate solution. Update the best solution found so far if it’s better.
  • If the subproblem’s relaxed objective value is worse than the best solution found so far, discard it (bound). The relaxation’s value is an upper bound (maximization) on any integer solution inside the subproblem, so none of them can beat the best solution either.
  • Otherwise, pick any variable xjx_j whose value kk in the relaxed solution isn’t an integer, e.g. xj=2.7x_j = 2.7. Branch on it: make 2 copies of the current subproblem, keep every constraint the same in both, then add xj≤⌊k⌋x_j \le \lfloor k \rfloor (here xj≤2x_j \le 2) to 1 copy and xj≥⌈k⌉x_j \ge \lceil k \rceil (here xj≥3x_j \ge 3) to the other. No integer lies strictly between ⌊k⌋\lfloor k \rfloor and ⌈k⌉\lceil k \rceil, so every integer point feasible in the parent subproblem stays feasible in 1 of the 2 children, just not xj=kx_j = k itself.
  • Repeat on each open subproblem until none remain.

The best solution found when the search ends is the IPP’s optimal solution. An infeasible subproblem (empty feasible region) is discarded without branching.

Worked Example

Maximize Z=2x1+3x2Z = 2x_1 + 3x_2 subject to x1+x2≤5x_1 + x_2 \le 5, 2x2≤72x_2 \le 7, x1,x2≥0x_1, x_2 \ge 0 and integer.

LP relaxation optimum: x1=1.5x_1 = 1.5, x2=3.5x_2 = 3.5, Z=13.5Z = 13.5.

  • Branch on x1x_1 into x1≤1x_1 \le 1 and x1≥2x_1 \ge 2.
  • x1≤1x_1 \le 1
    LP optimum (1,3.5)(1, 3.5), Z=12.5Z = 12.5. Branch on x2x_2 into x2≤3x_2 \le 3 and x2≥4x_2 \ge 4.
    • x2≤3x_2 \le 3
      LP optimum (1,3)(1, 3), integral, Z=11Z = 11. Best solution so far.
    • x2≥4x_2 \ge 4
      infeasible, since 2x2≤72x_2 \le 7 forces x2≤3.5x_2 \le 3.5. Discard.
  • x1≥2x_1 \ge 2
    LP optimum (2,3)(2, 3), integral, Z=13Z = 13. Better than the best solution so far. New best.
  • The x1≤1x_1 \le 1 branch’s bound (12.5) is below the best solution (13). No open subproblems remain.

Optimal solution: x1=2x_1 = 2, x2=3x_2 = 3, Z=13Z = 13.

Branch and bound search tree for the worked example The LP relaxation branches on x1 into x1 ≤ 1 and x1 ≥ 2. The x1 ≥ 2 branch is already integral and becomes the best solution. The x1 ≤ 1 branch branches again on x2, giving one integral but worse solution and one infeasible subproblem. x 1 ≤ 1 x 1 ≥ 2 x 2 ≤ 3 x 2 ≥ 4 LP relaxation x 1 = 1.5, x 2 = 3.5 Z = 13.5 x 1 = 1, x 2 = 3.5 Z = 12.5 fractional, branch again x 1 = 2, x 2 = 3 Z = 13 integral, best solution x 1 = 1, x 2 = 3 Z = 11 integral, beaten by 13 infeasible discarded

Wolfram Mathematica notebooks

A companion notebook for this note. Open it in Mathematica and evaluate the cells to reproduce the worked example.

The summary notebook defines every function used in this module, with documentation and no examples, as a starting point for your own problems.

Written by October 24, 2026 2 min read
Was this helpful?