Site Map Guestbook News Support Download / Purchase Efficiency Testlab About

Traveling Salesman Problem
Company
Feedback
PCGrates
PCGrate-S(X) Series
PCGrates Screenshots
PCGrates Examples
Our Customers
NP-Complete Problems
Traveling Salesman Problem
Hamiltonian Cycle Problem
NP-Complete Problems Screenshots
NP-Complete Problems Examples
References
According to Cook's theorem (Cook, S.A. The complexity of theorem-proving procedures, Proc. 3rd Ann. ACM Symp. on Theory of Computing machinery, New York, 151-158 (1.5; 2.6; 3.1.1; 5.2; A1.4; A9.1)), the existence of an algorithm of polynomial complexity to precisely solve the TSP with no bounds on the network's edge weights allows us to affirm that we can construct an algorithm of polynomial complexity.  
That also precisely solves all other NP-complete problems (some of them with the aid of the Traveling SalesMan algorithm).  
The traveling salesman problem, or TSP for short, is easy to state: given a finite number of "cities" along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities and returning to your starting point. (The travel costs are symmetric in the sense that traveling from city X to city Y costs just as much as traveling from Y to X; the "way of visiting all the cities" is simply the order in which the cities are visited.) To put it differently, the data consist of integer weights assigned to the edges of a finite complete graph; the objective is to find a hamiltonian cycle (that is, a cycle passing through all the vertices) of the minimum total weight. In this context, hamiltonian cycles are commonly called tours.  
The TSMP-1 (Traveling SalesMan Problem) code is intended for solving the problem of the precise determination of the length and path of a minimal Hamiltonian cycle (cycles) of a weighed network (the Traveling Salesman Problem, the TSP) in a time that polynomially depends on the network's dimension (the number of its nodes); and it also relates to the construction (on this basis) of algorithms of polynomial complexity to solve so-called NP-complete problems of discrete mathematics. The essence of this problem is as follows: to find in a network given a cycle sequence of passing the edges in such a way that it includes all the nodes of the network one and only one time (i.e. the passage of the edges is a Hamiltonian cycle), and the sum of the edge weights of the cycle under consideration (the length of the cycle) is minimal among all possible cycles of the network (at least not greater than the length of any other cycles having similar properties).  
A precise method is known to solve the TSP for a network with no bounds on its edge weights. This method is based on constructing a complete set of the network's cycles. Since the number of these cycles is increased as N!, where N is the number of the network's nodes, modern computers are unable to construct and evaluate a solution set within an acceptable time period unless the problem's dimension is not large (for example, the direct solving the TSP by a search all cycles cannot be performed unless the number of the network's nodes is not greater than 30-50). If N is greater than 50, then the continuous computational process to be realized even on a very fast computer for determining the length of all the network's cycles may lose for a very long time (months or even years). This method is described both in the documentation and in the program as the Exp. Method. The fact that the precise solution of the TSP is impossible to be found without constructing a complete set of the Hamiltonian cycles is explained in theoretical cybernetics by the fact that there is a class of NP-complexity problems including the TSP. However, up to now there is no proof that problems of this class cannot be solved precisely in an acceptable time (by means of algorithms of polynomial complexity). The variant of such a method is described both in the documentation and in the program as the Polyn. Method.  
TSPLIB Instances and TSMP-1 Benchmarks  
The TSPLIB is Gerhard Reinelt's library of some 110 instances of the traveling salesman problem. Some of these instances arise from the task of drilling holes in printed circuit boards; others have been constructed artificially. (A popular way of constructing a TSP instance is to choose a set of actual cities and to define the cost of travel from X to Y as the distance between X and Y.) None of them (with a single exception) is contrived to be hard and none of them is contrived to be easy; their sizes range from 17 to 85,900 cities. TSMP-1 solver has solved each instance up to size 299 because of the problem with memory of the Win32 platform; some of the remaining instances are still open problems.  
We report below the running times for the TSMP-1 solver on TSPLIB instances. The tests were carried out on a 200 MHz Intel® Pentium Pro™ workstation under Windows NT™ ver. 4.0 and with 64 MB of RAM.  
 
# Name Type Attempts in Search Procedure Average execution time, sec  
1 burma14 GEO 1 6  
2 ulysses16 GEO 1 22  
3 gr17 MATRIX 1 8  
4 gr21 MATRIX 1 3  
5 ulysses22 GEO 1 53  
6 fri26 MATRIX 1 7  
7 bayg29 GEO 1 9  
8 bays29 GEO 1 13  
9 dantzig42 MATRIX 1 23  
10 swiss42 MATRIX 1 13  
11 att48 ATT 1 56  
12 gr48 MATRIX 1 67  
13 hk48 MATRIX 1 17  
14 eil51 EUC_2D 1 73  
15 berlin52 EUC_2D 1 29  
16 brazil58 MATRIX 1 68  
17 st70 EUC_2D 1 50  
18 eil76 EUC_2D 1 30  
19 pr76 EUC_2D 1 186  
20 gr96 GEO 1 67  
21 rat99 EUC_2D 1 95  
22 kroA100 EUC_2D 1 100  
23 kroB100 EUC_2D 1 236  
24 kroC100 EUC_2D 1 96  
25 kroD100 EUC_2D 1 100  
26 kroE100 EUC_2D 1 244  
27 rd100 EUC_2D 1 67  
28 eil101 EUC_2D 1 74  
29 lin105 EUC_2D 1 59  
30 pr107 EUC_2D 1 103  
31 gr120 MATRIX 1 223  
32 pr124 EUC_2D 1 364  
33 bier127 EUC_2D 1 165  
34 ch130 EUC_2D 1 213  
35 pr136 EUC_2D 1 397  
36 gr137 GEO 1 342  
37 pr144 EUC_2D 1 258  
38 ch150 EUC_2D 1 303  
39 kroA150 EUC_2D 1 500  
40 kroB150 EUC_2D 1 423  
41 pr152 EUC_2D 1 793  
42 u159 EUC_2D 1 100  
43 si175 MATRIX 3 1309  
44 brg180 MATRIX 1 146  
45 rat195 EUC_2D 5 2223  
46 d198 EUC_2D 3 1182  
47 kroA200 EUC_2D 1 659  
48 kroB200 EUC_2D 1 391  
49 gr202 GEO 1 501  
50 ts225 EUC_2D 1 2052  
51 tsp225 EUC_2D 1 1501  
52 pr226 EUC_2D 1 435  
53 gr229 GEO 3 3861  
54 gil262 EUC_2D 1 1306  
55 pr264 EUC_2D 1 267  
56 a280 EUC_2D 3 537  
57 pr299 EUC_2D 3 1749  
Site Map Contacts
Copyright © 1996-2017 International Intellectual Group, Inc.
About Efficiency TestLab Download / Purchase Support News
All rights reserved.