Ⅰ Foundations 1
1 Introduction&Francesca Rossi，Peter van Beek，Toby Walsh 3
1.1 Purpose of the Handbook 4
1.2 Structure and Content 4
1.3 Future Research 10
2 Constraint Satisfaction：An Emerging Paradigm&Eugene C.Freuder and Alan K.Mackworth 13
2.1 The Early Days 13
2.2 The Constraint Satisfaction Problem：Representation and Reasoning 16
2.3 Conclusions 23
3 Constraint Propagation&Christian Bessiere 29
3.1 Background 30
3.2 Formal Viewpoint 33
3.3 Arc Consistency 37
3.4 Higher Order Consistencies 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 Specific Constraints 70
4 Backtracking Search Algorithms&Peter van Beek 85
4.1 Preliminaries 86
4.2 Branching Strategies 87
4.3 Constraint Propagation 90
4.4 Nogood Recording 96
4.5 Non-Chronological Backtracking 102
4.6 Heuristics for Backtracking Algorithms 105
4.7 Randomization and Restart Strategies 111
4.8 Best-First Search 116
4.9 Optimization 117
4.10 Comparing Backtracking Algorithms 118
5 Local Search Methods&Holger H.Hoos and Edward Tsang 135
5.1 Introduction 136
5.2 Randomised Iterative Improvement Algorithms 142
5.3 Tabu Search and Related Algorithms 144
5.4 Penalty-Based Local Search Algorithms 148
5.5 Other Approaches 154
5.6 Local Search for Constraint Optimisation Problems 155
5.7 Frameworks and Toolkits for Local Search 157
5.8 Conclusions and Outlook 158
6 Global Constraints&Willem-Jan van Hoeve and Irit Katriel 169
6.1 Notation and Preliminaries 170
6.2 Examples of Global Constraints 176
6.3 Complete Filtering Algorithms 182
6.4 Optimization Constraints 189
6.5 Partial Filtering Algorithms 193
6.6 Global Variables 200
6.7 Conclusion 203
7 Tractable Structures for Constraint Satisfaction Problems&Rina Dechter 209
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 and Bibliographical Notes 241
8 The Complexity of Constraint Languages&David Cohen and Peter Jeavons 245
8.1 Basic Definitions 246
8.2 Examples of Constraint Languages 247
8.3 Developing an Algebraic Theory 251
8.4 Applications of the Algebraic Theory 258
8.5 Constraint Languages Over an Infinite Set 263
8.6 Multi-Sorted Constraint Languages 264
8.7 Alternative Approaches 269
8.8 Future Directions 274
9 Soft Constraints&Pedro Meseguer，Francesca Rossi，Thomas Schiex 281
9.1 Background：Classical Constraints 282
9.2 Specific Frameworks 283
9.3 Generic Frameworks 287
9.4 Relations among Soft Constraint Frameworks 291
9.5 Search 297
9.6 Inference 300
9.7 Combining Search and Inference 313
9.8 Using Soft Constraints 316
9.9 Promising Directions for Further Research 321
10 Symmetry in Constraint Programming&Ian P.Gent，Karen E.Petrie，Jean-Francois Puget 329
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&Barbara M.Smith 377
11.1 Preliminaries 378
11.2 Representing a Problem 379
11.3 Propagation and Search 379
11.4 Viewpoints 381
11.5 Expressing the Constraints 382
11.6 Auxiliary Variables 386
11.7 Implied Constraints 387
11.8 Reformulations of CSPs 391
11.9 Combining Viewpoints 394
11.10 Symmetry and Modelling 398
11.11 Optimization Problems 400
11.12 Supporting Modelling and Reformulation 401
Ⅱ Extensions，Languages，and Applications 407
12 Constraint Logic Programming&Kim Marriott，Peter J.Stuckey，Mark Wallace 409
12.1 History of CLP 411
12.2 Semantics of Constraint Logic Programs 413
12.3 CLP for Conceptual Modeling 425
12.4 CLP for Design Modeling 430
12.5 Search in CLP 437
12.6 Impact of CLP 442
12.7 Future of CLP and Interesting Research Questions 444
13 Constraints in Procedural and Concurrent Languages&Thom Fruhwirth，Laurent Michel，and Christian Schulte 453
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&Christian Schulte and Mats Carlsson 495
14.1 Architecture for Constraint Programming Systems 496
14.2 Implementing Constraint Propagation 506
14.3 Implementing Search 513
14.4 Systems Overview 517
14.5 Outlook 519
15 Operations Research Methods in Constraint Programming&John N.Hooker 527
15.1 Schemes for Incorporating OR into CP 527
15.2 Plan of the Chapter 528
15.3 Linear Programming 530
15.4 Mixed Integer/Linear Modeling 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 Lagrangean Relaxation 547
15.9 Dynamic Programming 550
15.10 Branch-and-Price Methods 554
15.11 Benders Decomposition 556
15.12 Toward Integration of CP and OR 560
16 Continuous and Interval Constraints&Frederic Benhamou and Laurent Granvilliers 571
16.1 From Discrete to Continuous Constraints 574
16.2 The Branch-and-Reduce Framework 575
16.3 Consistency Techniques 577
16.4 Numerical Operators 583
16.5 Hybrid Techniques 587
16.6 First Order Constraints 590
16.7 Applications and Software packages 593
16.8 Conclusion 595
17 Constraints over Structured Domains&Carmen Gervet 605
17.1 History and Applications 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 Implementation Aspects 631
17.8 Applications 633
17.9 Further Topics 633
18 Randomness and Structure&Carla Gomes and Toby Walsh 639
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&Manolis Koubarakis 665
19.1 Preliminaries 666
19.2 Constraint-Based Formalisms for Reasoning About Time 669
19.3 Efficient Algorithms for Temporal CSPs 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&Boi Faltings 699
20.1 Definitions 701
20.2 Distributed Search 702
20.3 Improvements and Variants 713
20.4 Distributed Local Search 718
20.5 Open Constraint Programming 721
20.6 Further Issues 724
20.7 Conclusion 726
21 Uncertainty and Change&Kenneth N.Brown and Ian Miguel 731
21.1 Background and Definitions 732
21.2 Example：Course Scheduling 732
21.3 Uncertain Problems 733
21.4 Problems that Change 738
21.5 Pseudo-dynamic Formalisms 752
21.6 Challenges and Future Trends 753
21.7 Summary 755
22 Constraint-Based Scheduling and Planning&Philippe Baptiste，Philippe Laborie，Claude Le Pape，Wim Nuijten 761
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 Heuristic Search 789
22.6 Conclusions 794
23 Vehicle Routing&Philip Kilby and Paul Shaw 801
23.1 The Vehicle Routing Problem 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-VRP in the Real World 825
23.7 Conclusions 828
24 Configuration&Ulrich Junker 837
24.1 What Is Configuration？ 838
24.2 Configuration Knowledge 844
24.3 Constraint Models for Configuration 853
24.4 Problem Solving for Configuration 863
24.5 Conclusion 868
25 Constraint Applications in Networks&Helmut Simonis 875
25.1 Electricity Networks 876
25.2 Water（Oil）Networks 878
25.3 Data Networks 879
25.4 Conclusion 898
26 Bioinformatics and Constraints&Rolf Backofen and David Gilbert 905
26.1 What Biologists Want from Bioinformatics 906
26.2 The Central Dogma 907
26.3 A Classification of Problem Areas 908
26.4 Sequence Related Problems 908
26.5 Structure Related Problems 922
26.6 Function Related Problems 935
26.7 Microarrays 937
Index 945