branch and bound

An exact method for discrete and global optimization that alternates two operations: branching, which divides the solution space into subproblems, and bounding, which computes for each subproblem a limit on the best objective value it could contain — typically by solving a relaxation, such as dropping integrality constraints — so that any subproblem whose bound cannot improve on the incumbent (the best complete solution yet found) is pruned. The search tree may be explored depth-first, best-first or in hybrid orders, and the method ends with a proof of optimality, or earlier with a guaranteed gap between incumbent and bound. Strengthened by cutting planes (branch and cut), it is the engine of mixed-integer programming solvers used in scheduling, logistics and energy planning; it also drives exact traveling-salesmantraveling salesman problem, n.: The puzzle of planning a round trip through a list of cities that stops at each one once and covers the least distance. It is easy to state, but the number of possible routes explodes as cities are added. and constraint-optimizationconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes. solvers and the formal verificationformal verification, n.: Using mathematics, not just testing, to prove that a computer system always behaves as specified — for example, that a chip never adds wrongly or that a program can never crash in a particular way. of neural networksneural network, n.: A kind of computer program that learns a task from examples by tuning thousands to billions of connections between simple number-crunching units, an arrangement loosely inspired by nerve cells in the brain., and machine learning is increasingly used to make its branching decisions.