Handbook of Constraint Programming (eBook)

Peter van Beek, Francesca Rossi, Toby Walsh (Herausgeber)

eBook Download: PDF

2006 | 1. Auflage
978 Seiten
Elsevier Science (Verlag)
9780080463803 (ISBN)

Infos

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

Inhalt

Front Cover 1
Title Page 4
Copyright Page 5
Foreword 6
Editors 8
Contributors 10
Table of Contents 14
Part I: Foundations 22
Chapter 1 Introduction 24
1.1 Purpose of the Handbook 25
1.2 Structure and Content 25
1.3 Future Research 31
Chapter 2 Constraint Satisfaction: An Emerging Paradigm 34
2.1 The Early Days 34
2.2 The Constraint Satisfaction Problem: Representation and Reasoning 37
2.3 Conclusions 44
Chapter 3 Constraint Propagation 50
3.1 Background 51
3.2 Formal Viewpoint 54
3.3 Arc Consistency 58
3.4 Higher Order Consistencies 71
3.5 Domain-Based Consistencies Stronger than AC 78
3.6 Domain-Based Consistencies Weaker than AC 83
3.7 Constraint Propagation as Iteration of Reduction Rules 89
3.8 Specific Constraints 91
Chapter 4 Backtracking Search Algorithms 106
4.1 Preliminaries 107
4.2 Branching Strategies 108
4.3 Constraint Propagation 111
4.4 Nogood Recording 117
4.5 Non-Chronological Backtracking 123
4.6 Heuristics for Backtracking Algorithms 126
4.7 Randomization and Restart Strategies 132
4.8 Best-First Search 137
4.9 Optimization 138
4.10 Comparing Backtracking Algorithms 139
Chapter 5 Local Search Methods 156
5.1 Introduction 157
5.2 Randomised Iterative Improvement Algorithms 163
5.3 Tabu Search and Related Algorithms 165
5.4 Penalty-Based Local Search Algorithms 169
5.5 Other Approaches 175
5.6 Local Search for Constraint Optimisation Problems 176
5.7 Frameworks and Toolkits for Local Search 178
5.8 Conclusions and Outlook 179
Chapter 6 Global Constraints 190
6.1 Notation and Preliminaries 191
6.2 Examples of Global Constraints 197
6.3 Complete Filtering Algorithms 203
6.4 Optimization Constraints 210
6.5 Partial Filtering Algorithms 214
6.6 Global Variables 221
6.7 Conclusion 224
Chapter 7 Tractable Structures for Constraint Satisfaction Problems 230
7.1 Background 231
7.2 Structure-Based Tractability in Inference 234
7.3 Trading Time and Space by Hybrids of Search and Inference 252
7.4 Structure-Based Tractability in Search 260
7.5 Summary and Bibliographical Notes 262
Chapter 8 The Complexity of Constraint Languages 266
8.1 Basic Definitions 267
8.2 Examples of Constraint Languages 268
8.3 Developing an Algebraic Theory 272
8.4 Applications of the Algebraic Theory 279
8.5 Constraint Languages Over an Infinite Set 284
8.6 Multi-Sorted Constraint Languages 285
8.7 Alternative Approaches 290
8.8 Future Directions 295
Chapter 9 Soft Constraints 302
9.1 Background: Classical Constraints 303
9.2 Specific Frameworks 304
9.3 Generic Frameworks 308
9.4 Relations among Soft Constraint Frameworks 312
9.5 Search 318
9.6 Inference 321
9.7 Combining Search and Inference 334
9.8 Using Soft Constraints 337
9.9 Promising Directions for Further Research 342
Chapter 10 Symmetry in Constraint Programming 350
10.1 Symmetries and Group Theory 352
10.2 Definitions 358
10.3 Reformulation 361
10.4 Adding Constraints Before Search 364
10.5 Dynamic Symmetry Breaking Methods 371
10.6 Combinations of Symmetry Breaking Methods 383
10.7 Successful Applications 384
10.8 Symmetry Expression and Detection 385
10.9 Further Research Themes 387
10.10 Conclusions 389
Chapter 11 Modelling 398
11.1 Preliminaries 399
11.2 Representing a Problem 400
11.3 Propagation and Search 400
11.4 Viewpoints 402
11.5 Expressing the Constraints 403
11.6 Auxiliary Variables 407
11.7 Implied Constraints 408
11.8 Reformulations of CSPs 412
11.9 Combining Viewpoints 415
11.10 Symmetry and Modelling 419
11.11 Optimization Problems 421
11.12 Supporting Modelling and Reformulation 422
Part II: Extensions, Languages, and Applications 428
Chapter 12 Constraint Logic Programming 430
12.1 History of CLP 432
12.2 Semantics of Constraint Logic Programs 434
12.3 CLP for Conceptual Modeling 446
12.4 CLP for Design Modeling 451
12.5 Search in CLP 458
12.6 Impact of CLP 463
12.7 Future of CLP and Interesting Research Questions 465
Chapter 13 Constraints in Procedural and Concurrent Languages 474
13.1 Procedural and Object-Oriented Languages 475
13.2 Concurrent Constraint Programming 486
13.3 Rule-Based Languages 494
13.4 Challenges and Opportunities 506
13.5 Conclusion 507
Chapter 14 Finite Domain Constraint Programming Systems 516
14.1 Architecture for Constraint Programming Systems 517
14.2 Implementing Constraint Propagation 527
14.3 Implementing Search 534
14.4 Systems Overview 538
14.5 Outlook 540
Chapter 15 Operations Research Methods in Constraint Programming 548
15.1 Schemes for Incorporating OR into CP 548
15.2 Plan of the Chapter 549
15.3 Linear Programming 551
15.4 Mixed Integer/Linear Modeling 555
15.5 Cutting Planes 557
15.6 Relaxation of Global Constraints 560
15.7 Relaxation of Piecewise Linear and Disjunctive Constraints 566
15.8 Lagrangean Relaxation 568
15.9 Dynamic Programming 571
15.10 Branch-and-Price Methods 575
15.11 Benders Decomposition 577
15.12 Toward Integration of CP and OR 581
Chapter 16 Continuous and Interval Constraints 592
16.1 From Discrete to Continuous Constraints 595
16.2 The Branch-and-Reduce Framework 596
16.3 Consistency Techniques 598
16.4 Numerical Operators 604
16.5 Hybrid Techniques 608
16.6 First Order Constraints 611
16.7 Applications and Software packages 614
16.8 Conclusion 616
Chapter 17 Constraints over Structured Domains 626
17.1 History and Applications 627
17.2 Constraints over Regular and Constructed Sets 630
17.3 Constraints over Finite Set Intervals 634
17.4 Influential Extensions to Subset Bound Solvers 640
17.5 Constraints over Maps, Relations and Graphs 649
17.6 Constraints over Lattices and Hierarchical Trees 652
17.7 Implementation Aspects 652
17.8 Applications 654
17.9 Further Topics 654
Chapter 18 Randomness and Structure 660
18.1 Random Constraint Satisfaction 661
18.2 Random Satisfiability 665
18.3 Random Problems with Structure 669
18.4 Runtime Variability 672
18.5 History 678
18.6 Conclusions 679
Chapter 19 Temporal CSPs 686
19.1 Preliminaries 687
19.2 Constraint-Based Formalisms for Reasoning About Time 690
19.3 Efficient Algorithms for Temporal CSPs 698
19.4 More Expressive Queries for Temporal CSPs 702
19.5 First-Order Temporal Constraint Languages 704
19.6 The Scheme of Indefinite Constraint Databases 706
19.7 Conclusions 712
Chapter 20 Distributed Constraint Programming 720
20.1 Definitions 722
20.2 Distributed Search 723
20.3 Improvements and Variants 734
20.4 Distributed Local Search 739
20.5 Open Constraint Programming 742
20.6 Further Issues 745
20.7 Conclusion 747
Chapter 21 Uncertainty and Change 752
21.1 Background and Definitions 753
21.2 Example: Course Scheduling 753
21.3 Uncertain Problems 754
21.4 Problems that Change 759
21.5 Pseudo-dynamic Formalisms 773
21.6 Challenges and Future Trends 774
21.7 Summary 776
Chapter 22 Constraint-Based Scheduling and Planning 782
22.1 Constraint Programming Models for Scheduling 784
22.2 Constraint Programming Models for Planning 792
22.3 Constraint Propagation for Resource Constraints 799
22.4 Constraint Propagation on Optimization Criteria 806
22.5 Heuristic Search 810
22.6 Conclusions 815
Chapter 23 Vehicle Routing 822
23.1 The Vehicle Routing Problem 823
23.2 Operations Research Approaches 825
23.3 Constraint Programming Approaches 830
23.4 Constraint Programming in Search 840
23.5 Using Constraint Programming as a Subproblem Solver 844
23.6 CP-VRP in the Real World 846
23.7 Conclusions 849
Chapter 24 Configuration 858
24.1 What Is Configuration? 859
24.2 Configuration Knowledge 865
24.3 Constraint Models for Configuration 874
24.4 Problem Solving for Configuration 884
24.5 Conclusion 889
Chapter 25 Constraint Applications in Networks 896
25.1 Electricity Networks 897
25.2 Water (Oil) Networks 899
25.3 Data Networks 900
25.4 Conclusion 919
Chapter 26 Bioinformatics and Constraints 926
26.1 What Biologists Want from Bioinformatics 927
26.2 The Central Dogma 928
26.3 A Classification of Problem Areas 929
26.4 Sequence Related Problems 929
26.5 Structure Related Problems 943
26.6 Function Related Problems 956
26.7 Microarrays 958
Index 966

Produkt-Details

• Erscheint lt. Verlag: 18.8.2006
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• Themenwelt: Informatik ► Theorie / Studium ► Künstliche Intelligenz / Robotik
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik
• ISBN-13: 9780080463803 / 9780080463803