/* 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 sells, 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;
distrib
>
Fedora
>
13
>
i386
>
media
>
os
>
by-pkgid
>
f1e2bc5e1a8a784323c2a7a37d36f441
>
files
>
136
