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