Handbook of constraint programming2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

Handbook of constraint programmingPDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

Ⅰ Foundations1

1 Introduction&Francesca Rossi，Peter van Beek，Toby Walsh3

1.1 Purpose of the Handbook4

1.2 Structure and Content4

1.3 Future Research10

2 Constraint Satisfaction：An Emerging Paradigm&Eugene C.Freuder and Alan K.Mackworth13

2.1 The Early Days13

2.2 The Constraint Satisfaction Problem：Representation and Reasoning16

2.3 Conclusions23

3 Constraint Propagation&Christian Bessiere29

3.1 Background30

3.2 Formal Viewpoint33

3.3 Arc Consistency37

3.4 Higher Order Consistencies50

3.5 Domain-Based Consistencies Stronger than AC57

3.6 Domain-Based Consistencies Weaker than AC62

3.7 Constraint Propagation as Iteration of Reduction Rules68

3.8 Specific Constraints70

4 Backtracking Search Algorithms&Peter van Beek85

4.1 Preliminaries86

4.2 Branching Strategies87

4.3 Constraint Propagation90

4.4 Nogood Recording96

4.5 Non-Chronological Backtracking102

4.6 Heuristics for Backtracking Algorithms105

4.7 Randomization and Restart Strategies111

4.8 Best-First Search116

4.9 Optimization117

4.10 Comparing Backtracking Algorithms118

5 Local Search Methods&Holger H.Hoos and Edward Tsang135

5.1 Introduction136

5.2 Randomised Iterative Improvement Algorithms142

5.3 Tabu Search and Related Algorithms144

5.4 Penalty-Based Local Search Algorithms148

5.5 Other Approaches154

5.6 Local Search for Constraint Optimisation Problems155

5.7 Frameworks and Toolkits for Local Search157

5.8 Conclusions and Outlook158

6 Global Constraints&Willem-Jan van Hoeve and Irit Katriel169

6.1 Notation and Preliminaries170

6.2 Examples of Global Constraints176

6.3 Complete Filtering Algorithms182

6.4 Optimization Constraints189

6.5 Partial Filtering Algorithms193

6.6 Global Variables200

6.7 Conclusion203

7 Tractable Structures for Constraint Satisfaction Problems&Rina Dechter209

7.1 Background210

7.2 Structure-Based Tractability in Inference213

7.3 Trading Time and Space by Hybrids of Search and Inference231

7.4 Structure-Based Tractability in Search239

7.5 Summary and Bibliographical Notes241

8 The Complexity of Constraint Languages&David Cohen and Peter Jeavons245

8.1 Basic Definitions246

8.2 Examples of Constraint Languages247

8.3 Developing an Algebraic Theory251

8.4 Applications of the Algebraic Theory258

8.5 Constraint Languages Over an Infinite Set263

8.6 Multi-Sorted Constraint Languages264

8.7 Alternative Approaches269

8.8 Future Directions274

9 Soft Constraints&Pedro Meseguer，Francesca Rossi，Thomas Schiex281

9.1 Background：Classical Constraints282

9.2 Specific Frameworks283

9.3 Generic Frameworks287

9.4 Relations among Soft Constraint Frameworks291

9.5 Search297

9.6 Inference300

9.7 Combining Search and Inference313

9.8 Using Soft Constraints316

9.9 Promising Directions for Further Research321

10 Symmetry in Constraint Programming&Ian P.Gent，Karen E.Petrie，Jean-Francois Puget329

10.1 Symmetries and Group Theory331

10.2 Definitions337

10.3 Reformulation340

10.4 Adding Constraints Before Search343

10.5 Dynamic Symmetry Breaking Methods350

10.6 Combinations of Symmetry Breaking Methods362

10.7 Successful Applications363

10.8 Symmetry Expression and Detection364

10.9 Further Research Themes366

10.10 Conclusions368

11 Modelling&Barbara M.Smith377

11.1 Preliminaries378

11.2 Representing a Problem379

11.3 Propagation and Search379

11.4 Viewpoints381

11.5 Expressing the Constraints382

11.6 Auxiliary Variables386

11.7 Implied Constraints387

11.8 Reformulations of CSPs391

11.9 Combining Viewpoints394

11.10 Symmetry and Modelling398

11.11 Optimization Problems400

11.12 Supporting Modelling and Reformulation401

Ⅱ Extensions，Languages，and Applications407

12 Constraint Logic Programming&Kim Marriott，Peter J.Stuckey，Mark Wallace409

12.1 History of CLP411

12.2 Semantics of Constraint Logic Programs413

12.3 CLP for Conceptual Modeling425

12.4 CLP for Design Modeling430

12.5 Search in CLP437

12.6 Impact of CLP442

12.7 Future of CLP and Interesting Research Questions444

13 Constraints in Procedural and Concurrent Languages&Thom Fruhwirth，Laurent Michel，and Christian Schulte453

