[下载]Elsevier06新书《约束规划手册》（Handbook of Constraint Programming）

8928

收藏 2007-10-14

Handbook of Constraint Programming (Foundations of Artificial Intelligence)约束规划对经济学的意义不言而喻，这本书涵括了约束规划的所有领域，特此推荐！<li><img class="bookDetail" height="226" alt="Handbook of Constraint Programming" src="http://img.ebooks.com/previews/000/000274/000274219/000274219-sml-1.jpg" width="161" style="; HEIGHT: 226px;"/> &nbsp;&nbsp;</li><li>AMAZON价格： <table class="product"><tbody><tr><td class="productLabel">List Price:</td><td class="listprice">$180.00 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</td></tr><tr><td class="productLabel">Price:</td><td>$169.20 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</td></tr></tbody></table></li><li>Hardcover: 978 pages &nbsp;&nbsp;</li>978 pages &nbsp;<li>Publisher: Elsevier Science (October 13, 2006) &nbsp;&nbsp;</li><li>Language: English </li><li>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 </li><li>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&cedil;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&acute;ed&acute;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</li><li>&nbsp;