Modern heuristic techniques for combinatorial problems. (English) Zbl 0942.90500

New York, NY: Halstead Press (Wiley). xiv, 320 p. (1993).

Contents: Colin R. Reeves and John E. Beasley, Introduction (1–19); Kathryn A. Dowsland, Simulated annealing (20–69); Fred Glover and Manuel Laguna, Tabu search (70–150); Colin R. Reeves, Genetic algorithms (151–196); Carsten Peterson and Bo Soderberg, Artificial neural networks (197–242); John E. Beasley, Lagrangean relaxation (243–303); Colin R. Reeves, Evaluation of heuristic performance (304–315).
The past few years have seen an explosion of directions for heuristically solving combinatorial optimization problems. Techniques such as simulated annealing, tabu search, genetic algorithms, and neural networks have offered the hope of providing a general method for solving a range of problems. This collection of survey papers attempts to delineate the current state of the art. In addition to the above topics, there is also a chapter on Lagrangean relaxation, which while somewhat older, is still used in many applications. Each survey comes with a reasonably extensive bibliography that outlines the variety of problems that have been solved with the technique. The surveys themselves contain few computational results, though a short concluding chapter discusses issues in computational testing.
While the book does contain surveys by different authors, it is obvious that the authors and editor had set up an overall structure, since all the papers are written at roughly the same level (which is an advantage: all of these papers can be understood by practitioners). Overall, the surveys are good introductions to the techniques and the applications provide sufficient pointers to the literature for further information.

Reviewer: Michael A. Trick (MR 94h:90002)

MSC:

90-06	Proceedings, conferences, collections, etc. pertaining to operations research and mathematical programming
90C59	Approximation methods and heuristics in mathematical programming
90C27	Combinatorial optimization
00B15	Collections of articles of miscellaneous specific interest
68R05	Combinatorics in computer science
90C10	Integer programming

Keywords:

Modern heuristic techniques; Combinatorial problems; simulated annealing; tabu search; genetic algorithms; neural networks; Lagrangean relaxation; collection of survey papers

Software:

OR-Library