7

General Description of Branch and Bound

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.

Practical Example: Traveling Salesman Problem

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()
    ...
}

My Actual Question

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?

rpax
  • 4,468
  • 7
  • 33
  • 57
danmcardle
  • 2,079
  • 2
  • 17
  • 25
  • 1
    This document contains a collection of programming exercises in the functional programming language Haskell. The exercises are all concerned with the infamous Travelling Salesman Problem (TSP for short), both its exact solution and heuristic approximations. http://www.cs.kent.ac.uk/pubs/2004/1923/index.html – dierre Mar 27 '13 at 00:10
  • Thank you for the link. While it is interesting, I can't find anything in this that pertains to branch and bound solutions to the TSP. – danmcardle Mar 27 '13 at 00:20

2 Answers2

5

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.

Petr
  • 62,528
  • 13
  • 153
  • 317
1

Computation with mutable state is no more powerful than computation without it. One can be reduced to the other.

In particular, a mutable cell in a functional viewpoint becomes a sequence of successive values, usually in some arrangement where new copies shadow older ones (for example, in tail recursion.)

phs
  • 10,687
  • 4
  • 58
  • 84