Handbook of Constraint Programming

Francesca Rossi, Peter van Beek and Toby Walsh (Eds.)9780444527264, 0444527265

Handbook of Constraint ProgrammingEdited byFrancesca Rossi, University of Padova, ItalyPeter van Beek, University of Waterloo, CanadaToby Walsh, National ICT Australia & University of New South Wales, Australia”This encyclopedic work covers twenty-plus years of research in constraint programming in a readable, accessible and appealing way. For someone outside the field wondering what Constraint Programming is all about, this is the perfect introduction, and the book will remain useful as a reference for years.- Michael Trick, Professor of Operations Research, Tepper School of Business, Carnegie Mellon University”This book is an impressive and comprehensive coverage of Constraint Programming. The authors, many of whom are key contributors to the subjects described, have done a great job to make the important and interesting material accessible. A must-read for newcomers, and a must-have for the converts.- Joxan Jaffar, Professor and Dean, School of Computing, National University of Singapore”This handbook captures the breadth and sophistication of the field of constraint programming (CP), a rapidly growing area of research with significant academic and commercial impact. The editors and contributors provide an outstanding overview of the core and cutting edge techniques in the field. This handbook will be essential to all CP researchers and practitioners. It will also be a great guide for researchers from related fields, such as optimization and operations research.- Bart Selman, Professor of Computer Science, Cornell UniversityConstraint programming is a powerful paradigm for solving combinatorial andnumerical problems that draws on a wide range of techniques from artificial intelligence, computer science, databases, programming languages, and operations research. Constraint programming is currently applied with success to many domains, such as scheduling, planning, vehicle routing, configuration, networks, and bioinformatics.The aim of this handbook is to capture the full breadth and depth of the field of constraint programming and to be encyclopedic in its scope and coverage. Each chapter of the handbook is a self-contained survey of a topic, and is written by one or more authors who are leading researchers in the area.The intended audience of the handbook is researchers, graduate students, upper-year undergraduates, and practitioners who wish to learn about the state-of-the-art in constraint programming. No prior knowledge about the field is necessary to be able to read the chapters and gather useful knowledge. Researchers from other fields will find the handbook an effective way to learn about constraint programming and to be able to use constraint programming concepts and techniques in their own work.

---

Table of contents :
Content:
Foundations of Artificial Intelligence
Page ii

Front Matter
Page iii

Copyright page
Page iv

Foreword
Pages v-vi
Ugo Montanari

Editors
Page vii

Contributors
Pages ix-xi

Chapter 1 – Introduction
Pages 3-12
Francesca Rossi, Peter van Beek, Toby Walsh

Chapter 2 – Constraint Satisfaction: An Emerging Paradigm
Pages 13-27
Eugene C. Freuder, Alan K. Mackworth

Chapter 3 – Constraint Propagation
Pages 29-83
Christian Bessiere

Chapter 4 – Backtracking Search Algorithms
Pages 85-134
Peter van Beek

Chapter 5 – Local Search Methods
Pages 135-167
Holger H. Hoos, Edward Tsang

Chapter 6 – Global Constraints
Pages 169-208
Willem-Jan van Hoeve, Irit Katriel

Chapter 7 – Tractable Structures for Constraint Satisfaction Problems
Pages 209-244
Rina Dechter

Chapter 8 – The Complexity of Constraint Languages
Pages 245-280
David Cohen, Peter Jeavons

Chapter 9 – Soft Constraints
Pages 281-328
Pedro Meseguer, Francesca Rossi, Thomas Schiex

Chapter 10 – Symmetry in Constraint Programming
Pages 329-376
Ian P. Gent, Karen E. Petrie, Jean-François Puget

Chapter 11 – Modelling
Pages 377-406
Barbara M. Smith

Chapter 12 – Constraint Logic Programming
Pages 409-452
Kim Marriott, Peter J. Stuckey, Mark Wallace

Chapter 13 – Constraints in Procedural and Concurrent Languages
Pages 453-494
Thom Frühwirth, Laurent Michel, Christian Schulte

Chapter 14 – Finite Domain Constraint Programming Systems
Pages 495-526
Christian Schulte, Mats Carlsson

Chapter 15 – Operations Research Methods in Constraint Programming
Pages 527-570
John N. Hooker

Chapter 16 – Continuous and Interval Constraints
Pages 571-603
Frédéric Benhamou, Laurent Granvilliers

Chapter 17 – Constraints over Structured Domains
Pages 605-638
Carmen Gervet

Chapter 18 – Randomness and Structure
Pages 639-664
Carla Gomes, Toby Walsh

Chapter 19 – Temporal CSPs
Pages 665-697
Manolis Koubarakis

Chapter 20 – Distributed Constraint Programming
Pages 699-729
Boi Faltings

Chapter 21 – Uncertainty and Change
Pages 731-760
Kenneth N. Brown, Ian Miguel

Chapter 22 – Constraint-Based Scheduling and Planning
Pages 761-799
Philippe Baptiste, Philippe Laborie, Claude Le Pape, Wim Nuijten

Chapter 23 – Vehicle Routing
Pages 801-836
Philip Kilby, Paul Shaw

Chapter 24 – Configuration
Pages 837-873
Ulrich Junker

Chapter 25 – Constraint Applications in Networks
Pages 875-903
Helmut Simonis

Chapter 26 – Bioinformatics and Constraints
Pages 905-944
Rolf Backofen, David Gilbert

Index
Pages 945-955