Search Methodologies

Edmund K. Burke · Graham Kendall

Editors

Search

Methodologies

Introductory Tutorials in Optimization

and Decision Support Techniques

Second Edition

Search Methodologies

Edmund K. Burke • Graham Kendall

Editors

Search Methodologies

Introductory Tutorials in Optimization and

Decision Support Techniques

Second Edition

123

Editors

Edmund K. Burke

University of Stirling

Cottrell Building

Scotland, United Kingdom

Graham Kendall

Vice-Provost (Research

and Knowledge Transfer)

University of Nottingham, Malaysia

and University of Nottingham, UK

Jalan Broga, Semenyih, Malaysia

ISBN 978-1-4614-6939-1 ISBN 978-1-4614-6940-7 (eBook)

DOI 10.1007/978-1-4614-6940-7

Springer New York Heidelberg Dordrecht London

Library of Congress Control Number: 2013944229

© Springer Science+Business Media New York 2014

This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of

the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,

broadcasting, reproduction on microfilms or in any other physical way, and transmission or information

storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology

now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection

with reviews or scholarly analysis or material supplied specifically for the purpose of being entered

and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of

this publication or parts thereof is permitted only under the provisions of the Copyright Law of the

Publisher’s location, in its current version, and permission for use must always be obtained from Springer.

Permissions for use may be obtained through RightsLink at the Copyright Clearance Center. Violations

are liable to prosecution under the respective Copyright Law.

The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication

does not imply, even in the absence of a specific statement, that such names are exempt from the relevant

protective laws and regulations and therefore free for general use.

While the advice and information in this book are believed to be true and accurate at the date of pub￾lication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any

errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect

to the material contained herein.

Printed on acid-free paper

Springer is part of Springer Science+Business Media (www.springer.com)

Foreword to the First Edition

This is not so much a foreword as a testimonial. As I embarked on the pleasant

journey of reading through the chapters of this book, I became convinced that this is

one of the best sources of introductory material on the search methodologies topic to

be found. The book’s subtitle, “Introductory Tutorials in Optimization and Decision

Support Techniques,” aptly describes its aim, and the editors and contributors to this

volume have achieved this aim with remarkable success.

The chapters in this book are exemplary in giving useful guidelines for imple￾menting the methods and frameworks described. They are tutorials in the way tuto￾rials ought to be designed. I found no chapter that did not contain interesting and

relevant information and found several chapters that can only be qualified as de￾lightful.

Those of us who have devoted a substantial portion of our energies to the study

and elaboration of search methodologies often wish we had a simple formula for

passing along the core notions to newcomers to the area. (I must confess, by the

way, that I qualify as a relative newcomer to some of the areas in this volume.)

While simplicity, like beauty, to some degree lies in the eyes of the beholder and no

universal or magical formula for achieving it exists, this book comes much closer

to reaching such a goal than I would have previously considered possible. It will

occupy a privileged position on my list of recommended reading for students and

colleagues who want to get a taste for the basics of search methodologies and who

have an interest in equipping themselves to probe more deeply.

If good books may be likened to ladders that help us ascend to higher rungs

of knowledge and understanding, we all know there are nevertheless many books

written in technical areas that seem to be more like stumbling blocks or at best

broken stepping stools that deposit us in isolated nooks offering no clear access to

continued means of ascent. Not so the present book. Its chapters lead to ideal sites

for continued exploration and offer compelling motivation for further pursuit of its

ideas and frameworks. If my reckoning is not completely amiss, those who read this

volume will find abundant reasons for sharing my conviction that we owe its editors

and authors a true debt of gratitude for putting this work together.

Boulder, CO, USA Fred Glover

v

Foreword to the Second Edition

It gives me great pleasure to write this short foreword to the second edition of this

outstanding book. The first edition established this volume as an important interna￾tional landmark in the exposition and explanation of computational search method￾ologies and associated issues. As its title indicates, it covers a broad and diverse

portfolio of search techniques from an interdisciplinary perspective in an extensive

and comprehensive way. In some ways, this is no surprise because the authors that

have been brought together in this volume truly represent a collection of the very

top figures in the field. It is an extremely impressive group of authors who have the

highest possible qualifications to present these chapters in a clear and authoritative

way.

