Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 38 ยท Integer Programming

Branch and Bound

Understand branch and bound step by step: LP relaxations, branching on fractional variables, pruning by bound, node selection, and a from-scratch Python implementation.

Branch and bound (B&B) is the algorithm at the heart of every MILP solver. The idea is divide and conquer, guided by LP bounds: split the problem into smaller subproblems (branch), solve the LP relaxation of each (bound), and throw away any subproblem that cannot contain a better answer (prune).

You already know the ingredients. The LP relaxation of an integer program gives an optimistic bound (Integer Programming Basics). If the relaxation solution has a fractional variable, say x = 2.4, any integer solution must have either x <= 2 or x >= 3. Those two statements cover all integer points, so you create two child problems, one for each.

The algorithm

For a maximization problem:

  1. Keep a best known integer solution (the incumbent), initially none with value -inf.
  2. Pick an open node and solve its LP relaxation.
  3. If the LP is infeasible, prune (nothing is here).
  4. If the LP value is no better than the incumbent, prune by bound.
  5. If the LP solution is integer, it becomes the new incumbent; prune (we found a solution).
  6. Otherwise choose a fractional variable x_j = f, create children with x_j <= floor(f) and x_j >= ceil(f), and add both to the open list.
  7. Stop when the list is empty. The incumbent is optimal.
flowchart TD
    R["Root LP<br/>x=3, y=1.5<br/>bound 21"] -->|"y <= 1"| A["LP: x=3.33, y=1<br/>bound 20.67"]
    R -->|"y >= 2"| B["LP: x=2, y=2<br/>bound 18"]
    A -->|"x <= 3"| C["x=3, y=1<br/>value 19 integer"]
    A -->|"x >= 4"| D["x=4, y=0<br/>value 20 integer"]
    B --> E["integer, value 18<br/>pruned by bound"]

A small search tree: leaves are integer solutions or are pruned because their bound is below the incumbent.

A complete implementation

The code below keeps a stack of nodes (each is a list of variable bounds), solves each LP with linprog, and records what happened. It is written for clarity, not speed.

Python Branch and bound from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the printed log from top to bottom: the root relaxation is fractional, the algorithm dives left, finds integer solutions, and uses their value to prune later nodes. The result matches SciPy's solver.

Why pruning is so powerful

Without pruning you would enumerate every integer point. With a good incumbent and tight bounds, entire subtrees vanish. The quality of the bound, which comes from the formulation, determines how big the tree grows. Compare by counting nodes on a tougher knapsack-like problem with and without bound pruning.

Python How much does pruning save?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both searches find the same optimum, but the pruned search visits roughly a tenth of the nodes (183 against 1,673 in this run).

Choices that change the tree

  • Branching variable. Common rules: the most fractional variable (closest to .5), or strong branching, which tries a few candidates and picks the one with the biggest bound improvement. Modern solvers also use pseudo-costs learned during the search.
  • Node selection.
    • Depth first uses little memory and finds incumbents quickly.
    • Best bound first always expands the node with the best LP value, minimizing the nodes needed to prove optimality.
    • Solvers mix both: dive to get incumbents, then switch to best-bound.
  • Bounding by heuristics. Rounding and "diving" heuristics produce good incumbents early; the better the incumbent, the more pruning.
  • Presolve. Before branching, solvers tighten bounds, remove redundant rows and fix variables.

Branch and cut

Branch and cut adds cutting planes at nodes (see Cutting Planes and Formulation Strength): extra valid inequalities that cut off fractional LP points without removing any integer solution. This tightens each node's bound and shrinks the tree. HiGHS, Gurobi, CPLEX and CBC are all branch-and-cut solvers.

Complexity warning

In the worst case, B&B examines exponentially many nodes (2^n for n binary variables). That is unavoidable in general because integer programming is NP-hard. In practice, structure and good formulations let solvers handle models with many thousands of variables, but it can also fail on small hard instances. When a solve takes too long:

  1. Check formulation strength (tighten big-M, add valid inequalities).
  2. Provide a good starting solution.
  3. Set a time limit and an acceptable gap (for example 1%).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A node's LP relaxation (maximization) has value 17.5 and the incumbent is 18. What happens?

    No integer solution below this node can exceed its LP value 17.5, which is worse than the incumbent, so the subtree cannot help.
  2. 2. If the LP optimum has x = 2.4, which pair of children is created?

    Every integer value satisfies x <= 2 or x >= 3, and the fractional point 2.4 satisfies neither child.
  3. 3. What does depth-first node selection mainly give you?

    Diving finds feasible integer solutions early, which makes later pruning stronger, and the open list stays small.
  4. 4. Why does a tighter formulation help branch and bound?

    Pruning depends on bounds. A relaxation closer to the true integer optimum cuts off subtrees sooner.

Summary

  • Branch and bound splits a problem on a fractional variable and bounds each part with its LP relaxation.
  • A node is pruned when it is infeasible, integer, or has a bound no better than the incumbent.
  • Bound quality (formulation) controls tree size; node selection and branching rules affect speed.
  • Branch and cut adds valid inequalities during the search; production solvers rely on it.
  • B&B is exponential in the worst case, so use time limits, gaps and good formulations.

Next: Cutting Planes and Formulation Strength