The Prize Collecting Traveling Salesman Problem.

Abstract

The following is a valid model for an important class of scheduling and routing problems. A salesman who travels between pairs of cities at a cost depending only on the pair, gets a prize in every city that he visits and pays a penalty to every city that he fails to visit, wishes to minimize his travel costs and penalties, while visiting enough to collect a prescribed amount of prize money. We call this problem the Prize Collecting Traveling Salesman Problem (PCTSP). This paper discusses structural, the convex hull of the solutions to the PCTSP. In particular, it identifies several families of facet defining inequalities for this polytope. Some of these inequalities are related to facets of the ordinary TS polytope, others to facets of the knapsack polytope. They can be used in algorithms for the PCTSP either as cutting planes or as ingredients of a Lagrangean optimum. Keywords: Traveling salesman problem; Facets; Polyhedral Combinations; Convex polytopes.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1987
Accession Number
ADA189418

Entities

People

  • Egon Balas

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Coefficients
  • Elimination
  • Equations
  • Heuristic Methods
  • Inequalities
  • Linear Programming
  • Mathematics
  • Military Research
  • Permutations
  • Rolling Mills
  • Scheduling (Production)
  • Sequences
  • Simplex Method
  • Structural Properties

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research