We consider two linear relaxations of the asymmetric traveling salesman problem (TSP), the Held-Karp relaxation of the TSP's arc-based formulation, and a particular approximate linear programming (ALP) relaxation obtained by restricting the dual of the TSP's shortest path formulation. We show that the two formulations produce equal lower bounds for the TSP's optimal cost regardless of cost structure; i.e. costs need not be non-negative, symmetric or metric. We then show how the ALP formulation can be modified to yield a relaxation for several TSP variants, and discuss how the formulations differ from arc-based relaxations.
Citation
Daniel J. Epstein Department of Industrial and Systems Engineering University of Southern California 3715 McClintock Avenue GER 240, Los Angeles, California 90089 February, 2013