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