# source:glpk-cmake/examples/tsp.mod@1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

• Generated files and doc/notes are removed
File size: 6.5 KB
Line
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
12param n, integer, >= 3;
13/* number of nodes */
14
15set V := 1..n;
16/* set of nodes */
17
18set E, within V cross V;
19/* set of arcs */
20
21param c{(i,j) in E};
22/* distance from node i to node j */
23
24var x{(i,j) in E}, binary;
25/* x[i,j] = 1 means that the salesman goes from node i to node j */
26
27minimize 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
30s.t. leave{i in V}: sum{(i,j) in E} x[i,j] = 1;
31/* the salesman leaves each node i exactly once */
32
33s.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
45var 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
50s.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
55s.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
72solve;
73
74printf "Optimal tour has length %d\n",
75   sum{(i,j) in E} c[i,j] * x[i,j];
76printf("From node   To node   Distance\n");
77printf{(i,j) in E: x[i,j]} "      %3d       %3d   %8g\n",
78   i, j, c[i,j];
79
80data;
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
90param n := 16;
91
92param : 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
335end;
Note: See TracBrowser for help on using the repository browser.