Constraint Networks E-Book

Christophe Lecoutre

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 941

Veröffentlichungsjahr: 2013

Beschreibung

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 to be solved or the type of constraints involved, making it an extremely user-friendly resource for those involved in this field.

Leseprobe

Table of Contents

Acknowledgements

Notation

Main Acronyms

List of Algorithms

Introduction

I. Toward simplicity of use

II. Conceptual simplicity of techniques and algorithms

III. Organization of this book

IV. Introductory example

Chapter 1: Constraint Networks

1.1. Variables and constraints

1.2. Networks of variables and constraints

1.3. Examples of constraint networks

1.4. Partial orders, decisions, nogoods and properties

1.5. Data structures to represent constraint networks

Chapter 2: Random and Structured Networks

2.1. Random constraint networks

2.2. Structured constraint networks

PART ONE: Inference

Chapter 3: Consistencies

3.1. Basic consistencies

3.2. Stability of consistencies

3.3. Domain-filtering consistencies

3.4. Higher-order consistencies

3.5. Global consistency

3.6. Caveats about node, arc and path consistencies

Chapter 4: Generic GAC Algorithms

4.1. Coarse-grained propagation schemes

4.2. Iterating over valid tuples

4.3. GAC3 and GAC2001

4.4. More about general-purpose GAC algorithms

4.5. Improving the efficiency of generic GAC algorithms

4.6. Experimental results

4.7. Discussion

Chapter 5: Generalized Arc Consistency for Table Constraints

5.1. Classical schemes

5.2. Indexing-based approaches

5.3. Compression-based approaches

5.4. GAC-valid+allowed scheme

5.5. Simple tabular reduction

5.6. GAC for negative table constraints

5.7. Experimental results

5.8. Conclusion

Chapter 6: Singleton Arc Consistency

6.1. SAC1 and SAC2

6.2. SAC-Opt and SAC-SDS

6.3. SAC3

6.4. SAC3+

6.5. Illustration

6.6. Weaker and stronger forms of SAC

6.7. Experimental results

6.8. Conclusion

Chapter 7: Path and Dual Consistency

7.1. Qualitative study

7.2. Enforcing (conservative) path consistency

7.3. Enforcing strong (conservative) dual consistency

7.4. Experimental results

7.5. Conclusion

PART TWO: Search

Chapter 8: Backtrack Search

8.1. General description

8.2. Maintaining (generalized) arc consistency

8.3. Classical look-ahead and look-back schemes

8.4. Illustrations

8.5. The role of explanations

Chapter 9: Guiding Search toward Conflicts

9.1. Search-guiding heuristics

9.2. Adaptive heuristics

9.3. Strength of constraint weighting

9.4. Guiding search to culprit decisions

9.5. Conclusion

Chapter 10: Restarts and Nogood Recording

10.1. Restarting search

10.2. Nogood recording from restarts

10.3. Managing standard nogoods

10.4. Minimizing nogoods

10.5. Experimental results

10.6. Conclusion

Chapter 11: State-based Reasoning

11.1. Inconsistent partial states

11.2. Learning from explanations and failed values

11.3. Reducing elementary inconsistent partial states

11.4. Equivalence detection

11.5. Experimental results

11.6. Conclusion

Chapter 12: Symmetry Breaking

12.1. Group theory

12.2. Symmetries on constraint networks

12.3. Symmetry-breaking methods

12.4. Automatic symmetry detection

12.5. Lightweight detection of variable symmetries

12.6. A GAC algorithm for lexicographic ordering constraints

12.7. Experimental results

Appendix A: Mathematical Background

A.1. Sets, relations, graphs and trees

A.2. Complexity

Appendix B: XML Representation of Constraint Networks

Bibliography

Back Cover

Index

First published in Great Britain and the United States in 2009 by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUKwww.iste.co.ukJohn Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USAwww.wiley.com

© ISTE Ltd, 2009

The rights of Christophe Lecoutre to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

Lecoutre, Christophe.

Constraint networks: techniques and algorithms / Christophe Lecoutre.

p. cm.

Includes bibliographical references and index.

ISBN 978-1-84821-106-3

1. Constraint programming (Computer science) 2. Computer algorithms. 3. Computer networks. I. Title.

QA76.612.L43 2009

004.6--dc22

2009016652

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN: 978-1-84821-106-3

Acknowledgements

First of all, I would very much like to thank Julian Ullmann, Emeritus Professor at King’s College London, for his valuable support. Julian made an impressively careful reading of the entire book, giving me a lot of suggestions and amending the text in countless places. It was a great honor to me to benefit from Julian’s help. Thanks to him, the manuscript has been considerably improved.

I am very grateful to people who have contributed comments, corrections and suggestions in various parts of the manuscript: Gilles Audemard, Christian Bessiere, Lucas Bordeaux, Frédéric Boussemart, Hadrien Cambazard, Sylvie Coste-Marquis, Marc van Dongen, Fred Hemery, Philippe Jégou, Mouny Samy Modeliar, Olivier Roussel, Thomas Schiex, Radoslaw Szymanek, Sébastien Tabary, Vincent Vidal, Richard Wallace, Ke Xu and Yuanlin Zhang. Thank you to all of you.

Main Acronyms

CPconstraint programmingCSPconstraint satisfaction problemSATBoolean satisfiability problemACarc consistencyCDCconservative dual consistencyCPCconservative path consistencyDCdual consistencyGACgeneralized arc consistencyIwCinverse w-consistencykWCk-wise consistencyMaxRPCmax-restricted path consistencyMaxRPWCmax-restricted pairwise consistencyNCnode consistencyNICneighborhood inverse consistency  PCpath consistencyPICpath inverse consistencyPPCpartial path consistencyPWCpairwise consistencyrNICrelational neighborhood inverse consistencyrPICrelational path inverse consistencySACsingleton arc consistencyBCbackward checkingBTDbacktracking with tree-decompositionCBJconflict-directed backjumpingDBTdynamic backtrackingDFSdepth-first searchFCforward checkingIBTintelligent backtrackingIPSinconsistent partial stateLClast-conflict-based reasoningMACmaintaining arc consistencySBDDsymmetry breaking via dominance detectionSBDSsymmetry breaking during searchSBTstandard backtrackingSTRsimple tabular reductionCNFconjunctive normal formCRCconnected row-convexDFAdeterministic finite automatonMDDmulti-valued decision diagramXMLextensible markup languageFAPPfrequency assignment problem with polarization constraintsQCPquasi-group completion problemQWHquasi-group with holes problemRLFAPradio-link frequency-assignment problem

Chapter 1

Constraint Networks

This chapter introduces the formalism of constraint networks, which can abstractly represent many academic and real-world problems. Section 1.1 introduces variables and constraints, which are the main ingredients of constraint networks. This introduction includes different representations of constraints as well as the vital concept of constraint support. In , we formally define constraint networks. Moreover, we present the (hyper)graphs that can be associated with any constraint network, and introduce instantiations. provides some illustrative examples of problems that can be easily represented by means of constraint networks. For simplicity and entertainment, these examples are based on logic puzzles. is concerned with partial orders in constraint networks, decisions and general properties of values and variables. Finally, introduces some data structures that can be employed to represent constraint networks in computer programs.