METAHEURISTICS:
COMPUTER DECISION-MAKING
PREFACE
Combinatorial optimization is the
process of finding the best,
or optimal, solution for problems with a discrete set of feasible solutions. Applications arise in numerous settings
involving operations
management and logistics, such as routing, scheduling, packing, inventory and production
management, location, logic,
and assignment of resources.
The economic impact of combinatorial optimization is profound, affecting sectors as diverse as transportation (airlines,
trucking, rail, and
shipping), forestry, manufacturing, logistics, aerospace, energy (electrical power, petroleum,
and natural gas),
telecommunications, biotechnology, financial services, and agriculture.
While much progress has been made in finding exact (provably optimal)
solutions to some combinatorial optimization problems, using techniques
such as dynamic programming, cutting planes, and branch and cut methods,
many hard combinatorial problems are still not solved exactly and
require good heuristic methods. Moreover, reaching "optimal solutions"
is in many cases meaningless, as in practice we are often dealing with
models that are rough simplifications of reality. The aim of heuristic
methods for combinatorial optimization is to quickly produce
good-quality solutions, without necessarily providing any guarantee of
solution quality. Metaheuristics are high level procedures that
coordinate simple heuristics, such as local search, to find solutions
that are of better quality than those found by the simple heuristics
alone. Modern metaheuristics include simulated annealing, genetic
algorithms, tabu search, GRASP, scatter search, ant colony optimization,
variable neighborhood search, and their hybrids. In many practical
problems they have proved to be effective and efficient approaches, being
flexible to accommodate variations in problem structure and in the
objectives considered for the evaluation of solutions. For all these
reasons, metaheuristics have probably been one of the most stimulating
research topics in optimization for the last two decades.
Metaheuristics: Computer
Decision-Making grew out of the 4th
Metaheuristics International Conference (MIC2001), held in Porto,
Portugal, on July 16-20, 2001, and chaired by Jorge Pinho de Sousa.
Kluwer Academic Publishers published three books developed from previous
editions of the Metaheuristic International Conference (MIC'95: I.H.
Osman and J.P. Kelly (eds.), Meta-heuristics:
Theory and Applications, Kluwer, 1996, held in Breckenridge,
United States, in 1995; MIC'97: S. Voss, S. Martello, I.H. Osman,
and C. Roucairol (eds.), Meta-heuristics:
Advances and Trends in Local Search Paradigms for Optimization, Kluwer,
1999, held in Sophia-Antipolis, France, in 1997; and MIC'99:
C.C. Ribeiro and P. Hansen (eds.), Essays
and Surveys in Metaheuristics, Kluwer, 2002, held in Angra dos
Reis, Brazil, in 1999). Though this book is not a conference
proceedings, it does characterize the type of research presented at
MIC2001.
Metaheuristics: Computer
Decision-Making exemplifies how much the field has matured in the
last few years. The volume has 33 papers, covering a broad range of
metaheuristics and related topics, as well as applications.
Metaheuristics and related topics include:
- genetic algorithms: Chapters
6, 9, 10, 13, 14, 17, 20, 21, and 24;
- tabu search: Chapters 15,
18, 27, 28, and 31;
- greedy randomized adaptive
search procedures (GRASP): Chapters 26, 28, 30, and 31;
- local search: Chapters 19,
25, 27, and 32;
- path-relinking: Chapters 1,
28, and 30;
- ant colony systems: Chapters
5, 22, and 33;
- memetic algorithms: Chapters
4 and 29;
- variable neighborhood
search: Chapters 7 and 23;
- simulated annealing:
Chapters 16 and 21;
- neural networks: Chapters 8
and 20;
- population reinforcement
optimization based exploration (PROBE): Chapter 2;
- Lagrangian heuristics:
Chapter 3;
- scatter search: Chapter 13;
and
- constraint programming:
Chapter 25.
Applications and problems types include:
assignment
and partitioning problems:
- generalized assignment:
Chapter 1,
- quadratic assignment:
Chapter 12,
- linear assignment: Chapter
22,
- number partitioning: Chapter
4,
- multi-constraint knapsack:
Chapter 2, and
- linear ordering: Chapter 3;
scheduling:
- nurse rostering: Chapter 7,
- school timetabling: Chapters
8 and 31,
- discrete-continuous
scheduling: Chapter 18, and
- discrete-lot sizing and
scheduling: Chapter 27;
tree
and graph problems:
- Steiner problem in graphs:
Chapter 28,
- communication network
design: Chapter 29,
- capacitated minimum spanning
tree: Chapter 30,
- k-cardinality tree: Chapter 23,
- graph drawing: Chapter 19,
and
- graph coloring: Chapter 15;
statistics:
- least squares estimation:
Chapter 6, and
- generalized vector-valued
regression: Chapter 20;
cutting
problems:
- strip packing with
guillotine patterns: Chapter 24, and
- cutting stock: Chapter 32;
mathematical
programming:
- multiobjective optimization:
Chapter 10,
- integer programming: Chapter
26, and
- minimax problem: Chapter 17;
vehicle
routing: Chapters 5 and 33;
single source capacitated
location: Chapter 9;
industrial applications:
- power systems: Chapter 21,
- petroleum reservoir
optimization: Chapter 13, and
- classification from
biological databases: Chapter 16; and
heuristic
search software framework: Chapter 11.
The editors would like to thank the authors for their contributions,
the over 70 referees for their tireless effort and helpful suggestions,
Kluwer Academic Publishers for publishing the book, and Alec Resende and
Geraldo Veiga for assistance in producing the final camera-ready
manuscript.
Last, but not least, we are specially grateful to Ana Viana, for her
valuable support and tireless collaboration in the editorial work
involving the publication of this book.
Florham Park and Porto, April 2003
Mauricio G. C. Resende and Jorge Pinho de Sousa