Handbook of Constraint Programming

Front Cover

Title Page

Copyright Page

Foreword

Editors

Contributors

Table of Contents

Part I: Foundations

Chapter 1 Introduction

1.1 Purpose of the Handbook

1.2 Structure and Content

1.3 Future Research

Chapter 2 Constraint Satisfaction: An Emerging Paradigm

2.1 The Early Days

2.2 The Constraint Satisfaction Problem: Representation and Reasoning

2.3 Conclusions

Chapter 3 Constraint Propagation

3.1 Background

3.2 Formal Viewpoint

3.3 Arc Consistency

3.4 Higher Order Consistencies

3.5 Domain-Based Consistencies Stronger than AC

3.6 Domain-Based Consistencies Weaker than AC

3.7 Constraint Propagation as Iteration of Reduction Rules

3.8 Specific Constraints

Chapter 4 Backtracking Search Algorithms

4.1 Preliminaries

4.2 Branching Strategies

4.3 Constraint Propagation

4.4 Nogood Recording

4.5 Non-Chronological Backtracking

4.6 Heuristics for Backtracking Algorithms

4.7 Randomization and Restart Strategies

4.8 Best-First Search

4.9 Optimization

4.10 Comparing Backtracking Algorithms

Chapter 5 Local Search Methods

5.1 Introduction

5.2 Randomised Iterative Improvement Algorithms

5.3 Tabu Search and Related Algorithms

5.4 Penalty-Based Local Search Algorithms

5.5 Other Approaches

5.6 Local Search for Constraint Optimisation Problems

5.7 Frameworks and Toolkits for Local Search

5.8 Conclusions and Outlook

Chapter 6 Global Constraints

6.1 Notation and Preliminaries

6.2 Examples of Global Constraints

6.3 Complete Filtering Algorithms

6.4 Optimization Constraints

6.5 Partial Filtering Algorithms

6.6 Global Variables

6.7 Conclusion

Chapter 7 Tractable Structures for Constraint Satisfaction Problems

7.1 Background

7.2 Structure-Based Tractability in Inference

7.3 Trading Time and Space by Hybrids of Search and Inference

7.4 Structure-Based Tractability in Search

7.5 Summary and Bibliographical Notes

Chapter 8 The Complexity of Constraint Languages

8.1 Basic Definitions

8.2 Examples of Constraint Languages

8.3 Developing an Algebraic Theory

8.4 Applications of the Algebraic Theory

8.5 Constraint Languages Over an Infinite Set

8.6 Multi-Sorted Constraint Languages

8.7 Alternative Approaches

8.8 Future Directions

Chapter 9 Soft Constraints

9.1 Background: Classical Constraints

9.2 Specific Frameworks

9.3 Generic Frameworks

9.4 Relations among Soft Constraint Frameworks

9.5 Search

9.6 Inference

9.7 Combining Search and Inference

9.8 Using Soft Constraints

9.9 Promising Directions for Further Research

Chapter 10 Symmetry in Constraint Programming

10.1 Symmetries and Group Theory

10.2 Definitions

10.3 Reformulation

10.4 Adding Constraints Before Search

10.5 Dynamic Symmetry Breaking Methods

10.6 Combinations of Symmetry Breaking Methods

10.7 Successful Applications

10.8 Symmetry Expression and Detection

10.9 Further Research Themes

10.10 Conclusions

Chapter 11 Modelling

11.1 Preliminaries

11.2 Representing a Problem

11.3 Propagation and Search

11.4 Viewpoints

11.5 Expressing the Constraints

11.6 Auxiliary Variables

11.7 Implied Constraints

11.8 Reformulations of CSPs

11.9 Combining Viewpoints

11.10 Symmetry and Modelling

11.11 Optimization Problems

11.12 Supporting Modelling and Reformulation

Part II: Extensions, Languages, and Applications

Chapter 12 Constraint Logic Programming

12.1 History of CLP

12.2 Semantics of Constraint Logic Programs

12.3 CLP for Conceptual Modeling

12.4 CLP for Design Modeling

12.5 Search in CLP

12.6 Impact of CLP

12.7 Future of CLP and Interesting Research Questions

Chapter 13 Constraints in Procedural and Concurrent Languages

