1 | /* TSP, Traveling Salesman Problem */ |
---|
2 | |
---|
3 | /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ |
---|
4 | |
---|
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. */ |
---|
11 | |
---|
12 | param n, integer, >= 3; |
---|
13 | /* number of nodes */ |
---|
14 | |
---|
15 | set V := 1..n; |
---|
16 | /* set of nodes */ |
---|
17 | |
---|
18 | set E, within V cross V; |
---|
19 | /* set of arcs */ |
---|
20 | |
---|
21 | param c{(i,j) in E}; |
---|
22 | /* distance from node i to node j */ |
---|
23 | |
---|
24 | var x{(i,j) in E}, binary; |
---|
25 | /* x[i,j] = 1 means that the salesman goes from node i to node j */ |
---|
26 | |
---|
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 */ |
---|
29 | |
---|
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 */ |
---|
32 | |
---|
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 */ |
---|
35 | |
---|
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. */ |
---|
44 | |
---|
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) */ |
---|
49 | |
---|
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 */ |
---|
54 | |
---|
55 | s.t. node{i in V}: |
---|
56 | /* node[i] is a conservation constraint for node i */ |
---|
57 | |
---|
58 | sum{(j,i) in E} y[j,i] |
---|
59 | /* summary flow into node i through all ingoing arcs */ |
---|
60 | |
---|
61 | + (if i = 1 then n) |
---|
62 | /* plus n cars which the salesman has at starting node */ |
---|
63 | |
---|
64 | = /* must be equal to */ |
---|
65 | |
---|
66 | sum{(i,j) in E} y[i,j] |
---|
67 | /* summary flow from node i through all outgoing arcs */ |
---|
68 | |
---|
69 | + 1; |
---|
70 | /* plus one car which the salesman sells at node i */ |
---|
71 | |
---|
72 | solve; |
---|
73 | |
---|
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]; |
---|
79 | |
---|
80 | data; |
---|
81 | |
---|
82 | /* These data correspond to the symmetric instance ulysses16 from: |
---|
83 | |
---|
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 */ |
---|
87 | |
---|
88 | /* The optimal solution is 6859 */ |
---|
89 | |
---|
90 | param n := 16; |
---|
91 | |
---|
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 | ; |
---|
334 | |
---|
335 | end; |
---|