Programming With Constraints

by Marriott, Kim; Stuckey, Peter J.

• ISBN13: 9780262133418
• ISBN10: 0262133415
• Format: Hardcover
• Copyright: 1998-03-13
• Publisher: Mit Pr

Summary

The job of the constraint programmer is to use mathematical constraints to model real world constraints and objects. In this book, Kim Marriott and Peter Stuckey provide the first comprehensive introduction to the discipline of constraint programming and, in particular, constraint logic programming. The book covers the necessary background material from artificial intelligence, logic programming, operations research, and mathematical programming. Topics discussed range from constraint-solving techniques to programming methodologies for constraint programming languages. Because there is not yet a universally used syntax for constraint logic programming languages, the authors present the programs in a way that is independent of any existing programming language. Practical exercises cover how to use the book with a number of existing constraint languages.

Table of Contents

Preface	xi
Introduction	1	(8)
Notes	6	(3)
I Constraints	9	(122)
1 Constraints	11	(40)
1.1 Constraints and Valuations	11	(4)
1.2 Modelling with Constraints	15	(3)
1.3 Constraint Satisfaction	18	(4)
1.4 Tree Constraints	22	(5)
1.5 Other Constraint Domains	27	(6)
1.6 Properties of Constraint Solvers	33	(2)
1.7 (*) Determined Variables and Local Propagation	35	(6)
1.8 Summary	41	(1)
1.9 Exercises	42	(1)
1.10 Practical Exercises	43	(4)
1.11 Notes	47	(4)
2 Simplification, Optimization and Implication	51	(34)
2.1 Constraint Simplification	51	(2)
2.2 Projection	53	(4)
2.3 Constraint Simplifiers	57	(4)
2.4 Optimization	61	(2)
2.5 The Simplex Algorithm	63	(9)
2.6 (*) Canonical Form Simplifiers	72	(3)
2.7 (*) Implication and Equivalence	75	(3)
2.8 Summary	78	(1)
2.9 Exercises	79	(1)
2.10 Practical Exercises	80	(3)
2.11 Notes	83	(2)
3 Finite Constraint Domains	85	(46)
3.1 Constraint Satisfaction Problems	86	(2)
3.2 A Simple Backtracking Solver	88	(3)
3.3 Node and Arc Consistency	91	(6)
3.4 Bounds Consistency	97	(12)
3.5 Generalized Consistency	109	(5)
3.6 Optimization for Arithmetic CSPs	114	(6)
3.7 Summary	120	(2)
3.8 Exercises	122	(1)
3.9 Practical Exercises	123	(4)
3.10 Notes	127	(4)
II Constraint Logic Programming	131	(258)
4 Constraint Logic Programs	133	(34)
4.1 User-Defined Constraints	133	(4)
4.2 Programming with Rules	137	(3)
4.3 Evaluation	140	(3)
4.4 Derivation Trees and Finite Failure	143	(3)
4.5 Goal Evaluation	146	(3)
4.6 Simplified Derivation Trees	149	(2)
4.7 The CLP Scheme	151	(2)
4.8 (*) Independence from Rule Ordering and Literal Selection	153	(5)
4.9 Summary	158	(1)
4.10 Exercises	158	(2)
4.11 Practical Exercises	160	(4)
4.12 Notes	164	(3)
5 Simple Modelling	167	(18)
5.1 Simple Modelling	167	(2)
5.2 Modelling Choice	169	(5)
5.3 Iteration	174	(5)
5.4 Optimization	179	(2)
5.5 Summary	181	(1)
5.6 Practical Exercises	181	(3)
5.7 Notes	184	(1)
6 Using Data Structures	185	(28)
6.1 Records	186	(2)
6.2 Lists	188	(5)
6.3 Association Lists	193	(5)
6.4 Binary Trees	198	(3)
6.5 Hierarchical Modelling	201	(2)
6.6 Tree Layout	203	(5)
6.7 Summary	208	(1)
6.8 Practical Exercises	208	(3)
6.9 Notes	211	(2)
7 Controlling Search	213	(38)
7.1 Estimating the Efficiency of a CLP Program	213	(4)
7.2 Controlling Search: An Example	217	(3)
7.3 Rule Ordering	220	(1)
7.4 Literal Ordering	220	(3)
7.5 Adding Redundant Constraints	223	(4)
7.6 Minimization	227	(3)
7.7 Identifying Deterministic Subgoals	230	(5)
7.8 An Extended Example: Bridge Building	235	(11)
7.9 Summary	246	(1)
7.10 Exercises	247	(1)
7.11 Practical Exercises	248	(2)
7.12 Notes	250	(1)
8 Modelling with Finite Domain Constraints	251	(42)
8.1 Domains and Labelling	252	(4)
8.2 Complex Constraints	256	(2)
8.3 Labelling	258	(8)
8.4 Different Problem Modellings	266	(6)
8.5 An Extended Example: Scheduling	272	(9)
8.6 (*) Arc Consistency	281	(3)
8.7 (*) Reified Constraints	284	(1)
8.8 Summary	285	(1)
8.9 Practical Exercises	286	(5)
8.10 Notes	291	(2)
9 Advanced Programming Techniques	293	(56)
9.1 Extending the Constraint Solver	293	(5)
9.2 Combined Symbolic and Arithmetic Reasoning	298	(3)
9.3 Programming Optimization	301	(6)
9.4 Higher-order Predicates	307	(2)
9.5 Negation	309	(4)
9.6 CLP Languages with Dynamic Scheduling	313	(7)
9.7 (*) Meta Programming	320	(4)
9.8 (*) Library Predicates	324	(18)
9.9 Summary	342	(1)
9.10 Practical Exercises	343	(3)
9.11 Notes	346	(3)
10 CLP Systems	349	(40)
10.1 Simple Backtracking Goal Evaluation	349	(3)
10.2 Incremental Constraint Solving	352	(6)
10.3 Efficient Saving and Restoring of the Constraint Store	358	(3)
10.4 Implementing If-Then-Else, Once and Negation	361	(5)
10.5 Optimization	366	(3)
10.6 Other Incremental Constraint Solvers	369	(7)
10.7 (*) Incremental Real Arithmetic Solving	376	(9)
10.8 Summary	385	(1)
10.9 Exercises	385	(2)
10.10 Notes	387	(2)
III Other Constraint Programming Languages	389	(60)
11 Constraint Databases	391	(34)
11.1 Modelling with Constraint Databases	391	(4)
11.2 Bottom Up Evaluation	395	(10)
11.3 Bottom-Up versus Top-Down	405	(2)
11.4 Mimicking Top-Down Evaluation Bottom-Up	407	(5)
11.5 (*) Improving Termination	412	(4)
11.6 (*) Relationship with Relational Databases	416	(5)
11.7 Summary	421	(1)
11.8 Exercises	422	(1)
11.9 Practical Exercises	422	(1)
11.10 Notes	423	(2)
12 Other Constraint Programming Languages	425	(24)
12.1 The CLP Paradigm	425	(2)
12.2 Concurrent Constraint Programming Languages	427	(3)
12.3 Constraint Handling Rules	430	(3)
12.4 Functional Languages	433	(3)
12.5 Term Rewriting	436	(3)
12.6 Imperative Programming Languages	439	(1)
12.7 Constraint Solving Toolkits	440	(3)
12.8 Mathematical Languages	443	(4)
12.9 Notes	447	(2)
References	449	(10)
Index	459