mathematics//optimization//combinatorial optimization

Combinatorial optimization is optimization over discrete choices (which robot takes which order, in what sequence to visit the sites, which sensors to install), where the candidates are finite but their number explodes with the size of the problem; it is the mathematics of dispatching, scheduling, routing and allocation in fleets, factories, warehouses and grids. Twenty robots and twenty orders already admit \(20!\approx2.4\cdot10^{18}\) one-to-one matchings, and checking a billion per second would take 77 years, so trying everything is out of the question from the start.

Combinatorial optimization is optimization over discrete choices (which robot takes which order, in what sequence to visit the sites, which sensors to install), where the candidates are finite but their number explodes with the size of the problem; it is the mathematics of dispatching, scheduling, routing and allocation in fleets, factories, warehouses and grids. Twenty robots and twenty orders already admit 20!≈2.4⋅101820!\approx2.4\cdot10^{18}20!≈2.4⋅1018 one-to-one matchings, and checking a billion per second would take 77 years, so trying everything is out of the question from the start.

All members of the family share that explosion and differ in whether some structure tames it. A few problems have it: the assignment problem is solved exactly in polynomial time despite its n!n!n! options, and so is the shortest path of graph search. Most do not, and are NP-hard: sending several agents to the same target (weapon-target assignment), routing vehicles, scheduling machines. For those there are two kinds of tool. The exact one writes the problem as an integer linear program and lets branch and bound search it while proving how far the best plan found is from the optimum. The fast one builds a plan with a heuristic such as a greedy algorithm and improves it by local search for as long as the clock allows; when the objective has diminishing returns (submodular), greedy even comes with a guaranteed fraction of the optimum.

NP-hard says only that no algorithm is known to guarantee the optimum in polynomial worst-case time, and in practice it means choosing among exactness, size and time. Real instances of tens or thousands of variables are often solved to proven optimality, while others of the same size never finish, so the honest method is to implement the simple rule, measure its gap to the optimum on cases you can solve exactly, and decide with that number.

Where it runs sets the budget. A fleet reassigns tasks every few seconds on a server, a factory plans tomorrow's production overnight, a grid operator commits generators for the next day; the same problem gets a heuristic in the first case and an exact solver in the last. An anytime algorithm fits the middle, with a valid plan at once and a better one each second.

The solvers are mature. OR-Tools (with its CP-SAT solver), HiGHS and SCIP are open, Gurobi and CPLEX commercial, and they handle models with millions of variables; the hard part is usually writing a formulation whose relaxation is tight.

Optimal for this cost matrix is not optimal for the system. Costs drift while robots move and drones fly, so a quick plan recomputed often with fresh data usually beats a perfect plan computed once from old data, which is the book's argument for the flyswatter rule.