Programming Constraint Services

by Schulte, Christian

• ISBN13: 9783540433712
• ISBN10: 3540433716
• Format: Paperback
• Copyright: 2002-05-01
• Publisher: Springer Verlag

Summary

This book is concerned with the architecture and implementation of constraint engines. The author's main contribution is that constraint services, such as search and combinators, are made programmable; this is achieved by devising computation spaces as simple abstractions for programming constraint services at a high level. State-of-the-art and novel search strategies such as visual interactive search and parallel search are covered.This book is indispensable reading for anyone seriously interested in constraint technology.

Table of Contents

Introduction	1	(8)
Constraint Programming	1	(1)
Motivation	2	(1)
Approach	3	(2)
Outline	5	(2)
Source Material	7	(2)
Constraint Programming	9	(6)
Constraints	9	(1)
Search	10	(3)
Programming	13	(2)
Introducing Oz Light	15	(14)
Overview	15	(1)
Oz Light: Basics	16	(4)
The Store	16	(1)
Threads	17	(1)
Statements	18	(2)
Oz Light Continued	20	(5)
Primitive Operations	20	(2)
Exceptions	22	(1)
Ports and Active Services	22	(2)
Finite Domain Constraints	24	(1)
Syntactic Convenience	25	(1)
Relation to Full Oz	26	(3)
Spaces for Search	29	(16)
Overview	29	(1)
Local Computation Spaces	30	(1)
Space Manipulation	31	(2)
Space Creation	31	(1)
Merging Spaces	32	(1)
Injecting into Spaces	33	(1)
Control and Status	33	(1)
Search	34	(6)
Alternatives	35	(1)
Distributable Spaces	36	(1)
Synchronizing on Stability	36	(1)
Committing to Alternatives	37	(1)
Cloning Spaces	37	(2)
Refining Commit	39	(1)
Situated Procedure Calls: Services Reconsidered	40	(1)
Previous Work: Solve Combinator	41	(1)
Summary	42	(3)
Search Engines	45	(10)
Depth-First Search	45	(2)
Simplifying Control: Exceptions	47	(1)
Binarization	47	(2)
Multiple Solutions	49	(1)
Explicit State Representation	49	(1)
Limited Discrepancy Search	50	(2)
Best-First Search	52	(3)
Best-Solution Search	55	(4)
Constraining Spaces	55	(1)
Iterative Best-Solution Search	56	(1)
Branch-and-Bound Best-Solution Search	56	(1)
An Alternative Formulation of BAB	57	(1)
Prune-Search: Generalizing BAB	57	(2)
Recomputation	59	(10)
Overview	59	(1)
Full Recomputation	60	(1)
Fixed Recomputation	61	(3)
Why Recomputation Matters	64	(1)
Adaptive Recomputation	65	(4)
Oz Explorer: Visual Search	69	(10)
Development of Constraint Programs	69	(1)
Example: Aligning for a Photo	70	(4)
Features	74	(1)
Implementation	75	(1)
Evaluation	76	(2)
Related Work	78	(1)
Distributed Search	79	(14)
Overview	79	(1)
Distributed Oz	80	(2)
Architecture	82	(4)
Cooperation	82	(2)
Worker	84	(1)
Manager	84	(1)
Best-Solution Search	85	(1)
Distributed Search Engines	86	(2)
Evaluation	88	(5)
Spaces for Combinators	93	(12)
Overview	93	(1)
Space Tree	94	(1)
Space Tree Manipulation	95	(4)
Space Creation	96	(1)
Merging Spaces	97	(2)
Injecting into Spaces	99	(1)
Control and Status	99	(5)
Stability	100	(2)
Status Variable	102	(1)
Debugging Support	103	(1)
Choice of Programming Language	104	(1)
Constraint Combinators	105	(12)
Introduction	105	(1)
Concurrent Negation	106	(1)
Generic Reification	107	(2)
Disjunction	109	(2)
Conditional	111	(2)
Andorra-Style Disjunction	113	(1)
Discussion and Evaluation	114	(3)
Implementing Oz Light	117	(4)
Overview	117	(1)
Synchronization	118	(1)
Store	118	(2)
Scheduler	120	(1)
Implementing Spaces	121	(22)
Overview	121	(1)
Space Tree	122	(8)
Nodes and Links	122	(1)
Threads	123	(1)
The Store: Model	124	(2)
The Store: Implementation	126	(4)
Stability	130	(3)
Runnable Threads	130	(1)
Globally Suspended Threads	131	(1)
Speculative Constraints	132	(1)
Local Threads	132	(1)
Checking Stability	132	(1)
Merge	133	(2)
Search	135	(2)
Choose and Commit	135	(1)
Cloning Spaces	136	(1)
Richer Basic Constraints	137	(2)
Variable Aliasing	137	(1)
Tree Constraints	138	(1)
Finite Domain Constraints	138	(1)
Ports	139	(1)
Performance Overview	140	(3)
Other Approaches to Search	143	(10)
Other Constraint Programming Systems	143	(2)
Comparison with Trailing	145	(6)
Expressiveness	145	(1)
Implementation Issues	146	(1)
Criteria and Examples	147	(1)
Copying	148	(1)
Copying versus Trailing	149	(1)
Recomputation versus Trailing	150	(1)
System Comparison	151	(2)
Conclusion	153	(4)
Main Contributions	153	(1)
Future Work	154	(3)
A. Benchmark Problems and Platforms	157	(4)
Benchmark Problems	157	(1)
Sequential Platform	158	(1)
Distributed Platform	159	(2)
References	161	(10)
Index	171