Constrained and Integer Programming

You can't build 3.5 aircraft, hire 2.7 nurses, or route 1.4 trucks. A huge share of real decisions are whole-number ones — and demanding that variables be integers turns an easy problem shockingly hard. This is integer programming (IP): a linear program with the extra rule \mathbf{x} \in \mathbb{Z}^n. That one word, "integer", is the difference between a problem solved in milliseconds and one that can defeat the world's fastest computers.

Why so hard? A linear program has a smooth, convex feasible region and its optimum sits at a corner you can walk to. The integer feasible set is instead a scatter of isolated lattice points — no convexity, no gradient to follow, nothing to slide along. Checking them one by one explodes combinatorially: with n yes/no choices there are 2^n combinations. Integer programming is NP-hard — no known algorithm solves every instance in reasonable time.

The LP relaxation: a bound for free

The key move is to relax the hard constraint. Drop the integrality rule and solve the ordinary LP — the LP relaxation. Because it optimises over a larger feasible set (all real points, not just the lattice), its optimum is at least as good as the integer one. For a maximization, that means:

(\text{integer optimum}) \;\le\; (\text{LP relaxation optimum}).

So the relaxation hands you an upper bound at the cost of one easy LP solve — an estimate of the best you could possibly hope for. (This is duality's gift again: the dual of the relaxation certifies the bound.) The catch: the relaxation's answer is usually fractional, and you cannot simply round it — the rounded point is often infeasible, or feasible but not optimal.

The picture shows a small IP. The shaded polygon is the LP feasible region; the dots are the integer feasible points. The LP relaxation peaks at a fractional corner (ringed one colour); the true integer optimum is a different lattice point entirely (ringed another). The naive "round the LP answer" point is flagged — and it lands outside the region.

Branch and bound: divide, bound, prune

The workhorse algorithm, branch and bound, turns the relaxation bound into a full search that cleverly avoids examining most of the lattice. Take the problem \max\, 5x + 4y subject to 6x + 4y \le 24, x + 2y \le 6, with x, y \ge 0 integer.

Bound. Solve the LP relaxation: the optimum is (3, 1.5) with value 21. Fractional — so 21 is only an upper bound.
Branch. Pick the fractional variable y = 1.5 and split the problem into two that can't both include it: one with y \le 1, one with y \ge 2. No integer solution is lost — they all live in one branch or the other.
Recurse. The y \ge 2 branch gives the integer point (2, 2), value 18 — our first incumbent (best-so-far). The y \le 1 branch, solved and split again on x, yields (4, 0), value 20 — a new, better incumbent.
Prune. Whenever a branch's LP bound is no better than the incumbent, discard the whole subtree unexamined — it cannot contain a winner. This pruning is what saves branch and bound from checking all 2^n possibilities.

The search ends with the integer optimum (4, 0), value 20 — safely below the LP bound of 21, and reached without enumerating every lattice point. Modern solvers wrap this skeleton in extra "cutting planes" that shave fractional corners off the relaxation, but branch, bound, prune is the beating heart.

A startling number of famous puzzles are integer programs in disguise. Sudoku, the travelling salesman, airline crew scheduling, seating charts, even sports fixture lists — all become "choose these 0/1 variables to satisfy the rules". Because IP is NP-hard, this cuts both ways: it means one general solver can attack an enormous variety of problems, but also that a big enough instance may be genuinely intractable. The travelling salesman problem — visit every city once at least cost — is the poster child: trivial to state, and a benchmark that has driven decades of algorithmic ingenuity precisely because brute force (checking all n! tours) is hopeless past a few dozen cities.

Never just round the LP solution. Rounding a fractional LP optimum can land you outside the feasible region, or on a feasible-but-suboptimal point. The integer optimum can sit far from the LP vertex — you must search, not round.
The relaxation is a bound, not the answer. The LP relaxation's value is an upper bound (for a max IP); the true integer optimum is generally strictly worse. The gap between them is what branch and bound must close.
Integer programming is genuinely hard. Branch and bound prunes cleverly and solves many practical instances fast, but its worst case is still exponential. Adding "just one more integer variable" can turn a solvable model into an intractable one — there is no free lunch.