Premium
A Simultaneous Enumeration Approach to the Traveling Salesman Problem
Author(s) -
Claus A.
Publication year - 1978
Publication title -
studies in applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 46
eISSN - 1467-9590
pISSN - 0022-2526
DOI - 10.1002/sapm1978582159
Subject(s) - travelling salesman problem , enumeration , integer programming , traveling purchaser problem , mathematical optimization , computer science , path (computing) , 2 opt , integer (computer science) , shortest path problem , bottleneck traveling salesman problem , linear programming , mathematics , theoretical computer science , discrete mathematics , graph , programming language
The solution procedure proposed in this paper uses certain principles of analog computers. The idea of using analog rather than digital computers to solve mathematical programming problems is not new—various methods have been proposed to solve linear programming, network flows, as well as shortest path problems (Dennis, 1959; Stern, 1965). These problems can be more efficiently solved with digital computers. To find a solution to the traveling salesman problem as well as other integer programming problems is difficult with existing hardware, especially if the number of variables is large. The question thus arises whether different hardware configurations make it possible to solve integer problems more efficiently. One such configuration is proposed below for the traveling salesman problem.