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*.

- Begin with each at 0. Let the step size be some
(problem dependent value)
*k*. - Set the cost of each edge (
*i*,*j*) to . - 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 .
- 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*. - If
*m*iterations have passed since the best relaxation value has decreased, cut*k*in half. - 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.

Mon Nov 11 15:16:52 EST 1996