1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/examples/tsp.mod Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,335 @@
1.4 +/* TSP, Traveling Salesman Problem */
1.5 +
1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
1.7 +
1.8 +/* The Traveling Salesman Problem (TSP) is stated as follows.
1.9 + Let a directed graph G = (V, E) be given, where V = {1, ..., n} is
1.10 + a set of nodes, E <= V x V is a set of arcs. Let also each arc
1.11 + e = (i,j) be assigned a number c[i,j], which is the length of the
1.12 + arc e. The problem is to find a closed path of minimal length going
1.13 + through each node of G exactly once. */
1.14 +
1.15 +param n, integer, >= 3;
1.16 +/* number of nodes */
1.17 +
1.18 +set V := 1..n;
1.19 +/* set of nodes */
1.20 +
1.21 +set E, within V cross V;
1.22 +/* set of arcs */
1.23 +
1.24 +param c{(i,j) in E};
1.25 +/* distance from node i to node j */
1.26 +
1.27 +var x{(i,j) in E}, binary;
1.28 +/* x[i,j] = 1 means that the salesman goes from node i to node j */
1.29 +
1.30 +minimize total: sum{(i,j) in E} c[i,j] * x[i,j];
1.31 +/* the objective is to make the path length as small as possible */
1.32 +
1.33 +s.t. leave{i in V}: sum{(i,j) in E} x[i,j] = 1;
1.34 +/* the salesman leaves each node i exactly once */
1.35 +
1.36 +s.t. enter{j in V}: sum{(i,j) in E} x[i,j] = 1;
1.37 +/* the salesman enters each node j exactly once */
1.38 +
1.39 +/* Constraints above are not sufficient to describe valid tours, so we
1.40 + need to add constraints to eliminate subtours, i.e. tours which have
1.41 + disconnected components. Although there are many known ways to do
1.42 + that, I invented yet another way. The general idea is the following.
1.43 + Let the salesman sells, say, cars, starting the travel from node 1,
1.44 + where he has n cars. If we require the salesman to sell exactly one
1.45 + car in each node, he will need to go through all nodes to satisfy
1.46 + this requirement, thus, all subtours will be eliminated. */
1.47 +
1.48 +var y{(i,j) in E}, >= 0;
1.49 +/* y[i,j] is the number of cars, which the salesman has after leaving
1.50 + node i and before entering node j; in terms of the network analysis,
1.51 + y[i,j] is a flow through arc (i,j) */
1.52 +
1.53 +s.t. cap{(i,j) in E}: y[i,j] <= (n-1) * x[i,j];
1.54 +/* if arc (i,j) does not belong to the salesman's tour, its capacity
1.55 + must be zero; it is obvious that on leaving a node, it is sufficient
1.56 + to have not more than n-1 cars */
1.57 +
1.58 +s.t. node{i in V}:
1.59 +/* node[i] is a conservation constraint for node i */
1.60 +
1.61 + sum{(j,i) in E} y[j,i]
1.62 + /* summary flow into node i through all ingoing arcs */
1.63 +
1.64 + + (if i = 1 then n)
1.65 + /* plus n cars which the salesman has at starting node */
1.66 +
1.67 + = /* must be equal to */
1.68 +
1.69 + sum{(i,j) in E} y[i,j]
1.70 + /* summary flow from node i through all outgoing arcs */
1.71 +
1.72 + + 1;
1.73 + /* plus one car which the salesman sells at node i */
1.74 +
1.75 +solve;
1.76 +
1.77 +printf "Optimal tour has length %d\n",
1.78 + sum{(i,j) in E} c[i,j] * x[i,j];
1.79 +printf("From node To node Distance\n");
1.80 +printf{(i,j) in E: x[i,j]} " %3d %3d %8g\n",
1.81 + i, j, c[i,j];
1.82 +
1.83 +data;
1.84 +
1.85 +/* These data correspond to the symmetric instance ulysses16 from:
1.86 +
1.87 + Reinelt, G.: TSPLIB - A travelling salesman problem library.
1.88 + ORSA-Journal of the Computing 3 (1991) 376-84;
1.89 + http://elib.zib.de/pub/Packages/mp-testdata/tsp/tsplib */
1.90 +
1.91 +/* The optimal solution is 6859 */
1.92 +
1.93 +param n := 16;
1.94 +
1.95 +param : E : c :=
1.96 + 1 2 509
1.97 + 1 3 501
1.98 + 1 4 312
1.99 + 1 5 1019
1.100 + 1 6 736
1.101 + 1 7 656
1.102 + 1 8 60
1.103 + 1 9 1039
1.104 + 1 10 726
1.105 + 1 11 2314
1.106 + 1 12 479
1.107 + 1 13 448
1.108 + 1 14 479
1.109 + 1 15 619
1.110 + 1 16 150
1.111 + 2 1 509
1.112 + 2 3 126
1.113 + 2 4 474
1.114 + 2 5 1526
1.115 + 2 6 1226
1.116 + 2 7 1133
1.117 + 2 8 532
1.118 + 2 9 1449
1.119 + 2 10 1122
1.120 + 2 11 2789
1.121 + 2 12 958
1.122 + 2 13 941
1.123 + 2 14 978
1.124 + 2 15 1127
1.125 + 2 16 542
1.126 + 3 1 501
1.127 + 3 2 126
1.128 + 3 4 541
1.129 + 3 5 1516
1.130 + 3 6 1184
1.131 + 3 7 1084
1.132 + 3 8 536
1.133 + 3 9 1371
1.134 + 3 10 1045
1.135 + 3 11 2728
1.136 + 3 12 913
1.137 + 3 13 904
1.138 + 3 14 946
1.139 + 3 15 1115
1.140 + 3 16 499
1.141 + 4 1 312
1.142 + 4 2 474
1.143 + 4 3 541
1.144 + 4 5 1157
1.145 + 4 6 980
1.146 + 4 7 919
1.147 + 4 8 271
1.148 + 4 9 1333
1.149 + 4 10 1029
1.150 + 4 11 2553
1.151 + 4 12 751
1.152 + 4 13 704
1.153 + 4 14 720
1.154 + 4 15 783
1.155 + 4 16 455
1.156 + 5 1 1019
1.157 + 5 2 1526
1.158 + 5 3 1516
1.159 + 5 4 1157
1.160 + 5 6 478
1.161 + 5 7 583
1.162 + 5 8 996
1.163 + 5 9 858
1.164 + 5 10 855
1.165 + 5 11 1504
1.166 + 5 12 677
1.167 + 5 13 651
1.168 + 5 14 600
1.169 + 5 15 401
1.170 + 5 16 1033
1.171 + 6 1 736
1.172 + 6 2 1226
1.173 + 6 3 1184
1.174 + 6 4 980
1.175 + 6 5 478
1.176 + 6 7 115
1.177 + 6 8 740
1.178 + 6 9 470
1.179 + 6 10 379
1.180 + 6 11 1581
1.181 + 6 12 271
1.182 + 6 13 289
1.183 + 6 14 261
1.184 + 6 15 308
1.185 + 6 16 687
1.186 + 7 1 656
1.187 + 7 2 1133
1.188 + 7 3 1084
1.189 + 7 4 919
1.190 + 7 5 583
1.191 + 7 6 115
1.192 + 7 8 667
1.193 + 7 9 455
1.194 + 7 10 288
1.195 + 7 11 1661
1.196 + 7 12 177
1.197 + 7 13 216
1.198 + 7 14 207
1.199 + 7 15 343
1.200 + 7 16 592
1.201 + 8 1 60
1.202 + 8 2 532
1.203 + 8 3 536
1.204 + 8 4 271
1.205 + 8 5 996
1.206 + 8 6 740
1.207 + 8 7 667
1.208 + 8 9 1066
1.209 + 8 10 759
1.210 + 8 11 2320
1.211 + 8 12 493
1.212 + 8 13 454
1.213 + 8 14 479
1.214 + 8 15 598
1.215 + 8 16 206
1.216 + 9 1 1039
1.217 + 9 2 1449
1.218 + 9 3 1371
1.219 + 9 4 1333
1.220 + 9 5 858
1.221 + 9 6 470
1.222 + 9 7 455
1.223 + 9 8 1066
1.224 + 9 10 328
1.225 + 9 11 1387
1.226 + 9 12 591
1.227 + 9 13 650
1.228 + 9 14 656
1.229 + 9 15 776
1.230 + 9 16 933
1.231 + 10 1 726
1.232 + 10 2 1122
1.233 + 10 3 1045
1.234 + 10 4 1029
1.235 + 10 5 855
1.236 + 10 6 379
1.237 + 10 7 288
1.238 + 10 8 759
1.239 + 10 9 328
1.240 + 10 11 1697
1.241 + 10 12 333
1.242 + 10 13 400
1.243 + 10 14 427
1.244 + 10 15 622
1.245 + 10 16 610
1.246 + 11 1 2314
1.247 + 11 2 2789
1.248 + 11 3 2728
1.249 + 11 4 2553
1.250 + 11 5 1504
1.251 + 11 6 1581
1.252 + 11 7 1661
1.253 + 11 8 2320
1.254 + 11 9 1387
1.255 + 11 10 1697
1.256 + 11 12 1838
1.257 + 11 13 1868
1.258 + 11 14 1841
1.259 + 11 15 1789
1.260 + 11 16 2248
1.261 + 12 1 479
1.262 + 12 2 958
1.263 + 12 3 913
1.264 + 12 4 751
1.265 + 12 5 677
1.266 + 12 6 271
1.267 + 12 7 177
1.268 + 12 8 493
1.269 + 12 9 591
1.270 + 12 10 333
1.271 + 12 11 1838
1.272 + 12 13 68
1.273 + 12 14 105
1.274 + 12 15 336
1.275 + 12 16 417
1.276 + 13 1 448
1.277 + 13 2 941
1.278 + 13 3 904
1.279 + 13 4 704
1.280 + 13 5 651
1.281 + 13 6 289
1.282 + 13 7 216
1.283 + 13 8 454
1.284 + 13 9 650
1.285 + 13 10 400
1.286 + 13 11 1868
1.287 + 13 12 68
1.288 + 13 14 52
1.289 + 13 15 287
1.290 + 13 16 406
1.291 + 14 1 479
1.292 + 14 2 978
1.293 + 14 3 946
1.294 + 14 4 720
1.295 + 14 5 600
1.296 + 14 6 261
1.297 + 14 7 207
1.298 + 14 8 479
1.299 + 14 9 656
1.300 + 14 10 427
1.301 + 14 11 1841
1.302 + 14 12 105
1.303 + 14 13 52
1.304 + 14 15 237
1.305 + 14 16 449
1.306 + 15 1 619
1.307 + 15 2 1127
1.308 + 15 3 1115
1.309 + 15 4 783
1.310 + 15 5 401
1.311 + 15 6 308
1.312 + 15 7 343
1.313 + 15 8 598
1.314 + 15 9 776
1.315 + 15 10 622
1.316 + 15 11 1789
1.317 + 15 12 336
1.318 + 15 13 287
1.319 + 15 14 237
1.320 + 15 16 636
1.321 + 16 1 150
1.322 + 16 2 542
1.323 + 16 3 499
1.324 + 16 4 455
1.325 + 16 5 1033
1.326 + 16 6 687
1.327 + 16 7 592
1.328 + 16 8 206
1.329 + 16 9 933
1.330 + 16 10 610
1.331 + 16 11 2248
1.332 + 16 12 417
1.333 + 16 13 406
1.334 + 16 14 449
1.335 + 16 15 636
1.336 +;
1.337 +
1.338 +end;