You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
335 lines
6.5 KiB
335 lines
6.5 KiB
/* TSP, Traveling Salesman Problem */
|
|
|
|
/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
|
|
|
|
/* The Traveling Salesman Problem (TSP) is stated as follows.
|
|
Let a directed graph G = (V, E) be given, where V = {1, ..., n} is
|
|
a set of nodes, E <= V x V is a set of arcs. Let also each arc
|
|
e = (i,j) be assigned a number c[i,j], which is the length of the
|
|
arc e. The problem is to find a closed path of minimal length going
|
|
through each node of G exactly once. */
|
|
|
|
param n, integer, >= 3;
|
|
/* number of nodes */
|
|
|
|
set V := 1..n;
|
|
/* set of nodes */
|
|
|
|
set E, within V cross V;
|
|
/* set of arcs */
|
|
|
|
param c{(i,j) in E};
|
|
/* distance from node i to node j */
|
|
|
|
var x{(i,j) in E}, binary;
|
|
/* x[i,j] = 1 means that the salesman goes from node i to node j */
|
|
|
|
minimize total: sum{(i,j) in E} c[i,j] * x[i,j];
|
|
/* the objective is to make the path length as small as possible */
|
|
|
|
s.t. leave{i in V}: sum{(i,j) in E} x[i,j] = 1;
|
|
/* the salesman leaves each node i exactly once */
|
|
|
|
s.t. enter{j in V}: sum{(i,j) in E} x[i,j] = 1;
|
|
/* the salesman enters each node j exactly once */
|
|
|
|
/* Constraints above are not sufficient to describe valid tours, so we
|
|
need to add constraints to eliminate subtours, i.e. tours which have
|
|
disconnected components. Although there are many known ways to do
|
|
that, I invented yet another way. The general idea is the following.
|
|
Let the salesman sell, say, cars, starting the travel from node 1,
|
|
where he has n cars. If we require the salesman to sell exactly one
|
|
car in each node, he will need to go through all nodes to satisfy
|
|
this requirement, thus, all subtours will be eliminated. */
|
|
|
|
var y{(i,j) in E}, >= 0;
|
|
/* y[i,j] is the number of cars, which the salesman has after leaving
|
|
node i and before entering node j; in terms of the network analysis,
|
|
y[i,j] is a flow through arc (i,j) */
|
|
|
|
s.t. cap{(i,j) in E}: y[i,j] <= (n-1) * x[i,j];
|
|
/* if arc (i,j) does not belong to the salesman's tour, its capacity
|
|
must be zero; it is obvious that on leaving a node, it is sufficient
|
|
to have not more than n-1 cars */
|
|
|
|
s.t. node{i in V}:
|
|
/* node[i] is a conservation constraint for node i */
|
|
|
|
sum{(j,i) in E} y[j,i]
|
|
/* summary flow into node i through all ingoing arcs */
|
|
|
|
+ (if i = 1 then n)
|
|
/* plus n cars which the salesman has at starting node */
|
|
|
|
= /* must be equal to */
|
|
|
|
sum{(i,j) in E} y[i,j]
|
|
/* summary flow from node i through all outgoing arcs */
|
|
|
|
+ 1;
|
|
/* plus one car which the salesman sells at node i */
|
|
|
|
solve;
|
|
|
|
printf "Optimal tour has length %d\n",
|
|
sum{(i,j) in E} c[i,j] * x[i,j];
|
|
printf("From node To node Distance\n");
|
|
printf{(i,j) in E: x[i,j]} " %3d %3d %8g\n",
|
|
i, j, c[i,j];
|
|
|
|
data;
|
|
|
|
/* These data correspond to the symmetric instance ulysses16 from:
|
|
|
|
Reinelt, G.: TSPLIB - A travelling salesman problem library.
|
|
ORSA-Journal of the Computing 3 (1991) 376-84;
|
|
http://elib.zib.de/pub/Packages/mp-testdata/tsp/tsplib */
|
|
|
|
/* The optimal solution is 6859 */
|
|
|
|
param n := 16;
|
|
|
|
param : E : c :=
|
|
1 2 509
|
|
1 3 501
|
|
1 4 312
|
|
1 5 1019
|
|
1 6 736
|
|
1 7 656
|
|
1 8 60
|
|
1 9 1039
|
|
1 10 726
|
|
1 11 2314
|
|
1 12 479
|
|
1 13 448
|
|
1 14 479
|
|
1 15 619
|
|
1 16 150
|
|
2 1 509
|
|
2 3 126
|
|
2 4 474
|
|
2 5 1526
|
|
2 6 1226
|
|
2 7 1133
|
|
2 8 532
|
|
2 9 1449
|
|
2 10 1122
|
|
2 11 2789
|
|
2 12 958
|
|
2 13 941
|
|
2 14 978
|
|
2 15 1127
|
|
2 16 542
|
|
3 1 501
|
|
3 2 126
|
|
3 4 541
|
|
3 5 1516
|
|
3 6 1184
|
|
3 7 1084
|
|
3 8 536
|
|
3 9 1371
|
|
3 10 1045
|
|
3 11 2728
|
|
3 12 913
|
|
3 13 904
|
|
3 14 946
|
|
3 15 1115
|
|
3 16 499
|
|
4 1 312
|
|
4 2 474
|
|
4 3 541
|
|
4 5 1157
|
|
4 6 980
|
|
4 7 919
|
|
4 8 271
|
|
4 9 1333
|
|
4 10 1029
|
|
4 11 2553
|
|
4 12 751
|
|
4 13 704
|
|
4 14 720
|
|
4 15 783
|
|
4 16 455
|
|
5 1 1019
|
|
5 2 1526
|
|
5 3 1516
|
|
5 4 1157
|
|
5 6 478
|
|
5 7 583
|
|
5 8 996
|
|
5 9 858
|
|
5 10 855
|
|
5 11 1504
|
|
5 12 677
|
|
5 13 651
|
|
5 14 600
|
|
5 15 401
|
|
5 16 1033
|
|
6 1 736
|
|
6 2 1226
|
|
6 3 1184
|
|
6 4 980
|
|
6 5 478
|
|
6 7 115
|
|
6 8 740
|
|
6 9 470
|
|
6 10 379
|
|
6 11 1581
|
|
6 12 271
|
|
6 13 289
|
|
6 14 261
|
|
6 15 308
|
|
6 16 687
|
|
7 1 656
|
|
7 2 1133
|
|
7 3 1084
|
|
7 4 919
|
|
7 5 583
|
|
7 6 115
|
|
7 8 667
|
|
7 9 455
|
|
7 10 288
|
|
7 11 1661
|
|
7 12 177
|
|
7 13 216
|
|
7 14 207
|
|
7 15 343
|
|
7 16 592
|
|
8 1 60
|
|
8 2 532
|
|
8 3 536
|
|
8 4 271
|
|
8 5 996
|
|
8 6 740
|
|
8 7 667
|
|
8 9 1066
|
|
8 10 759
|
|
8 11 2320
|
|
8 12 493
|
|
8 13 454
|
|
8 14 479
|
|
8 15 598
|
|
8 16 206
|
|
9 1 1039
|
|
9 2 1449
|
|
9 3 1371
|
|
9 4 1333
|
|
9 5 858
|
|
9 6 470
|
|
9 7 455
|
|
9 8 1066
|
|
9 10 328
|
|
9 11 1387
|
|
9 12 591
|
|
9 13 650
|
|
9 14 656
|
|
9 15 776
|
|
9 16 933
|
|
10 1 726
|
|
10 2 1122
|
|
10 3 1045
|
|
10 4 1029
|
|
10 5 855
|
|
10 6 379
|
|
10 7 288
|
|
10 8 759
|
|
10 9 328
|
|
10 11 1697
|
|
10 12 333
|
|
10 13 400
|
|
10 14 427
|
|
10 15 622
|
|
10 16 610
|
|
11 1 2314
|
|
11 2 2789
|
|
11 3 2728
|
|
11 4 2553
|
|
11 5 1504
|
|
11 6 1581
|
|
11 7 1661
|
|
11 8 2320
|
|
11 9 1387
|
|
11 10 1697
|
|
11 12 1838
|
|
11 13 1868
|
|
11 14 1841
|
|
11 15 1789
|
|
11 16 2248
|
|
12 1 479
|
|
12 2 958
|
|
12 3 913
|
|
12 4 751
|
|
12 5 677
|
|
12 6 271
|
|
12 7 177
|
|
12 8 493
|
|
12 9 591
|
|
12 10 333
|
|
12 11 1838
|
|
12 13 68
|
|
12 14 105
|
|
12 15 336
|
|
12 16 417
|
|
13 1 448
|
|
13 2 941
|
|
13 3 904
|
|
13 4 704
|
|
13 5 651
|
|
13 6 289
|
|
13 7 216
|
|
13 8 454
|
|
13 9 650
|
|
13 10 400
|
|
13 11 1868
|
|
13 12 68
|
|
13 14 52
|
|
13 15 287
|
|
13 16 406
|
|
14 1 479
|
|
14 2 978
|
|
14 3 946
|
|
14 4 720
|
|
14 5 600
|
|
14 6 261
|
|
14 7 207
|
|
14 8 479
|
|
14 9 656
|
|
14 10 427
|
|
14 11 1841
|
|
14 12 105
|
|
14 13 52
|
|
14 15 237
|
|
14 16 449
|
|
15 1 619
|
|
15 2 1127
|
|
15 3 1115
|
|
15 4 783
|
|
15 5 401
|
|
15 6 308
|
|
15 7 343
|
|
15 8 598
|
|
15 9 776
|
|
15 10 622
|
|
15 11 1789
|
|
15 12 336
|
|
15 13 287
|
|
15 14 237
|
|
15 16 636
|
|
16 1 150
|
|
16 2 542
|
|
16 3 499
|
|
16 4 455
|
|
16 5 1033
|
|
16 6 687
|
|
16 7 592
|
|
16 8 206
|
|
16 9 933
|
|
16 10 610
|
|
16 11 2248
|
|
16 12 417
|
|
16 13 406
|
|
16 14 449
|
|
16 15 636
|
|
;
|
|
|
|
end;
|