13.1 Procedural and Object-Oriented Languages454

13.2 Concurrent Constraint Programming465

13.3 Rule-Based Languages473

13.4 Challenges and Opportunities485

13.5 Conclusion486

14 Finite Domain Constraint Programming Systems&Christian Schulte and Mats Carlsson495

14.1 Architecture for Constraint Programming Systems496

14.2 Implementing Constraint Propagation506

14.3 Implementing Search513

14.4 Systems Overview517

14.5 Outlook519

15 Operations Research Methods in Constraint Programming&John N.Hooker527

15.1 Schemes for Incorporating OR into CP527

15.2 Plan of the Chapter528

15.3 Linear Programming530

15.4 Mixed Integer/Linear Modeling534

15.5 Cutting Planes536

15.6 Relaxation of Global Constraints539

15.7 Relaxation of Piecewise Linear and Disjunctive Constraints545

15.8 Lagrangean Relaxation547

15.9 Dynamic Programming550

15.10 Branch-and-Price Methods554

15.11 Benders Decomposition556

15.12 Toward Integration of CP and OR560

16 Continuous and Interval Constraints&Frederic Benhamou and Laurent Granvilliers571

16.1 From Discrete to Continuous Constraints574

16.2 The Branch-and-Reduce Framework575

16.3 Consistency Techniques577

16.4 Numerical Operators583

16.5 Hybrid Techniques587

16.6 First Order Constraints590

16.7 Applications and Software packages593

16.8 Conclusion595

17 Constraints over Structured Domains&Carmen Gervet605

17.1 History and Applications606

17.2 Constraints over Regular and Constructed Sets609

17.3 Constraints over Finite Set Intervals613

17.4 Influential Extensions to Subset Bound Solvers619

17.5 Constraints over Maps，Relations and Graphs628

17.6 Constraints over Lattices and Hierarchical Trees631

17.7 Implementation Aspects631

17.8 Applications633

17.9 Further Topics633

18 Randomness and Structure&Carla Gomes and Toby Walsh639

18.1 Random Constraint Satisfaction640

18.2 Random Satisfiability644

18.3 Random Problems with Structure648

18.4 Runtime Variability651

18.5 History657

18.6 Conclusions658

19 Temporal CSPs&Manolis Koubarakis665

19.1 Preliminaries666

19.2 Constraint-Based Formalisms for Reasoning About Time669

19.3 Efficient Algorithms for Temporal CSPs677

19.4 More Expressive Queries for Temporal CSPs681

19.5 First-Order Temporal Constraint Languages683

19.6 The Scheme of Indefinite Constraint Databases685

19.7 Conclusions691

20 Distributed Constraint Programming&Boi Faltings699

20.1 Definitions701

20.2 Distributed Search702

20.3 Improvements and Variants713

20.4 Distributed Local Search718

20.5 Open Constraint Programming721

20.6 Further Issues724

20.7 Conclusion726

21 Uncertainty and Change&Kenneth N.Brown and Ian Miguel731

21.1 Background and Definitions732

21.2 Example：Course Scheduling732

21.3 Uncertain Problems733

21.4 Problems that Change738

21.5 Pseudo-dynamic Formalisms752

21.6 Challenges and Future Trends753

21.7 Summary755

22 Constraint-Based Scheduling and Planning&Philippe Baptiste，Philippe Laborie，Claude Le Pape，Wim Nuijten761

22.1 Constraint Programming Models for Scheduling763

22.2 Constraint Programming Models for Planning771

22.3 Constraint Propagation for Resource Constraints778

22.4 Constraint Propagation on Optimization Criteria785

22.5 Heuristic Search789

22.6 Conclusions794

23 Vehicle Routing&Philip Kilby and Paul Shaw801

23.1 The Vehicle Routing Problem802

23.2 Operations Research Approaches804

23.3 Constraint Programming Approaches809

23.4 Constraint Programming in Search819

23.5 Using Constraint Programming as a Subproblem Solver823

23.6 CP-VRP in the Real World825

23.7 Conclusions828

24 Configuration&Ulrich Junker837

24.1 What Is Configuration？838

24.2 Configuration Knowledge844

24.3 Constraint Models for Configuration853

24.4 Problem Solving for Configuration863

24.5 Conclusion868

25 Constraint Applications in Networks&Helmut Simonis875

25.1 Electricity Networks876

25.2 Water（Oil）Networks878

25.3 Data Networks879

25.4 Conclusion898

26 Bioinformatics and Constraints&Rolf Backofen and David Gilbert905

26.1 What Biologists Want from Bioinformatics906

26.2 The Central Dogma907

26.3 A Classification of Problem Areas908

26.4 Sequence Related Problems908

26.5 Structure Related Problems922

26.6 Function Related Problems935

26.7 Microarrays937

Index945