4. Lower Bounds

In addition to good feasible tours one would like to have some
**guarantee on the quality** of the solutions found. Such a guarantee
can be given if a lower bound for the length of the shortest possible tour
is known. In general, lower bounds are obtained by solving **relaxations**
of the original problem in the sense that one optimizes over some set containing
all feasible solutions (tours) as a proper subset. Then the optimum solution of the
relaxed problem gives a valid lower bound for the value of the minimum solution
of the original problem. Different relaxations provide different lower bounds.
The main goal is to find relaxation problems for the TSP that can be solved efficiently
and which give lower bounds as tight as possible. Note that if the optimum solution
of the relaxed problem happens to be a valid tour, we have found the true optimum
of the original TSP. A detailled discussion of relaxations for lower bounds
can be found in [2].

We will discuss

- 1-tree Lagrangean relaxation 4.1
- assignment Lagrangean relaxation (in the near future)

4.1 1-Tree Lagrangean Relaxation

The 1-tree bound for the TSP is based on the following observation. If we select some node
of the problem, say node 1, then a tour consists of a special *spanning tree*
(namely a path) on the remaining *N*-1 nodes plus two edges connecting node 1 to this
spanning tree. Hence we obtain a relaxation of the TSP if we take as feasible solutions arbitrary
spanning trees on the node set
plus two additional edges incident to node 1.
Such a graph contains precisely one circle and is called *1-tree*. To get the optimum
1-tree we calculate the *minimum spanning tree* (MST) on the node set
,
which can be done in polynomial time unsing Prim's algorithm. Node 1 is then connected
to its nearest and second nearest neighbor on the MST.

The lower bounds provided by the 1-tree relaxation are rather poor, as can be seen using
the applet below. The bound can be improved considerably by fairly simple means. In a
tour exactly two edges are incident to each node, i.e. all nodes have degree
*d*_{i} = 2. If we associate with each node *i* some
weight
and use modified edge weights
then the
length of *every* tour is increased by
.
Hence the relative order
of the tours with respect to their length remain unchanged. If we compute lower bounds
using using the new weights and subtract
we obtain lower bounds for the
original problem. Therefore we can use the node weights to make nodes more or less attractive.

To improve the 1-tree bound, we can adjust the weights
to make those nodes with *d*_{i} = 1
more attractive and nodes with *d*_{i} > 2 less attractive. Then we calculate a new optimum
1-tree with respect to the adjusted weights. Its length is likely to be larger, providing a
tighter lower bound for our TSP. This procedure is then iterated until the length of
the 1-tree does not change significantly or if we find a optimum 1-tree with all nodes
of degree 2 (i.e. the true optimum tour). The scheme to adjust the the node weights
requires some care. Details can be found in [2].

In optimization theory, parameters like the
which allow to take account of the boundary
conditions (*d*_{i} = 2) as part of the cost function are called *Lagrange parameters*,
the corresponding relaxation is called *Lagrangean relaxation*.

Here's the applet. The algorithm starts with the optimum 1-tree (all weights *p*_{i}=0) and
proceeds by adjusting weights to enforce degree *d*_{i}=2 for all nodes. Nodes with degree
2 are colored blue, other nodes are green (*d*_{i} < 2) or yellow (*d*_{i} > 2). The iteration
stops if a tour is found (all *d*_{i} = 2). This tour is the optimum tour. The two special edges
that connect node 1 to the MST are colored red.