Lesson 2

Relaxations are still useful. In a maximization problem, the LP relaxation gives an upper bound on what any integer solution in the same branch can achieve. In a minimization problem, it gives a lower bound. Branch-and-bound algorithms repeatedly solve such relaxations, discard branches whose bound is already worse than the best known integer solution, and branch on a variable that should be integral but currently has a fractional value.

The industrial solvers use many additional tricks. Valid inequalities tighten the relaxation. Clever branching chooses the next discrete decision. Heuristics quickly find good integer portfolios, which makes pruning stronger. The core combinatorial picture is simpler: the solver searches through discrete choices, and the bounds tell it which parts of the search space no longer deserve attention.