On a Linear-Programming, Combinatorial Approach to the Traveling-Salesman Problem

1 February 1959

journal article
Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research

Vol. 7 (1) , 58-66
https://doi.org/10.1287/opre.7.1.58

Abstract

This paper elaborates a method of attack on traveling-salesman problems, proposed by the authors in an earlier paper, in which linear programming is used to reduce the combinatorial magnitude of such problems. To illustrate the method, a step-by-step solution of Barachet's ten-city example is presented.

Keywords

DECISION THEORY
LINEAR PROGRAM
OPTIMIZATION
TRAVELING SALESMAN PROBLEM
LINEAR PROGRAMMING