As the editors have explained in the Introduction, decision support systems now

underpin the core of many modern management approaches in such diverse areas

as health care, commerce, industry, science, and government. In many everyday sit￾uations across many different working environments, the idea of taking important

managerial decisions without some kind of decision support system would be incon￾ceivable. Moreover, it is the techniques and methods that are introduced in this book

that often lie at the heart of the search engines upon which these decision support

systems depend. Thus, the book ideally fits the current needs of today’s increasingly

computer-driven world.

The aim of the book is clearly articulated in the Introduction. It aims to present

a series of well-written tutorials by the leading experts in their fields. Moreover, it

does this by covering practically the whole possible range of topics in the disci￾pline. It enables students and practitioners to study and appreciate the beauty and

the power of some of the computational search techniques that are able to effectively

navigate through search spaces that are sometimes inconceivably large.

I am convinced that this second edition will build on the success of the first

edition and that it will prove to be just as popular. Three main features of the volume

add significantly, in my opinion, to its appeal. These can be outlined as follows:

vii

viii Foreword to the Second Edition

• I have already referred to the set of excellent authors who have written the chap￾ters of the book, but I think that it is worth emphasizing how important this is.

All the authors are world-renowned experts in their field.

• There is full and complete coverage of the area of search methodologies. This

is complemented in the second edition by additional chapters on Scatter Search,

GRASP (Greedy Randomized Adaptive Search Procedures), and Very Large￾Scale Neighborhood Search. The choice of these additional chapters was inspired

and reflects the ever-changing nature and developing focus of the field.

• I particularly appreciate the uniform approach to the description of topics which

originate from such different disciplines as operations research, computer sci￾ence, mathematics, artificial intelligence, and others. Establishing this common

structure across such a large number of authors is testament to the skill and inter￾national standing of the editors. Their vision has been realized in an exceptional

introductory treatment of the field. I think that tricks of trade, examples, sources

of additional information, and the extensive list of appropriate references repre￾sent particularly useful resources, and I have regularly directed my own students

to them in the first edition. I expect to continue to do so with this new edition.

These features particularly add to the usefulness of the book either for self-study

or as the basis of a course in the topic.

To summarize, I highly recommend the book for those who require an introduc￾tion to the breadth of techniques and approaches that are represented by the field of

search methodologies. I have gained a lot of pleasure from reading through this new

edition, and I am sure that it will be a valuable resource to teachers, students, and

practitioners for many years to come.

Poznan, Poland Jacek Blazewicz

Preface to the First Edition

We first had the idea for this book over 3 years ago. It grew out of a one-day work￾shop entitled Introductory Tutorials in Search, Optimization and Decision Support

Methodologies (INTROS), which was held in Nottingham in August 2003. The aim

of the workshop was to deliver basic introductions to a broad spectrum of search

methodologies from across disciplinary boundaries. It was supported by the UK En￾gineering and Physical Sciences Research Council (EPSRC) and the London Math￾ematical Society (LMS) and was attended by over one hundred delegates from all

over the world. We were very fortunate to have 11 of the world’s leading scientists in

search methodologies presenting a range of stimulating and highly informative tu￾torials. All of the INTROS presenters have contributed to this volume, and we have

enhanced the content by inviting additional, specifically targeted, complementary

chapters. We are pleased to be able to present such a comprehensive, multidisci￾plinary collection of tutorials in this crucially important research area.

We would like to take this opportunity to thank the many people who have con￾tributed towards the preparation of this book. We owe a great debt of gratitude to

the authors of the chapters. As one would expect from such a distinguished group of

scientists, they have prepared their excellent contributions in a thoroughly reliable

and professional manner. Without them, of course, the book would not have been

possible. We are extremely grateful to our copy editor, Piers Maddox, who excelled

himself in bringing together, in one coherent structure, the various documents that

were sent to him. We are also very grateful to Gary Folven, Carolyn Ford, and their

staff at Springer who have provided us with invaluable advice and support during

every step of the way. We would like to offer our gratitude to Fred Glover for writing

the foreword for this book. His warm praise is particularly pleasing. A special thank

you should go to Emma-Jayne Dann and Alison Payne for all the administrative

support they have given us, both in the preparation of this volume and in the orga￾nization of the INTROS workshop that underpinned it. We are also very thankful

