Traveling Salesman: how to use a lower bound?
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).