Branch and Bound Methods for the Traveling Salesman Problem

Abstract

This paper reviews the state of the art in enumerative solution methods for the traveling salesman problem (TSP). The introduction (Section 1) discusses the main ingredients of branch and bound methods for the TSP. Sections 2, 3 and 4 discuss classes of methods based on three different relaxations of the TSP: the assignment problem with the TSP cost function, the 1-tree problem with a Lagrangian objective function, and the assignment problem with a Lagrangean objective function. Section 5 briefly reviews some other relaxations of the TSP, while Section 6 discusses the performance of some state of the art computer codes. Besides material from the literature, the paper also includes the results and statistical analysis of some computational experiments designed for the purposes of this review.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1983
Accession Number
ADA126957

Entities

People

  • Egon Balas
  • Paolo Toth

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Cyber
  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Computer Programming
  • Computers
  • Dynamic Programming
  • Exponential Functions
  • Integer Programming
  • Linear Programming
  • Literature
  • Mathematical Programming
  • Mathematics
  • Operations Research
  • Optimization
  • Simplex Method
  • Standards
  • Statistical Analysis
  • Trees (Data Structures)

Readers

  • Environmental Remediation and Restoration.
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Graph Algorithms and Convex Optimization.