Handbook of constraint programmingPDF电子书下载

Ⅰ 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