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 $\{2,\ldots,N\}$ 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 $\{2,\ldots,N\}$, 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 $\pi_i$ and use modified edge weights $d_{ij}' = d_{ij}+\pi_i+\pi_j$ then the length of every tour is increased by $2\cdot\sum_i\pi_i$. 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 $2\cdot\sum_i\pi_i$ 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 $\pi_i$ 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 $\pi_i$ requires some care. Details can be found in [2].

In optimization theory, parameters like the $\pi_i$ 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.

Sorry, your browser is not enabled to execute a Java applet.