|
|
/* 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;
|
