The lower bound for the Traveling Salesman Problem

Question

When applying the B&B approach to the Traveling Salesman Problem, we want to minimize the distance (which may satisfy the triangle inequality) or the cost (which may not satisfy the triangle inequality). What is the efficient way to set the lower bound?

I saw from some online resources that we need to consider both the incoming and outgoing edges and their weights, which is either the distance or the cost. We can do a reduction on the weight matrix by subtracting the smallest numbers in each row, and subtracting the smallest numbers in each column, until there is a 0. But I don't quiet understand why is that. Is there other ways to set the lower bounds?

Answer 1

I find a different solution but it's easy to understand.

Because the tour is a cycle, each vertex in the tour should have an edge in and other edge out. Thus, the cost of each tour is greater or equal to half of the sum of the two edges of least cost adjacent to each vertex (since each edge is calculated twice).

So the lower bound:

1/2 Sum{(u₁,v), (u₂,v)}, where v in V, and (u₁,v), (u₂, v) are the two least cost edges adjacent to v.

Reference: https://web.archive.org/web/20160520165234/http://lcm.csa.iisc.ernet.in/dsa/node187.html

Comments

I like this bound.

Answer 2

read the book of algorithm, a question is the same