Programming with Constraints: An Introduction

Cover......Page __sk_0000.djvu
Copyright......Page __sk_0002.djvu
Contents......Page __sk_0005.djvu
Preface......Page __sk_0009.djvu
Introduction......Page __sk_0015.djvu
Notes......Page __sk_0020.djvu
I Constraints......Page __sk_0023.djvu
1.1 Constraints and Valuations......Page __sk_0025.djvu
1.2 Modelling with Constraints......Page __sk_0029.djvu
1.3 Constraint Satisfaction......Page __sk_0032.djvu
1.4 Tree Constraints......Page __sk_0036.djvu
1.5 Other Constraint Domains......Page __sk_0041.djvu
1.6 Properties of Constraint Solvers......Page __sk_0047.djvu
1.7 (*) Determined Variables and Local Propagation......Page __sk_0049.djvu
1.8 Summary......Page __sk_0055.djvu
1.9 Exercises......Page __sk_0056.djvu
1.10 Practical Exercises......Page __sk_0057.djvu
1.11 Notes......Page __sk_0061.djvu
2.1 Constraint Simplification......Page __sk_0065.djvu
2.2 Projection......Page __sk_0067.djvu
2.3 Constraint Simplifiers......Page __sk_0071.djvu
2.4 Optimization......Page __sk_0075.djvu
2.5 The Simplex Algorithm......Page __sk_0077.djvu
2.6 (*) Canonical Form Simplifiers......Page __sk_0086.djvu
2.7 (*) Implication and Equivalence......Page __sk_0089.djvu
2.8 Summary......Page __sk_0092.djvu
2.9 Exercises......Page __sk_0093.djvu
2.10 Practical Exercises......Page __sk_0094.djvu
2.11 Notes......Page __sk_0097.djvu
3 Finite Constraint Domains......Page __sk_0099.djvu
3.1 Constraint Satisfaction Problems......Page __sk_0100.djvu
3.2 A Simple Backtracking Solver......Page __sk_0102.djvu
3.3 Node and Arc Consistency......Page __sk_0105.djvu
3.4 Bounds Consistency......Page __sk_0111.djvu
3.5 Generalized Consistency......Page __sk_0123.djvu
3.6 Optimization for Arithmetic CSPs......Page __sk_0128.djvu
3.7 Summary......Page __sk_0134.djvu
3.8 Exercises......Page __sk_0136.djvu
3.9 Practical Exercises......Page __sk_0137.djvu
3.10 Notes......Page __sk_0141.djvu
II Constraint Logic Programming......Page __sk_0145.djvu
4.1 User-Defined Constraints......Page __sk_0147.djvu
4.2 Programming with Rules......Page __sk_0151.djvu
4.3 Evaluation......Page __sk_0154.djvu
4.4 Derivation Trees and Finite Failure......Page __sk_0157.djvu
4.5 Goal Evaluation......Page __sk_0160.djvu
4.6 Simplified Derivation Trees......Page __sk_0163.djvu
4.7 The CLP Scheme......Page __sk_0165.djvu
4.8 (*) Independence from Rule Ordering and Literal Selection......Page __sk_0167.djvu
4.10 Exercises......Page __sk_0172.djvu
4.11 Practical Exercises......Page __sk_0174.djvu
4.12 Notes......Page __sk_0178.djvu
5.1 Simple Modelling......Page __sk_0181.djvu
5.2 Modelling Choice......Page __sk_0183.djvu
5.3 Iteration......Page __sk_0188.djvu
5.4 Optimization......Page __sk_0193.djvu
5.6 Practical Exercises......Page __sk_0195.djvu
5.7 Notes......Page __sk_0198.djvu
6 Using Data Structures......Page __sk_0199.djvu
6.1 Records......Page __sk_0200.djvu
6.2 Lists......Page __sk_0202.djvu
6.3 Association Lists......Page __sk_0207.djvu
6.4 Binary Trees......Page __sk_0212.djvu
6.5 Hierarchical Modelling......Page __sk_0215.djvu
6.6 Tree Layout......Page __sk_0217.djvu
6.8 Practical Exercises......Page __sk_0222.djvu
6.9 Notes......Page __sk_0225.djvu
7.1 Estimating the Efficiency of a CLP Program......Page __sk_0227.djvu
7.2 Controlling Search: An Example......Page __sk_0231.djvu
7.4 Literal Ordering......Page __sk_0234.djvu
7.5 Adding Redundant Constraints......Page __sk_0237.djvu
7.6 Minimization......Page __sk_0241.djvu
7.7 Identifying Deterministic Subgoals......Page __sk_0244.djvu
7.8 An Extended Example: Bridge Building......Page __sk_0249.djvu
7.9 Summary......Page __sk_0260.djvu
7.10 Exercises......Page __sk_0261.djvu
7.11 Practical Exercises......Page __sk_0262.djvu
7.12 Notes......Page __sk_0264.djvu
8 Modelling with Finite Domain Constraints......Page __sk_0265.djvu
8.1 Domains and Labelling......Page __sk_0266.djvu
8.2 Complex Constraints......Page __sk_0270.djvu
8.3 Labelling......Page __sk_0272.djvu
8.4 Different Problem Modellings......Page __sk_0280.djvu
8.5 An Extended Example: Scheduling......Page __sk_0286.djvu
8.6 (*) Arc Consistency......Page __sk_0295.djvu
8.7 (*) Reified Constraints......Page __sk_0298.djvu
8.8 Summary......Page __sk_0299.djvu
8.9 Practical Exercises......Page __sk_0300.djvu
8.10 Notes......Page __sk_0305.djvu
9.1 Extending the Constraint Solver......Page __sk_0307.djvu
9.2 Combined Symbolic and Arithmetic Reasoning......Page __sk_0312.djvu
9.3 Programming Optimization......Page __sk_0315.djvu
9.4 Higher-order Predicates......Page __sk_0321.djvu
9.5 Negation......Page __sk_0323.djvu
9.6 CLP Languages with Dynamic Scheduling......Page __sk_0327.djvu
9.7 (*) Meta Programming......Page __sk_0334.djvu
9.8 (*) Library Predicates......Page __sk_0338.djvu
9.9 Summary......Page __sk_0356.djvu
9.10 Practical Exercises......Page __sk_0357.djvu
9.11 Notes......Page __sk_0360.djvu
10.1 Simple Backtracking Goal Evaluation......Page __sk_0363.djvu
10.2 Incremental Constraint Solving......Page __sk_0366.djvu
10.3 Efficient Saving and Restoring of the Constraint Store......Page __sk_0372.djvu
10.4 Implementing If-Then-Else, Once and Negation......Page __sk_0375.djvu
10.5 Optimization......Page __sk_0380.djvu
10.6 Other Incremental Constraint Solvers......Page __sk_0383.djvu
10.7 (*) Incremental Real Arithmetic Solving......Page __sk_0390.djvu
10.9 Exercises......Page __sk_0399.djvu
10.10 Notes......Page __sk_0401.djvu
III Other Constraint Programming Languages......Page __sk_0403.djvu
11.1 Modelling with Constraint Databases......Page __sk_0405.djvu
11.2 Bottom Up Evaluation......Page __sk_0409.djvu
11.3 Bottom-Up versus Top-Down......Page __sk_0419.djvu
11.4 Mimicking Top-Down Evaluation Bottom-Up......Page __sk_0421.djvu
11.5 (*) Improving Termination......Page __sk_0426.djvu
11.6 (*) Relationship with Relational Databases......Page __sk_0430.djvu
11.7 Summary......Page __sk_0435.djvu
11.9 Practical Exercises......Page __sk_0436.djvu
11.10 Notes......Page __sk_0437.djvu
12.1 The CLP Paradigm......Page __sk_0439.djvu
12.2 Concurrent Constraint Programming Languages......Page __sk_0441.djvu
12.3 Constraint Handling Rules......Page __sk_0444.djvu
12.4 Functional Languages......Page __sk_0447.djvu
12.5 Term Rewriting......Page __sk_0450.djvu
12.6 Imperative Programming Languages......Page __sk_0453.djvu
12.7 Constraint Solving Toolkits......Page __sk_0454.djvu
12.8 Mathematical Languages......Page __sk_0457.djvu
12.9 Notes......Page __sk_0461.djvu
References......Page __sk_0463.djvu
Index......Page __sk_0473.djvu