# Great papers: The Traveling-Salesman Problem and Minimum Spanning Trees

I’ve decided to read and summarize one great paper a week from this list. This week’s paper is the 1970 paper The Traveling-Salesman Problem and Minimum Spanning Trees by Held and Karp.

Summary:

Held and Karp study 1-trees and their ability to provide lower bounds for the (symmetric) Traveling-Salesman Problem (TSP). Part of this paper’s importance stems from their use of Lagrangian Relaxation (LR) for solving an integer program (IP). In a 1979 survey paper on LR in Management Science, Fisher states that the “birth” of the Lagrangian approach as it exists today (i.e., 1979) occurred due to Held and Karp. Their success with TSP motivated others to consider LR for scheduling, location, covering, partitioning, and general integer programs.

Consider a simple undirected graph $G=(V,E)$ with vertex set $V=\{ 1, \dots, n\}$ and a cost function $c: E \to \mathbb{R}$. A 1-tree is a spanning tree of $G[V\setminus\{1\}]$ plus two edges incident to vertex 1. A minimum 1-tree is easy to compute; use any minimum spanning tree algorithm on $G[V\setminus\{1\}]$ and add two least cost edges incident to vertex 1. A TSP tour is a special kind of 1-tree–one in which each vertex has two incident edges. It is easy to see that a minimum 1-tree provides a lower bound on the TSP objective.

It turns out that for any real $n$-vector $\pi$, changing the edge costs from $c_{ij} \to c_{ij}+\pi_i + \pi_j$ leaves the TSP invariant, but it can change the minimum 1-tree. This $\pi$ vector is the Lagrangian multiplier for the degree-2 constraints arising in many TSP formulations. When $\pi$ is given, solving the LR is easy–the problem is exactly the problem of finding a minimum 1-tree. The problem then becomes, how does one find the best $\pi$–the vector that gives the best lower bound for TSP? Even if this can be answered easily, the lower bound from the best $\pi$ is not necessarily tight with the optimal IP objective.

Held and Karp define several problems that are equivalent to finding this best lower bound. One such problem is amenable to a column generation approach. In this problem, there is a binary variable $y_k$ for each 1-tree $k$ from the set $K$ of all 1-trees. The LP relaxation is then to minimize $\sum_{k \in K} c_k y_k$ such that $\sum_{k \in K} y_k =1$, $\sum_{k \in K} d^k_i y_k = 2~\forall i \in V$, and $y_k \ge 0~k\in K$. Here, $d^k_i$ is the degree of vertex $i$ in 1-tree $k$. As stated in their paper, this program seeks a minimum-weight ‘convex combination of 1-trees’ with average degree two. Since a graph can have many 1-trees, this program has many variables, hence the need for column generation. Fortunately the pricing problem for generating the next 1-tree to enter the basis is easy, as it is a minimum 1-tree problem.

Unfortunately convergence to an optimal solution was slow. So they considered an ascent method as well, only to conclude that the number of iterations required grew rapidly with n. Moreover, it has not yet been determined whether the ascent method always converges to a maximum point… They then propose a third approach–an ascent method embedded into a branch-and-bound algorithm.

They finish with a discussion relating minimal 1-trees and matroids (who doesn’t write about matroids in the 60s/70s???) and consider ‘other applications’. It is noted that a 1-arborescense for asymmetric TSP would play the same role as a 1-tree did for the symmetric case. They also consider (what seems to be) the vehicle routing problem, or as Held and Karp put it, a modified symmetric traveling-salesman problem in which cities 2,3,…,n are to be visited by p-salesmen, all based at city 1. In this case, one would use a $p$-tree (instead of a 1-tree), which consists of a $p$-component forest on vertices $2,3,\dots, n$ together with two incident edges from vertex 1 to each component of the forest.

I suppose there’s only one correct choice for next week…

Next up: M. Held and R. Karp, The Traveling-Salesman Problem and Minimum Spanning Trees: Part II, Mathematical Programming 1 (1971), 6.