Optimization Online


Equivalence of an Approximate Linear Programming Bound with the Held-Karp Bound for the Traveling Salesman Problem

Alejandro Toriello (toriello***at***usc.edu)

Abstract: 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.

Keywords: traveling salesman problem, approximate linear program, integer program, lower bound technique

Category 1: Combinatorial Optimization

Category 2: Integer Programming

Category 3: Other Topics (Dynamic Programming )

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

Download: [PDF]

Entry Submitted: 02/07/2013
Entry Accepted: 02/08/2013
Entry Last Modified: 03/07/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society