branchandbound

Branch and bound is a general algorithm design paradigm for solving discrete and combinatorial optimization problems. It systematically explores a search tree of subproblems and uses bounding to prune parts that cannot yield better solutions than the current best.

The method starts with an initial feasible solution to establish a bound. For a minimization problem, this provides an upper bound on the optimal value; for a maximization problem, a lower bound. Each node represents a subproblem with some decision variables fixed. A bound for a subproblem is computed by a relaxation or other estimate of the best possible objective within that subproblem.

If the bound is worse than the current best, the subproblem is discarded. If it corresponds to a feasible, integral solution, it updates the current best. Otherwise, the subproblem is divided (branched) into smaller subproblems by fixing another decision variable. A scheduling of node exploration may be depth-first or best-first, with a priority queue.

Common variants include branch-and-cut, which combines cutting planes with branching to tighten relaxations; branch-and-price, which uses column generation for large-variable problems; and various branching rules to improve pruning efficiency.

Applications include integer programming, the traveling salesman problem, knapsack problems, and scheduling. The approach is problem-dependent; worst-case time is exponential, but effective pruning often yields practical performance.