From Wikipedia's Branch and Bound:
This step is called pruning, and is usually implemented by maintaining a global variable m (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 m can be discarded.
A simple solution to the Traveling Salesman Problem is to keep a variable, e.g. best, that represents the shortest Hamiltonian Circuit found so far (upper bound).
Every time we consider a new step in a potential new circuit, we compute the cost of the path at the current point, e.g. cost, which is a lower bound on the cost of this path, and compare it to the best variable. If at any point cost >= best, we need not consider this path; we may prune all potential paths that begin with this subpath.
This is not difficult to implement in a procedural language such as C where we can create a variable that is in the scope of the function. For example,
int best = -1; // no best path yet
node* solveTSP() {
// best can be consulted and has a consistent
// value across all recursive calls to solveTSP()
...
}
It is not clear to me how such an algorithm would be implemented purely functionally. Is there a way to simulate the global variable m mentioned in wikipedia's definition?
I know that it is simple to have a global variable in Lisp, but is this possible in a more purely-functional language such as Haskell?
You simply pass the current best value as an additional argument to recursive calls and also return the updated best value as the a part of their results. So if you have a function of type a -> b, it becomes something like a -> Int -> (b, Int). Instead of reading the global variable, you read the additional argument, and instead of writing it, you return a modified value when the function finishes.
This can be nicely expressed using the state monad. Type Int -> (b, Int) is isomorphic to State Int b, so our function of type a -> b becomes a -> State Int b.