Constraint Networks – Targeting Simplicity for Techniques and Algorithms

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