An Exact Two-Matching Based Branch and Bound Algorithm for the Symmetric Traveling Salesman Problem

Abstract

An algorithm is described for the symmetric traveling salesman problem (TSP) based on a bipartite two-matching lower bounding technique. The lower bound is strengthened by using the bipartite two-matching as the basis for a heuristic algorithm for the dual of integer two-matching. We use this dual as a lower bound for the symmetric traveling salesman problem in a branch and bound algorithm. Results are presented for random symmetric TSPs with up to 3000 cities. On Euclidean problems the two-matching bound is weaker than on random problems and algorithm performance deteriorates as a result. The algorithm successfully solves 11 of 15 Euclidean problems from the literature with sizes ranging from 17 to 99 cities.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1991
Accession Number
ADA237878

Entities

People

  • D. L. Miller
  • Gerald L. Thompson
  • J. F. Pekny

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Chemical Engineering
  • Computer Networks
  • Computers
  • Elimination
  • Engineering
  • Equations
  • Integer Programming
  • Integrals
  • Linear Programming
  • Literature
  • Mathematics
  • Military Research
  • Networks
  • Schools
  • Sparse Matrix
  • Universities

Fields of Study

  • Computer science

Readers

  • Operations Research