Traveling Salesman: how to use a lower bound?

Question

Let me preface this question by giving some helpful background material.

I'm trying to solve the traveling salesman problem using branch and bound. Concretely, for a partial solution, I'm using the solution the algorithm would attain by making greedy choices as an upper bound, and comparing this bound to the current best solution. If the bound attained using this heuristic is better than the cost of the best known solution, we continue exploring the partial solution. Otherwise, we prune and discard. Note that the greedy solution attained is always valid.

The above link mentions a method for finding a global lower bound. This is fairly intuitive: for each node, we add to the bound the sum of the two minimum cost edges to other nodes (representing the cheapest in/out edges, if you will) and divide by two to avoid double counting. The solution implied by this global bound is almost never a valid solution but instead gives a hard limit on the lowest cost we could ever hope to attain.

Here's how I'm currently trying to calculate a local lower bound (a lower bound for a partial solution) with cost $C(S)$.

• Set bound to the current accumulated cost, $C(S)$
• For each unvisited node, add to bound the sum of the two least cost edges, making sure that the edges selected don't lead to a node already visited
• return bound/2

Here's my question: How is the above solution different from the greedy bound? Maybe a better lower bound would be to add to bound the sum of the two least cost edges, paying no attention to whether these edges lead to nodes already visited. Also, how do I actually use this bound to prune the search space? Do I compare the local lower bound computed for a partial solution with the global lower bound, pruning if $L(S) < GL$ or if $L(S) > C(B)$, or if $L(S) > L(B)$? (here $GL$ corresponds to the global lower bound; $L(S)$ computes the local lower bound on a partial solution; $C(B)$ represents the trip cost on the best known solution; $L(B)$ is the lower bound on the best solution). Also, how will $L(S)$ ever be less than the global lower bound (i.e. an infeasible solution) if we only ever use (valid) edges to cities we haven't yet visited?

Comments and suggestions on using this lower bound as well as its efficacy would be very much appreciated. Thank you.

Answer 1

You want a bound that depends upon the partial choices made so far. So, I suggest you compute a bound that is based upon (1) the sum of the edges in the part you've chosen already, plus (2) a greedy bound for the remaining unvisited nodes (for each node, sum of the two least cost edges, divided by two); or something like this. This will be different from the greedy bound applied to the entire graph, because of part (1).