Question

state the input and output of the traveling salesman problem. give the best lower bound on length of optimal tour and prove

Answer 1

Input − mask value for masking some cities, position.

Output minus; Find the shortest route to visit all the cities.

Input:

Cost matrix of the matrix.

0 20 42 25 30

20 0 30 34 15

42 30 0 10 10

25 34 10 0 25

30 15 10 25 0

Output:

Distance of Travelling Salesman: 80

A 1-tree problem on n cities is the problem of finding a tree that connects n cities with the first
city connecting to two cities.
When we try to find a lower bound for the 1-tree problem we try to find a minimum 1-tree. We
apply the 1-tree problem to the traveling salesman problem by considering that a tour is a tree
whose each vertex has a degree of two. Then a minimum 1-tree is also a minimal path.
Figure 10.7 shows a simple 1-tree.
1
Figure 10.7 A simple 1-tree.
Let us consider the geometric traveling salesman problem. We denote to eij the length of the path
from the i city to the j city. We assume that each city has a weight of πi. So we can say that each
edge has a cost of
cij = eij + πi πj 10.56
We now compute a new minimum 1-tree taking into account the edge costs. It is clear that the
new 1-tree we will construct id different from the original 1-tree. Let us consider a set of different
tours V. Let U be the set of 1-trees constructed by each tour from V. Recall that a tour is a 1-tree
with each vertex having a degree of 2. This means that the set of tours is included in the set of 1-
trees. Let us express a tour with T and the cost of a tour as L(cij , T) if we take in account the cost
of the edges. Therefore, it is true that
min LT∈U(cij, T) ≤ min LT∈V(cij, T) 10.57
From equation 3.17 we can write that:
L(cij , T) = L(eij , T) + ∑ π
=
n
i 1
idT
i 10.58
With dT
i we symbol the degree of i vertex in the 1-tree.
Consider T to be a tour. This means that dT
i = 2. So we can now write that:
L(cij , T) = L(eij , T) + ∑ π
=
n
i 1
i 2 10.59
We assume a minimal tour T’. Equation 3.18 is then transformed as:
min LT∈U(cij, T) ≤ min L(cij, T’) - ∑ π
=
n
i 1
i 2 10.60
Let us express the length of the optimal tour as c’ = L(eij , T’).Then from equation 10.59 and
10.60 we can get:
minT∈U{c + ∑ π
=
n
i 1
idT
i } ≤ c’ + ∑ π
=
n
i 1
i 2 10.61
This is transformed into:
minT∈U{c + ∑ π
=
n
i 1
i (dT
i -2)} ≤ c’ 10.62
We can finally write that:
w(π) = minT∈U{c + ∑ π
=
n
i 1
i (dT
i -2)} 10.63
Hence the lower bound for Held-Karp is
Held-Karplower-bound = max (w(π)).