next up previous contents
Next: Application to Manpower Planning Up: Lagrangian Relaxation Previous: Lagrangian Relaxation

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 tex2html_wrap_inline1451 associated with each node i.

  1. Begin with each tex2html_wrap_inline1313 at 0. Let the step size be some (problem dependent value) k.
  2. Set the cost of each edge (i,j) to tex2html_wrap_inline1461 .
  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 tex2html_wrap_inline1313 .
  4. For every node with degree more than 2 in the one tree, increase its tex2html_wrap_inline1313 by k; for those with degree 1, decrease its tex2html_wrap_inline1313 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.

Michael A. Trick
Mon Nov 11 15:16:52 EST 1996