1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/examples/tsp.mod	Sun Nov 06 20:59:10 2011 +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;