Constraint Networks

Christophe Lecoutre is Assistant Professor at the University of Artois, France.

• Acknowledgements 11Notation 13Main Acronyms 19List of Algorithms 21Introduction 27Chapter 1. Constraint Networks 391.1 . Variables and constraints 391.2. Networks of variables and constraints . 511.2. Examples of constraint networks 651.4. Partial orders, decisions, nogoods and properties 741.5. Data structures to represent constraint networks 86Chapter 2. Random and Structured Networks 932.1. Random constraint networks 942.2. Structured constraint networks 109PART ONE. INFERENCE 133Chapter 3. Consistencies 1373.1. Basic consistencies 1383.2. Stability of consistencies 1433.3. Domain-filtering consistencies 1503.4. Higher-order consistencies 1623.5. Global consistency 1733.6. Caveats about node, arc and path consistencies 184Chapter 4. Generic GAC Algorithms 1854.1.Coarse-grained propagation schemes 1864.2. Iterating over valid tuples 974.3. GAC3 and GAC2001 2004.4. More about general-purpose GAC algorithms 2054.5. Improving the efficiency of generic GAC algorithms 2144.6. Experimental results 2334.7. Discussion 236Chapter 5. Generalized Arc Consistency for Table Constraints 2395.1. Classical schemes 2405.2. Indexing-based approaches 2445.3. Compression-based approaches 2535.4. GAC-valid+allowed scheme 2645.5. Simple tabular reduction 2695.6. GACfor negative table constraints 2795.7. Experimental results 2835.8. Conclusion 286Chapter 6. Singleton Arc Consistency 2876.1. SAC1 and SAC2 2896.2. SAC-Opt and SAC-SDS 2906.3. SAC3 2926.4. SAC3+ 2966.5. Illustration 2996.6. Weaker and stronger forms of SAC 3006.7. Experimental results 3136.8. Conclusion 316Chapter 7. Path and Dual Consistency 3197.1. Qualitative study 3217.2. Enforcing (conservative) path consistency 3317.3. Enforcing strong (conservative) dual consistency 3367.4. Experimental results 3487.5. Conclusion 353PART TWO. SEARCH 355Chapter 8. Backtrack Search 3598.1. General description 3618.2. Maintaining (generalized) arc consistency 3678.3. Classical look-ahead and look-back schemes 3708.4. Illustrations 3788.5. The role of explanations 383Chapter 9. Guiding Search toward Conflicts 3919.1. Search-guiding heuristics 3929.2. Adaptive heuristics 3989.3. Strength of constraint weighting 4059.4. Guiding search to culprit decisions 4159.5. Conclusion 427Chapter 10. Restarts and Nogood Recording 43110.1. Restarting search 43210.2. Nogood recording from restarts 43610.3. Managing standard nogoods 44110.4. Minimizing nogoods 45010.5. Experimental results 45410.6. Conclusion 457Chapter 11. State-based Reasoning 45911.1. Inconsistent partial states 46011.2. Learning from explanations and failed values 47011.3. Reducing elementary inconsistent partial states 47611.4. Equivalence detection 48711.5. Experimental results 492  11.6. Conclusion 494Chapter 12. Symmetry Breaking 495Christophe LECOUTRE, Sébastien TABARY12.1. Group theory 49612.2. Symmetries on constraint networks 49912.3. Symmetry-breaking methods 50312.4. Automatic symmetry detection 50812.5. Lightweight detection of variable symmetries 51112.6. A GAC algorithm for lexicographic ordering constraints 52012.7. Experimental results 527Appendices 531Bibliography 547Index 571