forked from johannesgerer/jburkardt-f
-
Notifications
You must be signed in to change notification settings - Fork 1
/
lau_np.html
457 lines (414 loc) · 12 KB
/
lau_np.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
<html>
<head>
<title>
LAU_NP - Heuristics for NP problems
</title>
</head>
<body bgcolor="#EEEEEE" link="#CC0000" alink="#FF3300" vlink="#000055">
<h1 align = "center">
LAU_NP <br> Heuristics for NP problems
</h1>
<hr>
<p>
<b>LAU_NP</b>
is a FORTRAN90 library which
implements heuristic algorithms for certain "hard" problems,
by Hang Tong Lau.
</p>
<p>
These problems are hard in the sense that, as the problem size N
increases, the amount of work required to compute a solution grows
exponentially.
</p>
<p>
The classic example of this is the "traveling salesman problem",
which seeks the shortest roundtrip that visits each location exactly
once. The obvious method of solution, to compute the length of every
possible path, is not much worse than the best known method of
solution, in terms of the amount of computing required to find the
exact answer. However, there are heuristic methods that can find a
"reasonable" approximation to the answer for most problems, in a
much shorter amount of time.
</p>
<p>
The problems considered include:
<ul>
<li>
the integer linear programming problem;
</li>
<li>
the K-center problem;
</li>
<li>
the K-median problem;
</li>
<li>
the 0-1 knapsack problem;
</li>
<li>
the multiple knapsack problem;
</li>
<li>
the graph matching problem;
</li>
<li>
the graph partitioning problem;
</li>
<li>
the minimal Steiner tree problem;
</li>
<li>
the traveling salesman problem;
</li>
</ul>
</p>
<h3 align = "center">
Related Data and Programs:
</h3>
<p>
<a href = "../../f77_src/asa058/asa058.html">
ASA058</a>,
a FORTRAN77 library which
contains the original text of the Sparks
clustering algorithm.
</p>
<p>
<a href = "../../f77_src/asa136/asa136.html">
ASA136</a>,
a FORTRAN77 library which
contains the original text of the Hartigan
and Wong clustering algorithm.
</p>
<p>
<a href = "../../f_src/cities/cities.html">
CITIES</a>,
a FORTRAN90 library which
handles various problems associated with a set of "cities" on a map.
</p>
<p>
<a href = "../../datasets/cities/cities.html">
CITIES</a>,
a dataset directory which
contains a number of city distance datasets.
</p>
<p>
<a href = "../../f_src/floyd/floyd.html">
FLOYD</a>,
a FORTRAN90 library which
implements Floyd's algorithm for finding the shortest distance between pairs of
nodes on a directed graph.
</p>
<p>
<a href = "../../f_src/kmeans/kmeans.html">
KMEANS</a>,
a FORTRAN90 library which
contains several implementations of
the K-Means algorithm.
</p>
<p>
<a href = "../../f77_src/knapsack/knapsack.html">
KNAPSACK</a>,
a FORTRAN77 library which
solves a variety of knapsack problems.
</p>
<p>
<a href = "../../datasets/knapsack_01/knapsack_01.html">
KNAPSACK_01</a>,
a dataset directory which
contains test data for the 0/1 knapsack problem;
</p>
<p>
<a href = "../../datasets/knapsack_multiple/knapsack_multiple.html">
KNAPSACK_MULTIPLE</a>,
a dataset directory which
contains test data for the multiple knapsack problem;
</p>
<p>
<a href = "../../f77_src/lamp/lamp.html">
LAMP</a>,
a FORTRAN77 library which
solves linear assignment and matching problems.
</p>
<p>
<a href = "../../f_src/partition_problem/partition_problem.html">
PARTITION_PROBLEM</a>,
a FORTRAN90 library which
seeks solutions of the partition problem, splitting a set of integers into
two subsets with equal sum.
</p>
<p>
<a href = "../../f_src/spaeth/spaeth.html">
SPAETH</a>,
a FORTRAN90 library which
can cluster data according to various principles.
</p>
<p>
<a href = "../../datasets/spaeth/spaeth.html">
SPAETH</a>,
a dataset collection which
contains a set of test data.
</p>
<p>
<a href = "../../f_src/spaeth2/spaeth2.html">
SPAETH2</a>,
a FORTRAN90 library which
can cluster data according to various
principles.
</p>
<p>
<a href = "../../datasets/spaeth2/spaeth2.html">
SPAETH2</a>,
a dataset collection which
contains a set of test data.
</p>
<p>
<a href = "../../f_src/subset_sum/subset_sum.html">
SUBSET_SUM</a>,
a FORTRAN90 library which
seeks solutions of the subset sum problem.
</p>
<p>
<a href = "../../f77_src/toms456/toms456.html">
TOMS456</a>,
a FORTRAN77 library which
handles the routing problem, connecting some nodes in a network.
</p>
<p>
<a href = "../../datasets/tsp/tsp.html">
TSP</a>,
a dataset directory which
contains test data for the traveling salesperson problem;
</p>
<h3 align = "center">
Author:
</h3>
<p>
Hang Tong Lau
</p>
<h3 align = "center">
Reference:
</h3>
<p>
<ol>
<li>
Rainer Burkard, Ulrich Derigs,<br>
Assignment and Matching Problems: Solution methods with
FORTRAN programs,<br>
Lecture Notes in Economics and Mathematical Systems,<br>
Volume 184, <br>
Springer Verlag, 1980.
</li>
<li>
Nicos Christofides,<br>
Worst-case analysis of a new heuristic for the traveling salesman
problem,<br>
Management Science Research Report Number 388,<br>
Carnegie-Mellon University, 1976.
</li>
<li>
Frederick Hillier,<br>
Efficient heuristic procedure for integer linear programming
with an interior,<br>
Operations Research,<br>
Volume 17, pages 600-637, 1969.
</li>
<li>
Dorit Hochbaum, David Shmoys,<br>
A best possible heuristic for the K-center problem,<br>
Mathematics of Operations Research,<br>
Volume 10, pages 180-184, 1985.
</li>
<li>
Oscar Ibarra, Chul Kim,<br>
Fast approximation algorithms for the knapsack and sum of
subset problems,<br>
Journal of the Association for Computing Machinery,<br>
Volume 22, pages 463-468, 1975.
</li>
<li>
Brian Kernighan, Shen Lin,<br>
An efficient heuristic procedure for partitioning graphs,<br>
Bell System Technical Journal,<br>
Volume 49, pages 291-307, 1970.
</li>
<li>
Brian Kernighan, Shen Lin,<br>
Heuristic solution of a signal design optimization problem,<br>
Bell System Technical Journal,<br>
Volume 52, pages 1145-1159, 1973.
</li>
<li>
Lawrence Kou, George Markowsky, Leonard Berman,<br>
A fast algorithm for Steiner trees,<br>
Research report RC 7390,<br>
IBM Thomas J Watson Research Center,<br>
Yorktown Heights, New York, 1978.
</li>
<li>
Hang Tong Lau,<br>
Combinatorial Heuristic Algorithms in FORTRAN,<br>
Springer Verlag, 1986,<br>
ISBN: 3540171614,<br>
LC: QA402.5 L37.
</li>
<li>
Yoshiaki Toyoda,<br>
A simplified algorithm for obtaining approximate solutions
to zero-one programming problems,<br>
Management Science,<br>
Volume 21, pages 1417-1427, 1975.
</li>
</ol>
</p>
<h3 align = "center">
Source Code:
</h3>
<p>
<ul>
<li>
<a href = "lau_np.f90">lau_np.f90</a>, the source code.
</li>
<li>
<a href = "lau_np.sh">lau_np.sh</a>,
commands to compile the source code.
</li>
</ul>
</p>
<h3 align = "center">
Examples and Tests:
</h3>
<p>
<ul>
<li>
<a href = "lau_np_prb.f90">lau_np_prb.f90</a>, a sample problem.
</li>
<li>
<a href = "lau_np_prb.sh">lau_np_prb.sh</a>,
commands to compile, link and run the sample problem.
</li>
<li>
<a href = "lau_np_prb_output.txt">lau_np_prb_output.txt</a>,
the output file.
</li>
</ul>
</p>
<h3 align = "center">
List of Routines:
</h3>
<p>
<ul>
<li>
<b>GRAPH_ARC_EULER_CIRC</b> finds an Euler circuit in an Eulerian graph.
</li>
<li>
<b>GRAPH_ARC_MIN_PATH</b> finds the shortest path between two nodes.
</li>
<li>
<b>GRAPH_ARC_MIN_SPAN_TREE</b> finds a minimum spanning tree of a graph.
</li>
<li>
<b>GRAPH_ARC_PRINT</b> prints out a graph from an edge list.
</li>
<li>
<b>GRAPH_ARC_WEIGHT_PRINT</b> prints out a weighted graph from an edge list.
</li>
<li>
<b>GRAPH_DIST_MIN_SPAN_TREE3</b> finds a minimum spanning tree.
</li>
<li>
<b>GRAPH_DIST_PRINT</b> prints a distance matrix.
</li>
<li>
<b>I4_SWAP</b> switches two I4's.
</li>
<li>
<b>INT_LP</b> is a heuristic algorithm for the integer linear programming problem.
</li>
<li>
<b>K_CENTER</b> is a heuristic algorithm for the K-center problem.
</li>
<li>
<b>K_MEDIAN</b> is a heuristic algorithm for the K-median problem.
</li>
<li>
<b>KNAPSACK</b> is a heuristic algorithm for the zero-one knapsack problem.
</li>
<li>
<b>MULTI_KNAP</b> is a heuristic algorithm for the multi-dimensional 0/1 knapsack problem.
</li>
<li>
<b>PARSE1</b> is used by INT_LP.
</li>
<li>
<b>PARSE2</b> is used by INT_LP.
</li>
<li>
<b>PARSE3</b> is used by INT_LP.
</li>
<li>
<b>PARSE4</b> is used by INT_LP.
</li>
<li>
<b>PARSE5</b> is used by INT_LP.
</li>
<li>
<b>PARSE6</b> is used by INT_LP.
</li>
<li>
<b>PARSE7</b> is used by INT_LP.
</li>
<li>
<b>PARSE8</b> is used by INT_LP.
</li>
<li>
<b>PARTITION</b> is a heuristic algorithm for the graph partitioning problem.
</li>
<li>
<b>PMATCH</b> finds a minimum weight perfect matching in a graph.
</li>
<li>
<b>PMATCH_SUB_A</b> is used by PMATCH.
</li>
<li>
<b>PMATCH_SUB_B</b> is used by PMATCH.
</li>
<li>
<b>R8_SWAP</b> switches two R8's.
</li>
<li>
<b>R8MAT_PRINT</b> prints an R8MAT.
</li>
<li>
<b>R8MAT_PRINT_SOME</b> prints some of an R8MAT.
</li>
<li>
<b>R8VEC_SORT_HEAP_INDEX_A</b> does an indexed heap ascending sort of an R8VEC.
</li>
<li>
<b>R8VEC_SORT_HEAP_INDEX_D</b> does an indexed heap descending sort of an R8VEC.
</li>
<li>
<b>SIMPLEX</b> is used by INT_LP.
</li>
<li>
<b>STEINER</b> is a heuristic algorithm for the minimal Steiner tree problem.
</li>
<li>
<b>TIMESTAMP</b> prints the current YMDHMS date as a time stamp.
</li>
<li>
<b>TSP</b> is a heuristic algorithm for the traveling salesman problem.
</li>
</ul>
</p>
<p>
You can go up one level to <a href = "../f_src.html">
the FORTRAN90 source codes</a>.
</p>
<hr>
<i>
Last revised on 27 November 2006.
</i>
<!-- John Burkardt -->
</body>
</html>