to EPSRC and LMS for the financial support they gave us to hold this workshop.

Finally, we offer a special thank you to the INTROS delegates for their enthusiasm

and their encouragement.

ix

x Preface to the First Edition

We hope you enjoy reading this volume as much as we have enjoyed putting it

together. We are already planning a second edition, and if you have any comments

which can help us improve the book, please do not hesitate to contact us. We would

welcome your advice.

Edmund K. Burke

Nottingham, UK Graham Kendall

Nottingham, UK

Preface to the Second Edition

The first edition of this book, which appeared in 2005, grew out of a 1-day work￾shop entitled Introductory Tutorials in Search, Optimization and Decision Support

Methodologies (INTROS), which was held in Nottingham, UK, in August 2003. It

had 19 chapters which gave broad coverage of the predominant search methodolo￾gies at the time.

This second edition contains updated versions of the chapters, and we have also

included three additional chapters (Scatter Search, Chap. 5; GRASP: Greedy Ran￾domized Adaptive Search Procedures, Chap. 11; and Very Large-Scale Neighbor￾hood Search, Chap. 13). These new chapters, along with the revised chapters, we

believe, provide significant insight to the most popular search methodologies that

are in use today.

There are many people that we need to thank. Without their help and support, this

book would not have been possible. We are grateful to Jacek Blazewicz for writing

such a generous and positive foreword for this second edition. We are deeply in￾debted to all the authors for their contributions and for their patience about the time

that it took to get this edition into press. The authors represent a distinguished group

of scientists who have all prepared, and updated, excellent contributions in a consci￾entious and professional way. We are also grateful to our excellent copy editor, Piers

Maddox. We recognize that we did not always provide him with the material in a

form that he would have preferred. However, he dealt with everything very quickly

and extremely dilligently. We would also like to extend our thanks to the staff at

Springer, particularly Matthew Amboy, who have supported the preparation of this

book from the very beginning.

We hope you enjoy reading this book and gain as much from it as we gained in

editing it.

Stirling, UK Edmund K. Burke

Nottingham, UK Graham Kendall

xi

Contents

1 Introduction ................................................ 1

Edmund K. Burke and Graham Kendall

2 Classical Techniques ......................................... 19

Kathryn A. Dowsland

3 Integer Programming ........................................ 67

Robert Bosch and Michael Trick

4 Genetic Algorithms .......................................... 93

Kumara Sastry, David E. Goldberg, and Graham Kendall

5 Scatter Search .............................................. 119

Manuel Laguna

6 Genetic Programming ....................................... 143

Riccardo Poli and John Koza

7 Artificial Immune Systems .................................... 187

Uwe Aickelin, Dipankar Dasgupta, and Feng Gu

8 Swarm Intelligence .......................................... 213

Daniel Merkle and Martin Middendorf

9 Tabu Search ................................................ 243

Michel Gendreau and Jean-Yves Potvin

10 Simulated Annealing......................................... 265

Emile Aarts, Jan Korst and Wil Michiels

11 GRASP: Greedy Randomized Adaptive Search Procedures ........ 287

Mauricio G.C. Resende and Celso C. Ribeiro

xiii

xiv Contents

12 Variable Neighborhood Search ................................ 313

Pierre Hansen and Nenad Mladenovic´

13 Very Large-Scale Neighborhood Search ......................... 339

Douglas S. Altner, Ravindra K. Ahuja, Özlem Ergun,

14 Constraint Programming ..................................... 369

Eugene C. Freuder and Mark Wallace

15 Multi-objective Optimization.................................. 403

Kalyanmoy Deb

16 Sharpened and Focused No Free Lunch and Complexity Theory .... 451

Darrell Whitley

17 Machine Learning ........................................... 477

Xin Yao and Yong Liu

18 Fuzzy Reasoning ............................................ 519

Costas P. Pappis and Constantinos I. Siettos

19 Rough-Set-Based Decision Support ............................ 557

Roman Słowinski, Salvatore Greco, and Benedetto Matarazzo ´

20 Hyper-heuristics ............................................ 611

Peter Ross

21 Approximations and Randomization ........................... 639

Carla P. Gomes and Ryan Williams

22 Fitness Landscapes .......................................... 681

Colin R. Reeves

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 707

and James B. Orlin