General Description
In order to facilitate a concrete description, we assume that the goal is to find the minimum value of a function, where ranges over some set of admissible or candidate solutions (the search space or feasible region). Note that one can find the maximum value of by finding the minimum of . (For example, could be the set of all possible trip schedules for a bus fleet, and could be the expected revenue for schedule .)
A branch-and-bound procedure requires two tools. The first one is a splitting procedure that, given a set of candidates, returns two or more smaller sets whose union covers . Note that the minimum of over is, where each is the minimum of within . This step is called branching, since its recursive application defines a tree structure (the search tree) whose nodes are the subsets of .
The second tool is a procedure that computes upper and lower bounds for the minimum value of within a given subset of . This step is called bounding.
The key idea of the BB algorithm is: if the lower bound for some tree node (set of candidates) is greater than the upper bound for some other node, then may be safely discarded from the search. This step is called pruning, and is usually implemented by maintaining a global variable (shared among all nodes of the tree) that records the minimum upper bound seen among all subregions examined so far. Any node whose lower bound is greater than can be discarded.
The recursion stops when the current candidate set is reduced to a single element, or when the upper bound for set matches the lower bound. Either way, any element of will be a minimum of the function within .
Read more about this topic: Branch And Bound
Famous quotes containing the words general and/or description:
“The general review of the past tends to satisfy me with my political life. No man, I suppose, ever came up to his ideal. The first half [of] my political life was first to resist the increase of slavery and secondly to destroy it.... The second half of my political life has been to rebuild, and to get rid of the despotic and corrupting tendencies and the animosities of the war, and other legacies of slavery.”
—Rutherford Birchard Hayes (1822–1893)
“The great object in life is Sensation—to feel that we exist, even though in pain; it is this “craving void” which drives us to gaming, to battle, to travel, to intemperate but keenly felt pursuits of every description whose principal attraction is the agitation inseparable from their accomplishment.”
—George Gordon Noel Byron (1788–1824)