13.1 Procedural and Object-Oriented Languages

13.2 Concurrent Constraint Programming

13.3 Rule-Based Languages

13.4 Challenges and Opportunities

13.5 Conclusion

Chapter 14 Finite Domain Constraint Programming Systems

14.1 Architecture for Constraint Programming Systems

14.2 Implementing Constraint Propagation

14.3 Implementing Search

14.4 Systems Overview

14.5 Outlook

Chapter 15 Operations Research Methods in Constraint Programming

15.1 Schemes for Incorporating OR into CP

15.2 Plan of the Chapter

15.3 Linear Programming

15.4 Mixed Integer/Linear Modeling

15.5 Cutting Planes

15.6 Relaxation of Global Constraints

15.7 Relaxation of Piecewise Linear and Disjunctive Constraints

15.8 Lagrangean Relaxation

15.9 Dynamic Programming

15.10 Branch-and-Price Methods

15.11 Benders Decomposition

15.12 Toward Integration of CP and OR

Chapter 16 Continuous and Interval Constraints

16.1 From Discrete to Continuous Constraints

16.2 The Branch-and-Reduce Framework

16.3 Consistency Techniques

16.4 Numerical Operators

16.5 Hybrid Techniques

16.6 First Order Constraints

16.7 Applications and Software packages

16.8 Conclusion

Chapter 17 Constraints over Structured Domains

17.1 History and Applications

17.2 Constraints over Regular and Constructed Sets

17.3 Constraints over Finite Set Intervals

17.4 Influential Extensions to Subset Bound Solvers

17.5 Constraints over Maps, Relations and Graphs

17.6 Constraints over Lattices and Hierarchical Trees

17.7 Implementation Aspects

17.8 Applications

17.9 Further Topics

Chapter 18 Randomness and Structure

18.1 Random Constraint Satisfaction

18.2 Random Satisfiability

18.3 Random Problems with Structure

18.4 Runtime Variability

18.5 History

18.6 Conclusions

Chapter 19 Temporal CSPs

19.1 Preliminaries

19.2 Constraint-Based Formalisms for Reasoning About Time

19.3 Efficient Algorithms for Temporal CSPs

19.4 More Expressive Queries for Temporal CSPs

19.5 First-Order Temporal Constraint Languages

19.6 The Scheme of Indefinite Constraint Databases

19.7 Conclusions

Chapter 20 Distributed Constraint Programming

20.1 Definitions

20.2 Distributed Search

20.3 Improvements and Variants

20.4 Distributed Local Search

20.5 Open Constraint Programming

20.6 Further Issues

20.7 Conclusion

Chapter 21 Uncertainty and Change

21.1 Background and Definitions

21.2 Example: Course Scheduling

21.3 Uncertain Problems

21.4 Problems that Change

21.5 Pseudo-dynamic Formalisms

21.6 Challenges and Future Trends

21.7 Summary

Chapter 22 Constraint-Based Scheduling and Planning

22.1 Constraint Programming Models for Scheduling

22.2 Constraint Programming Models for Planning

22.3 Constraint Propagation for Resource Constraints

22.4 Constraint Propagation on Optimization Criteria

22.5 Heuristic Search

22.6 Conclusions

Chapter 23 Vehicle Routing

23.1 The Vehicle Routing Problem

23.2 Operations Research Approaches

23.3 Constraint Programming Approaches

23.4 Constraint Programming in Search

23.5 Using Constraint Programming as a Subproblem Solver

23.6 CP-VRP in the Real World

23.7 Conclusions

Chapter 24 Configuration

24.1 What Is Configuration?

24.2 Configuration Knowledge

24.3 Constraint Models for Configuration

24.4 Problem Solving for Configuration

24.5 Conclusion

Chapter 25 Constraint Applications in Networks

25.1 Electricity Networks

25.2 Water (Oil) Networks

25.3 Data Networks

25.4 Conclusion

Chapter 26 Bioinformatics and Constraints

26.1 What Biologists Want from Bioinformatics

26.2 The Central Dogma

26.3 A Classification of Problem Areas

26.4 Sequence Related Problems

26.5 Structure Related Problems

26.6 Function Related Problems

26.7 Microarrays

Index