Application to the TSP

We can use the method of lagrangian relaxation to strengthen some of our relaxations for the traveling salesman problem. For instance, we can formulate the TSP informally as:

Minimize Costs

Subject to

Exactly 2 edges at each node

Edges form a 1-tree

Now, we can relax the first type of constraints to get a problem like:

Minimize Costs + lagrangian penalties

Subject to

Edges form a 1-tree

We know how to solve the minimum 1-tree problem. We can solve the lagrangian relaxation as follows. There is a dual variable associated with each node i.

1. Begin with each at 0. Let the step size be some (problem dependent value) k.
2. Set the cost of each edge (i,j) to .
3. Solve the resulting minimum 1-tree problem. The lower bound on the traveling salesman solution is the 1-tree objective minus two times the sum of the .
4. For every node with degree more than 2 in the one tree, increase its by k; for those with degree 1, decrease its by k.
5. If m iterations have passed since the best relaxation value has decreased, cut k in half.
6. Go to 2.

This formulation, originally due to Held and Karp in the early 1970s provides a very strong relaxation to the traveling salesman problem.