lemon-project-template-glpk

annotate deps/glpk/examples/tsp.mod @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
rev   line source
alpar@9 1 /* TSP, Traveling Salesman Problem */
alpar@9 2
alpar@9 3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
alpar@9 4
alpar@9 5 /* The Traveling Salesman Problem (TSP) is stated as follows.
alpar@9 6 Let a directed graph G = (V, E) be given, where V = {1, ..., n} is
alpar@9 7 a set of nodes, E <= V x V is a set of arcs. Let also each arc
alpar@9 8 e = (i,j) be assigned a number c[i,j], which is the length of the
alpar@9 9 arc e. The problem is to find a closed path of minimal length going
alpar@9 10 through each node of G exactly once. */
alpar@9 11
alpar@9 12 param n, integer, >= 3;
alpar@9 13 /* number of nodes */
alpar@9 14
alpar@9 15 set V := 1..n;
alpar@9 16 /* set of nodes */
alpar@9 17
alpar@9 18 set E, within V cross V;
alpar@9 19 /* set of arcs */
alpar@9 20
alpar@9 21 param c{(i,j) in E};
alpar@9 22 /* distance from node i to node j */
alpar@9 23
alpar@9 24 var x{(i,j) in E}, binary;
alpar@9 25 /* x[i,j] = 1 means that the salesman goes from node i to node j */
alpar@9 26
alpar@9 27 minimize total: sum{(i,j) in E} c[i,j] * x[i,j];
alpar@9 28 /* the objective is to make the path length as small as possible */
alpar@9 29
alpar@9 30 s.t. leave{i in V}: sum{(i,j) in E} x[i,j] = 1;
alpar@9 31 /* the salesman leaves each node i exactly once */
alpar@9 32
alpar@9 33 s.t. enter{j in V}: sum{(i,j) in E} x[i,j] = 1;
alpar@9 34 /* the salesman enters each node j exactly once */
alpar@9 35
alpar@9 36 /* Constraints above are not sufficient to describe valid tours, so we
alpar@9 37 need to add constraints to eliminate subtours, i.e. tours which have
alpar@9 38 disconnected components. Although there are many known ways to do
alpar@9 39 that, I invented yet another way. The general idea is the following.
alpar@9 40 Let the salesman sells, say, cars, starting the travel from node 1,
alpar@9 41 where he has n cars. If we require the salesman to sell exactly one
alpar@9 42 car in each node, he will need to go through all nodes to satisfy
alpar@9 43 this requirement, thus, all subtours will be eliminated. */
alpar@9 44
alpar@9 45 var y{(i,j) in E}, >= 0;
alpar@9 46 /* y[i,j] is the number of cars, which the salesman has after leaving
alpar@9 47 node i and before entering node j; in terms of the network analysis,
alpar@9 48 y[i,j] is a flow through arc (i,j) */
alpar@9 49
alpar@9 50 s.t. cap{(i,j) in E}: y[i,j] <= (n-1) * x[i,j];
alpar@9 51 /* if arc (i,j) does not belong to the salesman's tour, its capacity
alpar@9 52 must be zero; it is obvious that on leaving a node, it is sufficient
alpar@9 53 to have not more than n-1 cars */
alpar@9 54
alpar@9 55 s.t. node{i in V}:
alpar@9 56 /* node[i] is a conservation constraint for node i */
alpar@9 57
alpar@9 58 sum{(j,i) in E} y[j,i]
alpar@9 59 /* summary flow into node i through all ingoing arcs */
alpar@9 60
alpar@9 61 + (if i = 1 then n)
alpar@9 62 /* plus n cars which the salesman has at starting node */
alpar@9 63
alpar@9 64 = /* must be equal to */
alpar@9 65
alpar@9 66 sum{(i,j) in E} y[i,j]
alpar@9 67 /* summary flow from node i through all outgoing arcs */
alpar@9 68
alpar@9 69 + 1;
alpar@9 70 /* plus one car which the salesman sells at node i */
alpar@9 71
alpar@9 72 solve;
alpar@9 73
alpar@9 74 printf "Optimal tour has length %d\n",
alpar@9 75 sum{(i,j) in E} c[i,j] * x[i,j];
alpar@9 76 printf("From node To node Distance\n");
alpar@9 77 printf{(i,j) in E: x[i,j]} " %3d %3d %8g\n",
alpar@9 78 i, j, c[i,j];
alpar@9 79
alpar@9 80 data;
alpar@9 81
alpar@9 82 /* These data correspond to the symmetric instance ulysses16 from:
alpar@9 83
alpar@9 84 Reinelt, G.: TSPLIB - A travelling salesman problem library.
alpar@9 85 ORSA-Journal of the Computing 3 (1991) 376-84;
alpar@9 86 http://elib.zib.de/pub/Packages/mp-testdata/tsp/tsplib */
alpar@9 87
alpar@9 88 /* The optimal solution is 6859 */
alpar@9 89
alpar@9 90 param n := 16;
alpar@9 91
alpar@9 92 param : E : c :=
alpar@9 93 1 2 509
alpar@9 94 1 3 501
alpar@9 95 1 4 312
alpar@9 96 1 5 1019
alpar@9 97 1 6 736
alpar@9 98 1 7 656
alpar@9 99 1 8 60
alpar@9 100 1 9 1039
alpar@9 101 1 10 726
alpar@9 102 1 11 2314
alpar@9 103 1 12 479
alpar@9 104 1 13 448
alpar@9 105 1 14 479
alpar@9 106 1 15 619
alpar@9 107 1 16 150
alpar@9 108 2 1 509
alpar@9 109 2 3 126
alpar@9 110 2 4 474
alpar@9 111 2 5 1526
alpar@9 112 2 6 1226
alpar@9 113 2 7 1133
alpar@9 114 2 8 532
alpar@9 115 2 9 1449
alpar@9 116 2 10 1122
alpar@9 117 2 11 2789
alpar@9 118 2 12 958
alpar@9 119 2 13 941
alpar@9 120 2 14 978
alpar@9 121 2 15 1127
alpar@9 122 2 16 542
alpar@9 123 3 1 501
alpar@9 124 3 2 126
alpar@9 125 3 4 541
alpar@9 126 3 5 1516
alpar@9 127 3 6 1184
alpar@9 128 3 7 1084
alpar@9 129 3 8 536
alpar@9 130 3 9 1371
alpar@9 131 3 10 1045
alpar@9 132 3 11 2728
alpar@9 133 3 12 913
alpar@9 134 3 13 904
alpar@9 135 3 14 946
alpar@9 136 3 15 1115
alpar@9 137 3 16 499
alpar@9 138 4 1 312
alpar@9 139 4 2 474
alpar@9 140 4 3 541
alpar@9 141 4 5 1157
alpar@9 142 4 6 980
alpar@9 143 4 7 919
alpar@9 144 4 8 271
alpar@9 145 4 9 1333
alpar@9 146 4 10 1029
alpar@9 147 4 11 2553
alpar@9 148 4 12 751
alpar@9 149 4 13 704
alpar@9 150 4 14 720
alpar@9 151 4 15 783
alpar@9 152 4 16 455
alpar@9 153 5 1 1019
alpar@9 154 5 2 1526
alpar@9 155 5 3 1516
alpar@9 156 5 4 1157
alpar@9 157 5 6 478
alpar@9 158 5 7 583
alpar@9 159 5 8 996
alpar@9 160 5 9 858
alpar@9 161 5 10 855
alpar@9 162 5 11 1504
alpar@9 163 5 12 677
alpar@9 164 5 13 651
alpar@9 165 5 14 600
alpar@9 166 5 15 401
alpar@9 167 5 16 1033
alpar@9 168 6 1 736
alpar@9 169 6 2 1226
alpar@9 170 6 3 1184
alpar@9 171 6 4 980
alpar@9 172 6 5 478
alpar@9 173 6 7 115
alpar@9 174 6 8 740
alpar@9 175 6 9 470
alpar@9 176 6 10 379
alpar@9 177 6 11 1581
alpar@9 178 6 12 271
alpar@9 179 6 13 289
alpar@9 180 6 14 261
alpar@9 181 6 15 308
alpar@9 182 6 16 687
alpar@9 183 7 1 656
alpar@9 184 7 2 1133
alpar@9 185 7 3 1084
alpar@9 186 7 4 919
alpar@9 187 7 5 583
alpar@9 188 7 6 115
alpar@9 189 7 8 667
alpar@9 190 7 9 455
alpar@9 191 7 10 288
alpar@9 192 7 11 1661
alpar@9 193 7 12 177
alpar@9 194 7 13 216
alpar@9 195 7 14 207
alpar@9 196 7 15 343
alpar@9 197 7 16 592
alpar@9 198 8 1 60
alpar@9 199 8 2 532
alpar@9 200 8 3 536
alpar@9 201 8 4 271
alpar@9 202 8 5 996
alpar@9 203 8 6 740
alpar@9 204 8 7 667
alpar@9 205 8 9 1066
alpar@9 206 8 10 759
alpar@9 207 8 11 2320
alpar@9 208 8 12 493
alpar@9 209 8 13 454
alpar@9 210 8 14 479
alpar@9 211 8 15 598
alpar@9 212 8 16 206
alpar@9 213 9 1 1039
alpar@9 214 9 2 1449
alpar@9 215 9 3 1371
alpar@9 216 9 4 1333
alpar@9 217 9 5 858
alpar@9 218 9 6 470
alpar@9 219 9 7 455
alpar@9 220 9 8 1066
alpar@9 221 9 10 328
alpar@9 222 9 11 1387
alpar@9 223 9 12 591
alpar@9 224 9 13 650
alpar@9 225 9 14 656
alpar@9 226 9 15 776
alpar@9 227 9 16 933
alpar@9 228 10 1 726
alpar@9 229 10 2 1122
alpar@9 230 10 3 1045
alpar@9 231 10 4 1029
alpar@9 232 10 5 855
alpar@9 233 10 6 379
alpar@9 234 10 7 288
alpar@9 235 10 8 759
alpar@9 236 10 9 328
alpar@9 237 10 11 1697
alpar@9 238 10 12 333
alpar@9 239 10 13 400
alpar@9 240 10 14 427
alpar@9 241 10 15 622
alpar@9 242 10 16 610
alpar@9 243 11 1 2314
alpar@9 244 11 2 2789
alpar@9 245 11 3 2728
alpar@9 246 11 4 2553
alpar@9 247 11 5 1504
alpar@9 248 11 6 1581
alpar@9 249 11 7 1661
alpar@9 250 11 8 2320
alpar@9 251 11 9 1387
alpar@9 252 11 10 1697
alpar@9 253 11 12 1838
alpar@9 254 11 13 1868
alpar@9 255 11 14 1841
alpar@9 256 11 15 1789
alpar@9 257 11 16 2248
alpar@9 258 12 1 479
alpar@9 259 12 2 958
alpar@9 260 12 3 913
alpar@9 261 12 4 751
alpar@9 262 12 5 677
alpar@9 263 12 6 271
alpar@9 264 12 7 177
alpar@9 265 12 8 493
alpar@9 266 12 9 591
alpar@9 267 12 10 333
alpar@9 268 12 11 1838
alpar@9 269 12 13 68
alpar@9 270 12 14 105
alpar@9 271 12 15 336
alpar@9 272 12 16 417
alpar@9 273 13 1 448
alpar@9 274 13 2 941
alpar@9 275 13 3 904
alpar@9 276 13 4 704
alpar@9 277 13 5 651
alpar@9 278 13 6 289
alpar@9 279 13 7 216
alpar@9 280 13 8 454
alpar@9 281 13 9 650
alpar@9 282 13 10 400
alpar@9 283 13 11 1868
alpar@9 284 13 12 68
alpar@9 285 13 14 52
alpar@9 286 13 15 287
alpar@9 287 13 16 406
alpar@9 288 14 1 479
alpar@9 289 14 2 978
alpar@9 290 14 3 946
alpar@9 291 14 4 720
alpar@9 292 14 5 600
alpar@9 293 14 6 261
alpar@9 294 14 7 207
alpar@9 295 14 8 479
alpar@9 296 14 9 656
alpar@9 297 14 10 427
alpar@9 298 14 11 1841
alpar@9 299 14 12 105
alpar@9 300 14 13 52
alpar@9 301 14 15 237
alpar@9 302 14 16 449
alpar@9 303 15 1 619
alpar@9 304 15 2 1127
alpar@9 305 15 3 1115
alpar@9 306 15 4 783
alpar@9 307 15 5 401
alpar@9 308 15 6 308
alpar@9 309 15 7 343
alpar@9 310 15 8 598
alpar@9 311 15 9 776
alpar@9 312 15 10 622
alpar@9 313 15 11 1789
alpar@9 314 15 12 336
alpar@9 315 15 13 287
alpar@9 316 15 14 237
alpar@9 317 15 16 636
alpar@9 318 16 1 150
alpar@9 319 16 2 542
alpar@9 320 16 3 499
alpar@9 321 16 4 455
alpar@9 322 16 5 1033
alpar@9 323 16 6 687
alpar@9 324 16 7 592
alpar@9 325 16 8 206
alpar@9 326 16 9 933
alpar@9 327 16 10 610
alpar@9 328 16 11 2248
alpar@9 329 16 12 417
alpar@9 330 16 13 406
alpar@9 331 16 14 449
alpar@9 332 16 15 636
alpar@9 333 ;
alpar@9 334
alpar@9 335 end;