Enumeration is Hopeless: The Size of the Integer Search Space

Why brute-force enumeration of integer feasible solutions fails on all but trivially small problems. We count the size of the integer search space for binary and bounded-integer variables, translate that count into wall-clock time at a given evaluation rate, and use these tools to see how quickly the budget collapses — motivating branch and bound.

Step 1 of 157%

Tutorial

Why We Cannot Just Enumerate

After relaxing an integer program to its LP, we can solve the relaxation efficiently — but the optimum is typically fractional. A naive way to recover the true integer optimum is to enumerate every integer point in the feasible box and pick the best. This strategy fails catastrophically: the number of integer points grows exponentially in the number of variables.

The cleanest illustration is the binary case. An integer program with $n$ variables, each taking value $0$ or $1$ , has

|\{0,1\}^n| = 2^n

candidate solutions. Even modest $n$ produces astronomical counts:

\begin{array}{c|c} n & 2^n \\ \hline 10 & 1{,}024 \\ 20 & 1{,}048{,}576 \\ 30 & \approx 1.07 \times 10^9 \\ 40 & \approx 1.10 \times 10^{12} \\ 60 & \approx 1.15 \times 10^{18} \end{array}

At $n=30$ we already have a billion candidates; at $n=60$ , $2^n$ exceeds the number of seconds since the Big Bang. This is the motivation for branch and bound: we must search the integer space without visiting every point.