mathematics//optimization//combinatorial optimization//branch and bound

Branch and bound is an exact search method for discrete optimization that splits the problem into smaller subproblems (branching) and discards every subproblem whose optimistic estimate is already worse than the best solution found so far (bounding); it is the core of integer programming solvers, and it gives the book's resource-to-target assignments their optimum in seconds or minutes for tens of agents. The search is a tree: the root is the whole problem, each branch fixes one more decision, and each leaf is a complete plan.

Branch and bound is an exact search method for discrete optimization that splits the problem into smaller subproblems (branching) and discards every subproblem whose optimistic estimate is already worse than the best solution found so far (bounding); it is the core of integer programming solvers, and it gives the book's resource-to-target assignments their optimum in seconds or minutes for tens of agents. The search is a tree: the root is the whole problem, each branch fixes one more decision, and each leaf is a complete plan.

Take ten fire-fighting drones and four fires, about a million ways to send them. Branching fixes drone 1 to fire A, or to B, and so on. For each partial plan a quick relaxation (letting the remaining drones be split fractionally, or ignoring how they interact) gives a lower bound on the expected loss any completion can reach. The best complete plan found so far, the incumbent, gives an upper bound. Whenever a partial plan's lower bound exceeds the incumbent, its whole subtree, perhaps a hundred thousand plans, is pruned without being looked at.

Branch and bound returns a certificate along with the plan. At any moment the gap between the incumbent and the best remaining lower bound says how far from optimal the current plan can be at most, so a search stopped by the clock still reports that its answer is within, say, 2 % of the optimum.

Its speed comes from two things: how tight the bounds are and how good the first incumbent is. Seeding the search with a greedy plan prunes large parts of the tree from the start; a loose relaxation prunes almost nothing and the search degenerates into enumeration. The worst case stays exponential, as NP-hardness predicts.

Modern integer linear programming solvers run branch and bound on the linear-programming relaxation and add cutting planes that tighten it (branch and cut), with heuristics that keep finding better incumbents. A* search is a close relative: its admissible heuristic plays the part of the bound, and it expands the most promising node first.

In a real-time system it runs with a time limit, and the greedy plan stays as the fallback if the deadline arrives before the first incumbent improves; that behaviour makes it an anytime algorithm with a proof attached.