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.