How do you search a space too big to search?
Integer programming (topic 04) is where the corner theorem stops being enough, and branch and bound (05) is the machinery that copes. Topic 19 shares this course's language of variables and constraints but drops the objective: sometimes the honest question is not “what's best” but “does anything work at all.” Topic 21 asks when the simplest rule of thumb is provably good enough, and topic 10 is what you reach for once exact methods die.
You cannot enumerate. A 60-item yes/no problem has 2⁶⁰ ≈ 1.15 × 10¹⁸ combinations (roughly two and a half times the number of seconds that have elapsed since the Big Bang) and no computer will ever be fast enough to visit them one at a time. So the trick is to stop trying.
Branching splits the problem: either we take this item or we don't, and each branch is a smaller problem of the same shape. That alone buys nothing. It is just enumeration drawn as a tree.
Bounding is where everything happens. Before opening a branch, ask a deliberately easier question, what if I could take fractions of things?, and solve that instead. The easy answer is optimistic by construction, because you relaxed a restriction. So if even the optimistic figure cannot beat an answer you already hold, everything below that branch is provably worthless and you delete it unopened. Not "probably worthless". Provably.
Two things surprise people. The best opening move is not to explore the most promising branch. It is to grab any decent answer fast, because a strong answer in hand is what makes everything else prunable. And a cut near the top of the tree is worth exponentially more than one near the bottom, so the satisfying-looking work down among the leaves is nearly worthless.
Maintain an incumbent z* (the best feasible objective found so far) and a list of unexplored subproblems. For each subproblem P, compute a bound U(P) ≥ max{cᵀx : x feasible in P}. Then:
if U(P) ≤ z* discard P entirely (fathom by bound)
if P is infeasible discard P (fathom by infeasibility)
if U(P) attained by an integral x z* ← max(z*, cᵀx)
otherwise split P and repeat (branch)
Correctness rests on one line: U(P) is an upper bound on everything in P, so U(P) ≤ z* means nothing in P beats what you already have. Any valid bounding function works; better bounds simply prune more.
For the 0/1 knapsack the standard choice is the Dantzig bound: sort by value per unit weight, fill greedily, and allow a fraction of the last item. Because the fractional problem is a relaxation, its optimum dominates the integral one.
The general machinery is Land & Doig (1960). Modern solvers add cutting planes: extra valid inequalities that shave fractional vertices off the relaxation without removing any integer point, and the combination, branch and cut, is what runs inside the major commercial and open-source solvers.
Note the asymmetry that makes this honest: branch and bound terminates with a proof. When the list empties, the incumbent is optimal and you can say so. That is a stronger output than any heuristic can offer, and it is what "solved" means in this field.
Everywhere, invisibly Branch and bound is the engine under essentially every commercial optimisation solver, and therefore under vehicle routing, production scheduling, sports-league fixture generation, portfolio selection with cardinality limits, and gate assignment at airports. The reason those problems became solvable is largely this algorithm getting better at proving things absent: reported solver speedups over the last three decades come substantially from improved cuts, bounds and presolve rather than from hardware alone.
Check yourself
A branch of the search has an optimistic bound of 348, and you already hold a solution worth 355. What do you do with that branch?
A bound is an upper limit on everything below the branch, so a bound under the incumbent proves the whole branch worthless. That one comparison removed half the search space.