The concept of branch-and-bound algorithms is very general and should be known by every mathematician. It is likely that you already know a version of it. Suppose that we would like to minimize a real function ${f}$ defined on a set ${S}$. A branch-and-bound algorithm consists in two ingredients to compute ${\min_S f}$:
• branch: a branching procedure, which splits ${S}$ into a couple of disjoint subsets ${S=S_1\cup S_2}$. Applied recursively, it produces a tree structure
• bound: a bounding procedure, which computes an upper and lower bound for ${\min_{S_i} f}$. By navigating the tree, one can then discard some of the branches according to the bounds (we prune the tree).
Branch-and-bound algorithms are used for many complex optimization problems such as for the famous Traveling Salesman Problem. They are also used in the implementation of artificial intelligence in games such as chess (${(\alpha,\beta)}$-pruning).