Browse Prior Art Database

Algorithm for Solving the Traveling Salesman and Other Problems

IP.com Disclosure Number: IPCOM000073794D
Original Publication Date: 1971-Feb-01
Included in the Prior Art Database: 2005-Feb-23
Document File: 3 page(s) / 24K

Publishing Venue

IBM

Related People

Held, M: AUTHOR [+2]

Abstract

This is an algorithm for the solution of the symmetric traveling-salesman problem which combines an ascent method and a branch and bound procedure. The ascent method itself is also applicable to a variety of other problems.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 55% of the total text.

Page 1 of 3

Algorithm for Solving the Traveling Salesman and Other Problems

This is an algorithm for the solution of the symmetric traveling-salesman problem which combines an ascent method and a branch and bound procedure. The ascent method itself is also applicable to a variety of other problems.

Central to this approach when applied to the traveling-salesman problem is the concept of a 1-tree which consists of a tree on the vertex set (2,3,..., n) together with two distinct edges at vertex 1. The transformation on "intercity distances" c(ij) -> c(ij) + Pi(i) + Pi(j) leaves the traveling-salesman problem invariant but changes the minimum 1-tree; also a tour is a 1-tree in which each vertex has degree 2. The analysis commences with the relationship:

(Image Omitted)

of a minimum tour with respect to (c(ij)); k is a generic index for 1-trees; c is the weight of the k-th 1-tree with respect to (c(ij)); and d(ik) is the degree of vertex i in the k-th 1-tree. Setting

(Image Omitted)

it is seen that C* >/- w(Pi); furthermore the best such lower bound on the solution of the traveling-salesman problem is given by max w(Pi).

An ascent method for computing or approximating max w(Pi) is presented. The method is iterative and computes a sequence Pi/m/ according to the formula (see orig. pg. 2499) where: for any k, k(Pi) is the index of a minimum-weight 1- tree at the point Pi, and t(m) is a sequence of appropriately chosen scalars.

The problem of finding max w(Pi) is really a special case of a far more general problem; finding the maximum of a function describable as the minimum of a large finite family of linear functions. Such problems can usually be derived whenever the Dantzig-Wolfe decomposition principle is applic...