Handbook of Constraint Programming

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

Constraint programming is a powerful paradigm for solving combinatorial search 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 constraint programming field and to be encyclopedic in its scope and coverage. While there are several excellent books on constraint programming, such books necessarily focus on the main notions and techniques and cannot cover also extensions, applications, and languages. The handbook gives a reasonably complete coverage of all these lines of work, based on constraint programming, so that a reader can have a rather precise idea of the whole field and its potential. Of course each line of work is dealt with in a survey-like style, where some details may be neglected in favor of coverage. However, the extensive bibliography of each chapter will help the interested readers to find suitable sources for the missing details. Each chapter of the handbook is intended to be 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, higher-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 should find in this handbook an effective way to learn about constraint programming and to possibly use some of the constraint programming concepts and techniques in their work, thus providing a means for a fruitful cross-fertilization among different research areas. The handbook is organized in two parts. The first part covers the basic foundations of constraint programming, including the history, the notion of constraint propagation, basic search methods, global constraints, tractability and computational complexity, and important issues in modeling a problem as a constraint problem. The second part covers constraint languages and solver, several useful extensions to the basic framework (such as interval constraints, structured domains, and distributed CSPs), and successful application areas for constraint programming. – Covers the whole field of constraint programming – Survey-style chapters – Five chapters on applications

---

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