Hardcover: 978 pages
  978 pages
 
Publisher: Elsevier Science (October 13, 2006)
 
Language: English
Book Description
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
Contents
Foreword v
Editors vii
Contributors ix
Contents xiii
I Foundations 1
1 Introduction 3
Francesca Rossi, Peter van Beek, TobyWalsh
1.1 Purpose of the Handbook . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Structure andContent . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Future Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Constraint Satisfaction: An Emerging Paradigm 13
Eugene C. Freuder and Alan K. Mackworth
2.1 TheEarlyDays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 The Constraint Satisfaction Problem: Representation and Reasoning . . 16
2.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3 Constraint Propagation 29
Christian Bessiere
3.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 FormalViewpoint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 ArcConsistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 HigherOrderConsistencies . . . . . . . . . . . . . . . . . . . . . . . . 50
3.5 Domain-Based Consistencies Stronger than AC . . . . . . . . . . . . . 57
3.6 Domain-Based Consistencies Weaker than AC . . . . . . . . . . . . . . 62
3.7 Constraint Propagation as Iteration of Reduction Rules . . . . . . . . . . 68
3.8 SpecificConstraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4 Backtracking Search Algorithms 85
Peter van Beek
4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.2 BranchingStrategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.3 ConstraintPropagation . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.4 Nogood Recording . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.5 Non-Chronological Backtracking . . . . . . . . . . . . . . . . . . . . . 102
4.6 Heuristics for Backtracking Algorithms . . . . . . . . . . . . . . . . . . 105
4.7 RandomizationandRestartStrategies . . . . . . . . . . . . . . . . . . . 111
4.8 Best-FirstSearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
4.9 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.10 ComparingBacktrackingAlgorithms . . . . . . . . . . . . . . . . . . . 118
5 Local Search Methods 135
Holger H. Hoos and Edward Tsang
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.2 RandomisedIterative ImprovementAlgorithms . . . . . . . . . . . . . 142
5.3 TabuSearchandRelatedAlgorithms . . . . . . . . . . . . . . . . . . . 144
5.4 Penalty-Based Local Search Algorithms . . . . . . . . . . . . . . . . . 148
5.5 OtherApproaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
5.6 Local Search for Constraint Optimisation Problems . . . . . . . . . . . 155
5.7 Frameworks andToolkits forLocalSearch . . . . . . . . . . . . . . . . 157
5.8 Conclusions andOutlook . . . . . . . . . . . . . . . . . . . . . . . . . 158
6 Global Constraints 169
Willem-Jan van Hoeve and Irit Katriel
6.1 Notation and Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 170
6.2 ExamplesofGlobalConstraints . . . . . . . . . . . . . . . . . . . . . . 176
6.3 Complete Filtering Algorithms . . . . . . . . . . . . . . . . . . . . . . 182
6.4 Optimization Constraints . . . . . . . . . . . . . . . . . . . . . . . . . 189
6.5 Partial Filtering Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 193
6.6 GlobalVariables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
6.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
7 Tractable Structures for Constraint Satisfaction Problems 209
Rina Dechter
7.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
7.2 Structure-Based Tractability in Inference . . . . . . . . . . . . . . . . . 213
7.3 Trading Time and Space by Hybrids of Search and Inference . . . . . . 231
7.4 Structure-Based Tractability in Search . . . . . . . . . . . . . . . . . . 239
7.5 Summary andBibliographicalNotes . . . . . . . . . . . . . . . . . . . 241
8 The Complexity of Constraint Languages 245
David Cohen and Peter Jeavons
8.1 BasicDefinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
8.2 Examples of Constraint Languages . . . . . . . . . . . . . . . . . . . . 247
8.3 Developing an Algebraic Theory . . . . . . . . . . . . . . . . . . . . . 251
8.4 Applicationsof theAlgebraicTheory . . . . . . . . . . . . . . . . . . . 258
8.5 Constraint Languages Over an Infinite Set . . . . . . . . . . . . . . . . 263
8.6 Multi-Sorted Constraint Languages . . . . . . . . . . . . . . . . . . . . 264
8.7 AlternativeApproaches . . . . . . . . . . . . . . . . . . . . . . . . . . 269
8.8 FutureDirections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
9 Soft Constraints 281
Pedro Meseguer, Francesca Rossi, Thomas Schiex
9.1 Background: Classical Constraints . . . . . . . . . . . . . . . . . . . . 282
9.2 SpecificFrameworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
9.3 GenericFrameworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
9.4 Relations among Soft Constraint Frameworks . . . . . . . . . . . . . . 291
9.5 Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
9.6 Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
9.7 CombiningSearchandInference . . . . . . . . . . . . . . . . . . . . . 313
9.8 UsingSoftConstraints . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
9.9 Promising Directions for Further Research . . . . . . . . . . . . . . . . 321
10 Symmetry in Constraint Programming 329
Ian P. Gent, Karen E. Petrie, Jean-Franc¸ois Puget
10.1 Symmetries and Group Theory . . . . . . . . . . . . . . . . . . . . . . 331
10.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
10.3 Reformulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
10.4 Adding Constraints Before Search . . . . . . . . . . . . . . . . . . . . 343
10.5 Dynamic Symmetry Breaking Methods . . . . . . . . . . . . . . . . . . 350
10.6 Combinations of Symmetry Breaking Methods . . . . . . . . . . . . . . 362
10.7 Successful Applications . . . . . . . . . . . . . . . . . . . . . . . . . . 363
10.8 Symmetry Expression and Detection . . . . . . . . . . . . . . . . . . . 364
10.9 Further Research Themes . . . . . . . . . . . . . . . . . . . . . . . . . 366
10.10 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
11 Modelling 377
Barbara M. Smith
11.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
11.2 Representing a Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 379
11.3 Propagation andSearch . . . . . . . . . . . . . . . . . . . . . . . . . . 379
11.4 Viewpoints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
11.5 Expressing the Constraints . . . . . . . . . . . . . . . . . . . . . . . . 382
11.6 Auxiliary Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
11.7 ImpliedConstraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
11.8 Reformulations ofCSPs . . . . . . . . . . . . . . . . . . . . . . . . . . 391
11.9 CombiningViewpoints . . . . . . . . . . . . . . . . . . . . . . . . . . 394
11.10 Symmetry and Modelling . . . . . . . . . . . . . . . . . . . . . . . . . 398
11.11 Optimization Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 400
11.12 Supporting Modelling and Reformulation . . . . . . . . . . . . . . . . . 401
II Extensions, Languages, and Applications 407
12 Constraint Logic Programming 409
Kim Marriott, Peter J. Stuckey, MarkWallace
12.1 History ofCLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
12.2 Semantics of Constraint Logic Programs . . . . . . . . . . . . . . . . . 413
12.3 CLPforConceptualModeling . . . . . . . . . . . . . . . . . . . . . . . 425
12.4 CLPforDesignModeling . . . . . . . . . . . . . . . . . . . . . . . . . 430
12.5 SearchinCLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
12.6 Impact ofCLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
12.7 Future of CLP and Interesting Research Questions . . . . . . . . . . . . 444
13 Constraints in Procedural and Concurrent Languages 453
Thom Fr¨uhwirth, Laurent Michel, and Christian Schulte
13.1 Procedural and Object-Oriented Languages . . . . . . . . . . . . . . . . 454
13.2 Concurrent Constraint Programming . . . . . . . . . . . . . . . . . . . 465
13.3 Rule-Based Languages . . . . . . . . . . . . . . . . . . . . . . . . . . 473
13.4 Challenges and Opportunities . . . . . . . . . . . . . . . . . . . . . . . 485
13.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486
14 Finite Domain Constraint Programming Systems 495
Christian Schulte and Mats Carlsson
14.1 Architecture for Constraint Programming Systems . . . . . . . . . . . . 496
14.2 Implementing Constraint Propagation . . . . . . . . . . . . . . . . . . . 506
14.3 ImplementingSearch . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
14.4 SystemsOverview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
14.5 Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
15 Operations Research Methods in Constraint Programming 527
John N. Hooker
15.1 Schemes for IncorporatingORintoCP . . . . . . . . . . . . . . . . . . 527
15.2 Plan of theChapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
15.3 Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530
15.4 MixedInteger/LinearModeling . . . . . . . . . . . . . . . . . . . . . . 534
15.5 Cutting Planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536
15.6 Relaxation of Global Constraints . . . . . . . . . . . . . . . . . . . . . 539
15.7 Relaxation of Piecewise Linear and Disjunctive Constraints . . . . . . . 545
15.8 LagrangeanRelaxation . . . . . . . . . . . . . . . . . . . . . . . . . . 547
15.9 Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . 550
15.10 Branch-and-Price Methods . . . . . . . . . . . . . . . . . . . . . . . . 554
15.11 Benders Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . 556
15.12 Toward IntegrationofCPandOR . . . . . . . . . . . . . . . . . . . . . 560
16 Continuous and Interval Constraints 571
Fr´ed´eric Benhamou and Laurent Granvilliers
16.1 From Discrete to Continuous Constraints . . . . . . . . . . . . . . . . . 574
16.2 TheBranch-and-ReduceFramework . . . . . . . . . . . . . . . . . . . 575
16.3 ConsistencyTechniques . . . . . . . . . . . . . . . . . . . . . . . . . . 577
16.4 NumericalOperators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583
16.5 HybridTechniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587
16.6 FirstOrderConstraints . . . . . . . . . . . . . . . . . . . . . . . . . . 590
16.7 Applications andSoftware packages . . . . . . . . . . . . . . . . . . . 593
16.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595
17 Constraints over Structured Domains 605
Carmen Gervet
17.1 History andApplications . . . . . . . . . . . . . . . . . . . . . . . . . 606
17.2 Constraints over Regular and Constructed Sets . . . . . . . . . . . . . . 609
17.3 Constraints over Finite Set Intervals . . . . . . . . . . . . . . . . . . . . 613
17.4 Influential Extensions to Subset Bound Solvers . . . . . . . . . . . . . . 619
17.5 Constraints over Maps, Relations and Graphs . . . . . . . . . . . . . . . 628
17.6 Constraints over Lattices and Hierarchical Trees . . . . . . . . . . . . . 631
17.7 ImplementationAspects . . . . . . . . . . . . . . . . . . . . . . . . . . 631
17.8 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633
17.9 FurtherTopics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633
18 Randomness and Structure 639
Carla Gomes and TobyWalsh
18.1 Random Constraint Satisfaction . . . . . . . . . . . . . . . . . . . . . . 640
18.2 Random Satisfiability . . . . . . . . . . . . . . . . . . . . . . . . . . . 644
18.3 Random Problems with Structure . . . . . . . . . . . . . . . . . . . . . 648
18.4 Runtime Variability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651
18.5 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657
18.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658
19 Temporal CSPs 665
Manolis Koubarakis
19.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666
19.2 Constraint-Based Formalisms for Reasoning About Time . . . . . . . . 669
19.3 EfficientAlgorithms forTemporalCSPs . . . . . . . . . . . . . . . . . 677
19.4 More Expressive Queries for Temporal CSPs . . . . . . . . . . . . . . . 681
19.5 First-Order Temporal Constraint Languages . . . . . . . . . . . . . . . 683
19.6 The Scheme of Indefinite Constraint Databases . . . . . . . . . . . . . . 685
19.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 691
20 Distributed Constraint Programming 699
Boi Faltings
20.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 701
20.2 DistributedSearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702
20.3 Improvements andVariants . . . . . . . . . . . . . . . . . . . . . . . . 713
20.4 DistributedLocalSearch . . . . . . . . . . . . . . . . . . . . . . . . . 718
20.5 Open Constraint Programming . . . . . . . . . . . . . . . . . . . . . . 721
20.6 Further Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 724
20.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 726
21 Uncertainty and Change 731
Kenneth N. Brown and Ian Miguel
21.1 Background and Definitions . . . . . . . . . . . . . . . . . . . . . . . . 732
21.2 Example: Course Scheduling . . . . . . . . . . . . . . . . . . . . . . . 732
21.3 UncertainProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733
21.4 Problems thatChange . . . . . . . . . . . . . . . . . . . . . . . . . . . 738
21.5 Pseudo-dynamic Formalisms . . . . . . . . . . . . . . . . . . . . . . . 752
21.6 Challenges andFutureTrends . . . . . . . . . . . . . . . . . . . . . . . 753
21.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 755
22 Constraint-Based Scheduling and Planning 761
Philippe Baptiste, Philippe Laborie, Claude Le Pape, Wim Nuijten
22.1 Constraint Programming Models for Scheduling . . . . . . . . . . . . . 763
22.2 Constraint Programming Models for Planning . . . . . . . . . . . . . . 771
22.3 Constraint Propagation for Resource Constraints . . . . . . . . . . . . . 778
22.4 Constraint Propagation on Optimization Criteria . . . . . . . . . . . . . 785
22.5 HeuristicSearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 789
22.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 794
23 Vehicle Routing 801
Philip Kilby and Paul Shaw
23.1 TheVehicleRoutingProblem . . . . . . . . . . . . . . . . . . . . . . . 802
23.2 Operations Research Approaches . . . . . . . . . . . . . . . . . . . . . 804
23.3 Constraint Programming Approaches . . . . . . . . . . . . . . . . . . . 809
23.4 Constraint Programming in Search . . . . . . . . . . . . . . . . . . . . 819
23.5 Using Constraint Programming as a Subproblem Solver . . . . . . . . . 823
23.6 CP-VRPintheRealWorld . . . . . . . . . . . . . . . . . . . . . . . . 825
23.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 828
24 Configuration 837
Ulrich Junker
24.1 What Is Configuration? . . . . . . . . . . . . . . . . . . . . . . . . . . 838
24.2 ConfigurationKnowledge . . . . . . . . . . . . . . . . . . . . . . . . . 844
24.3 Constraint Models for Configuration . . . . . . . . . . . . . . . . . . . 853
24.4 ProblemSolving forConfiguration . . . . . . . . . . . . . . . . . . . . 863
24.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 868
25 Constraint Applications in Networks 875
Helmut Simonis
25.1 ElectricityNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 876
25.2 Water (Oil)Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 878
25.3 DataNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 879
25.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 898
26 Bioinformatics and Constraints 905
Rolf Backofen and David Gilbert
26.1 WhatBiologistsWant fromBioinformatics . . . . . . . . . . . . . . . . 906
26.2 TheCentralDogma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907
26.3 A Classification of Problem Areas . . . . . . . . . . . . . . . . . . . . 908
26.4 SequenceRelatedProblems . . . . . . . . . . . . . . . . . . . . . . . . 908
26.5 StructureRelatedProblems . . . . . . . . . . . . . . . . . . . . . . . . 922
26.6 FunctionRelatedProblems . . . . . . . . . . . . . . . . . . . . . . . . 935
26.7 Microarrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 937
Index 945