Local Search Algorithms for Combinatorial Problems – Analysis, Improvements and New Applications

St├╝tzle, Th. G.
Pub. date
January 1999
220 of Dissertations in Artificial Intelligence
ISBN print
Artificial Intelligence, Computer & Communication Sciences, Computer Science

Many problems of enormous practical and theoretical importance are of combinatorial nature. Combinatorial problems are intriguing because they are easy to state but many of them are very difficult to solve they are NP-hard. Local search and extensions thereof based on metaheuristics, which have been developed at the interface between Artificial Intelligence and Operations Research, are among the best available techniques for obtaining high-quality solutions to large instances of NP-hard problems in a reasonable time.

This book presents contributions to several research aspects of metaheuristics. The contributions concern (i) the introduction of a new methodology for analyzing the run-time behavior of metaheuristics and, in general, randomized algorithms, (ii) the derivation of improved algorithmic variants for known metaheuristics, in particular for ant colony optimization and iterated local search, (iii) the exploration of new applications of specific metaheuristics, and (iv) the characterization of the run-time behavior of specific metaheuristics.

The achievements described in this book can be regarded as a further step towards achieving the goals of research on metaheuristics: the development of general and flexible, but at the same time powerful and efficient algorithms to approximately solve hard combinatorial problems.