Christophe Lecoutre

Constraint Networks

Targeting Simplicity for Techniques and Algorithms

• Gebundenes Buch

Produktbeschreibung

A major challenge in constraint programming is to develop efficient generic approaches to solve instances of the constraint satisfaction problem (CSP). With this aim in mind, this book provides an accessible synthesis of the author's research and work in this area, divided into four main topics: representation, inference, search, and learning. The results obtained and reproduced in this book have a wide applicability, regardless of the nature of the problem or the constraints involved, making it an extremely user-friendly resource for those involved in this field.

---

Hinweis: Dieser Artikel kann nur an eine deutsche Lieferadresse ausgeliefert werden.

Produktdetails

• Verlag: Wiley
• Seitenzahl: 320
• Erscheinungstermin: 1. September 2009
• Englisch
• Abmessung: 234mm x 163mm x 36mm
• Gewicht: 975g
• ISBN-13: 9781848211063
• ISBN-10: 1848211066
• Artikelnr.: 27879801

Autorenporträt

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

Inhaltsangabe

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, Sébastien 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

---

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, Sébastien 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