Constraint Networks - Christophe Lecoutre

. .

Résumé :
..

Biographie:

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

Sommaire:
Acknowledgements 11 Notation 13 Main Acronyms 19 List of Algorithms 21 Introduction 27 Chapter 1. Constraint Networks 39 1.1 . Variables and constraints 39 1.2. Networks of variables and constraints . 51 1.2. Examples of constraint networks 65 1.4. Partial orders, decisions, nogoods and properties 74 1.5. Data structures to represent constraint networks 86 Chapter 2. Random and Structured Networks 93 2.1. Random constraint networks 94 2.2. Structured constraint networks 109 PART ONE. INFERENCE 133 Chapter 3. Consistencies 137 3.1. Basic consistencies 138 3.2. Stability of consistencies 143 3.3. Domain-filtering consistencies 150 3.4. Higher-order consistencies 162 3.5. Global consistency 173 3.6. Caveats about node, arc and path consistencies 184 Chapter 4. Generic GAC Algorithms 185 4.1.Coarse-grained propagation schemes 186 4.2. Iterating over valid tuples 97 4.3. GAC3 and GAC2001 200 4.4. More about general-purpose GAC algorithms 205 4.5. Improving the efficiency of generic GAC algorithms 214 4.6. Experimental results 233 4.7. Discussion 236 Chapter 5. Generalized Arc Consistency for Table Constraints 239 5.1. Classical schemes 240 5.2. Indexing-based approaches 244 5.3. Compression-based approaches 253 5.4. GAC-valid+allowed scheme 264 5.5. Simple tabular reduction 269 5.6. GACfor negative table constraints 279 5.7. Experimental results 283 5.8. Conclusion 286 Chapter 6. Singleton Arc Consistency 287 6.1. SAC1 and SAC2 289 6.2. SAC-Opt and SAC-SDS 290 6.3. SAC3 292 6.4. SAC3+ 296 6.5. Illustration 299 6.6. Weaker and stronger forms of SAC 300 6.7. Experimental results 313 6.8. Conclusion 316 Chapter 7. Path and Dual Consistency 319 7.1. Qualitative study 321 7.2. Enforcing (conservative) path consistency 331 7.3. Enforcing strong (conservative) dual consistency 336 7.4. Experimental results 348 7.5. Conclusion 353 PART TWO. SEARCH 355 Chapter 8. Backtrack Search 359 8.1. General description 361 8.2. Maintaining (generalized) arc consistency 367 8.3. Classical look-ahead and look-back schemes 370 8.4. Illustrations 378 8.5. The role of explanations 383 Chapter 9. Guiding Search toward Conflicts 391 9.1. Search-guiding heuristics 392 9.2. Adaptive heuristics 398 9.3. Strength of constraint weighting 405 9.4. Guiding search to culprit decisions 415 9.5. Conclusion 427 Chapter 10. Restarts and Nogood Recording 431 10.1. Restarting search 432 10.2. Nogood recording from restarts 436 10.3. Managing standard nogoods 441 10.4. Minimizing nogoods 450 10.5. Experimental results 454 10.6. Conclusion 457 Chapter 11. State-based Reasoning 459 11.1. Inconsistent partial states 460 11.2. Learning from explanations and failed values 470 11.3. Reducing elementary inconsistent partial states 476 11.4. Equivalence detection 487 11.5. Experimental results 492 11.6. Conclusion 494 Chapter 12. Symmetry Breaking 495 Christophe LECOUTRE, Sebastien TABARY 12.1. Group theory 496 12.2. Symmetries on constraint networks 499 12.3. Symmetry-breaking methods 503 12.4. Automatic symmetry detection 508 12.5. Lightweight detection of variable symmetries 511 12.6. A GAC algorithm for lexicographic ordering constraints 520 12.7. Experimental results 527 Appendices 531 Bibliography 547 Index 571