# Full text of "Semirings for soft constraint solving and programming"

## See other formats

LNCS 2962 Stefano Bistarelli Semirings for Soft Constraint Solving and Programming Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis, and J. van Leeuwen 2962 Springer Berlin Heidelberg New York Hong Kong London Milan Paris Tokyo Stefano Bistarelli Semirings for Soft Constraint Solving and Programming Springer Series Editors Gerhard Goos, Karlsruhe University, Germany Juris Hartmanis, Cornell University, NY, USA Jan van Leeuwen, Utrecht University, The Netherlands Author Stefano Bistarelli Universita degli Studi "G. D’Annunzio" di Chieti-Pescara Dipartimento di Scienze Viale Pindaro, 42, 65127 Pescara, Italy E-mail:bista@sci. unich.it and Istituto di Informatica e Telematica, C.N.R. Via G. Moruzzi, 1, 56124 Pisa, Italy E-mail: stefano.bistarelli@iit.cnr.it Cataloging-in-Publication Data applied for A catalog record for this book is available from the Library of Congress. Bibliographic information published by Die Deutsche Bibliothek Die Deutsche Bibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data is available in the Internet at <http://dnb.ddb.de>. CR Subject Classification (1998): D.3.3, D.1.6, D.3.1, D.3, F.3.1, D.2.4, 1.2.2-3 ISSN 0302-9743 ISBN 3-540-21181-0 Springer- Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer- Verlag. Violations are liable for prosecution under the German Copyright Law. Springer- Verlag is a part of Springer Science+Business Media springeronline.com © Springer-Verlag Berlin Heidelberg 2004 Printed in Germany Typesetting: Camera-ready by author, data conversion by DA-TeX Gerd Blumenstein Printed on acid-free paper SPIN: 10988022 06/3142 5 4 3 2 1 0 Foreword Constraint satisfaction and constraint programming have shown themselves to be very simple but powerful ideas. A constraint is just a restriction on the allowed combinations of values for a set of variables. If we can state our problem in terms of a set of constraints, and have a way to satisfy such constraints, then we have a solution. The idea is general because it can be applied to several classes of constraints, and to several solving algorithms. Moreover, it is powerful because of its unifying nature, its generality, its declarative aspects and its application possibilities. In fact, many research and application areas have taken advantage of constraints to generalize and improve their results and application scenarios. In the last 10 years, however, this simple notion of constraint has shown some deficiencies concerning both theory and practice, typically in the way over- constrained problems and preferences are treated. When a problem has no so- lution, classical constraint satisfaction does not help. Also, classical constraints are not able to model conveniently problems which have preferences, for example over the selection of the most relevant constraints, or about the choice of the best among several solutions which satisfy all the constraints. Not being able to handle non-crisp constraints is not just a theoretical prob- lem, but it is also particularly negative for applications. In fact, over-constrained and preference-based problems are present in many application areas. Without formal techniques to handle them, it is much more difficult to define a procedure which can easily be repeated to single out an acceptable solution, and sometimes it is not even possible. For this reason, many researchers in constraint programming have proposed and studied several extensions of the classical concepts in order to address these needs. This has led to the notion of soft constraints. After several efforts to define specific classes of soft constraints, like fuzzy, partial and hierarchical, the need for a general treatment of soft constraints became evident, a treatment that could model many different classes altogether and to prove properties for all of them. Two of the main general frameworks for soft constraints were semiring-based soft constraints and valued constraints. This book is a revised, extended version of the Ph.D. thesis of Stefano Bistarelli, whom we had the pleasure to supervise at the University of Pisa. It focuses mainly on the semiring-based soft constraint formalism, also com- paring it with many of the specific classes and also with valued constraints. Semiring-based soft constraints are so called because they are based on an un- VI Foreword der lying semiring structure, which defines the set of preferences, the way they are ordered, and how they can be combined. This concept is very general and can be instantiated to obtain many of the classes of soft constraints that have already been proposed, including their solution algorithms, and also some new ones. The book includes formal definitions and properties of semiring-based soft constraints, as well as their use within constraint logic programming and concur- rent constraint programming. Moreover, it shows how to adapt to soft constraints some existing notions and techniques, such as abstraction and interchangeability, and it shows how soft constraints can be used in some application areas, such as security. This book is a great starting point for anyone interested in understanding the basics of semiring-based soft constraints, including the notion of soft constraint propagation, and also in getting a hint abut the applicability potential of soft constraints. In fact, it is the first book that summarizes most of the work on semiring-based soft constraints. Although most of its content also appears in published papers, this is the only place where this material is gathered in a coherent way. This book is the result of several threads of collaborative work, as can be seen from the many publications that are cited in the bibliography and whose content is reflected in the book. Therefore many authors have contributed to the material presented here. However, Stefano Bistarelli succeeded in providing a single line of discourse, as well as a unifying theme that can be found in all the chapters. This uniform approach makes the material of this book easily readable and useful for both novice and experienced researchers, who can follow the various chapters and find both informal descriptions and technical parts, as well as application scenarios. November 2003 Ugo Montanari 1 and Francesca Rossi 2 1 Dipartimento di Informatica Universita’ di Pisa Italy 2 Dipartimento di Matematica Pura ed Applicata Universita’ di Padova Italy Preface The Soft Constraints idea is able to capture many real-life situations that cannot be represented and solved with the classical crisp constraint framework. In this book we first describe a general framework for representing many soft constraint systems, and then we investigate the related theoretic and application- oriented issues. Our framework is based on a semiring structure, where the carrier of the semiring specifies the values to be associated with each tuple of values of the variable domain, and the two semiring operations, + and x, model constraint projection and combination, respectively. The semiring carrier and operations can be instantiated in order to capture all the non-crisp constraints representing fuzziness, optimization, probability, hierarchies, and others. The solution of each instance of the soft Constraint Satisfaction Problem (CSP) is computed by using the appropriate x and + semiring operation. This uniform representation can be used to give sufficient conditions for the correctness and applicability of local consistency and dynamic programming al- gorithms. In particular: — We show that using an idempotent x operator the classical local consis- tency (and also dynamic programming) techniques can be used to reduce the complexity of the problem without modifying its solution. — We adapt to the soft framework partial local consistency and labeling tech- niques, which require fewer pruning steps of the domain. This means that, although they are able to remove fewer non-optimal solutions than classi- cal algorithms can, partial local consistency algorithms can be beneficial because they are faster and easier implemented. — We extend general local consistency algorithms that use several pruning rules until the fix-point is reached. Solving a soft CSP is generally harder than solving the corresponding crisp CSP. For this reason we introduce an abstraction/concretization mapping over soft CSPs in order to solve a problem in an easier environment and then use the abstract results to speed up the search of solutions in the concrete one. Several mappings between existing soft frameworks are given. These mappings will es- pecially be useful for applying soft local consistency techniques in a safe, easy, and faster way. Also useful, when looking for optimal solutions, are the notions of substitutability and interchangeability. In crisp CSPs they have been used as a basis for search heuristics, solution adaptation, and abstraction techniques. The next part of the book involves some programming features: as classical constraint solving can be embedded into Constraint Logic Programming (CLP) VIII Preface systems, so too can our more general notion of constraint solving be handled within a logic language, thus giving rise to new instances of the CLP scheme. This not only gives new meanings to constraint solving in CLP, but it also allows one to treat in a uniform way optimization problem solving within CLP, without the need to resort to ad hoc methods. In fact, we show that it is possible to generalize the semantics of CLP programs to consider the chosen semiring and thus solve problems according to the semiring operations. This is done by associating each ground atom with an element of the semiring and by using the two semiring operations to combine goals. This allows us to perform in the same language both constraint solving and optimization. We then provide this class of languages with three equivalent semantics, model-theoretic, fix-point, and proof- theoretic, in the style of CLP programs. The language is then used to show how the soft CLP semantics can solve shortest-path problems. In a way similar to the soft CLP language we also extend the semantics of the Concurrent Constraints (cc) language. The extended cc language uses soft constraints to prune and direct the search for a solution. The last part of the book aims to describe how soft constraints can be used to solve some security-related problems. In the framework, the crucial goals of confidentiality and authentication can be achieved with different levels of secu- rity. In fact, different messages can enjoy different levels of confidentiality, or a principal can achieve different levels of authentication with different principals. Acknowledgement. This monograph is a revised and extended version of my doctoral dissertation which was submitted to the University of Pisa Computer Science Depart- ment and accepted in March 2001. The results presented here have been influenced by many people and I would like to take this opportunity to thank them all. I wish to thank first of all the supervisor of my Ph.D. thesis Ugo Montanari; the main part of this book came from the research performed under his significant guidance. I want also to thank Francesca Rossi, my unofficial supervisor; she shared with me the passion for constraints. Many of the ideas collected in this book came from ideas we developed together. A special thanks is also due to all the friends who shared with me some of the results I collected in this book: Giampaolo Bella, Boi Faltings, Rosella Gennari, Helene Fargier, Yan Georget, Nicoleta Neagu, Elvinia Riccobene, Thomas Schiex, and Gerard Verfaillie. Many thanks are due to the external reviewers of my Ph.D. thesis, Philippe Codognet and Pascal Van Hentenryck; they carefully read a preliminary version of the thesis and provided many useful comments and suggestions. My warmest thanks go to my friend Olga Petosa; she was so kind to read all the conversational parts of my work, correct some typing errors, and make it just a little nicer! Finally, I am also grateful both to the anonymous referees of this book and to Jan van Leeuwen; they gave me a number of hints on a draft version of the book which helped to improve the final presentation. Some thanks also to Anna Kramer and Alfred Hofmann who helped me with the last details needed for the publication of this book. December 2003 Stefano Bistarelli Contents 1. Introduction 1 1.1 From the Beginning 1 1.2 Applications 2 1.2.1 Assignment Problems 2 1.2.2 Personnel Assignment 2 1.2.3 Network Management 3 1.2.4 Scheduling Problems 3 1.2.5 Transport Problems 4 1.3 Crisp Constraints 4 1.3.1 CSPs 5 1.3.2 Constraint Logic Programming 12 1.4 Non-crisp Constraints 14 1.4.1 Partial Constraint Satisfaction Problems 15 1.4.2 Constraint Hierarchies 15 1.4.3 Fuzzy, Probabilistic and Valued CSPs 16 1.5 Overview of the Book 16 1.5.1 Structure of Subsequent Chapter 19 1.5.2 The Origin of the Chapters 20 2. Soft Constraint Satisfaction Problems 21 2.1 C-semirings and Their Properties 22 2.2 Constraint Systems and Problems 27 2.3 Instances of the Framework 33 2.3.1 Classical CSPs 33 2.3.2 Fuzzy CSPs (FCSPs) 35 2.3.3 Probabilistic CSPs (Prob-CSPs) 37 2.3.4 Weighted CSPs 38 2.3.5 Egalitarianism and Utilitarianism 39 2.3.6 Set-Based CSPs 40 2.3.7 Valued Constraint Problems 41 2.3.8 N-dimensional C-semirings 49 2.4 Conclusions 50 X Contents 3. Towards SCSPs Solutions 51 3.1 Soft Local Consistency 52 3.2 Applying Local Consistency to the Instances 59 3.2.1 Classical CSPs 59 3.2.2 Fuzzy CSPs 59 3.2.3 Probabilistic CSPs 60 3.2.4 Weighted CSPs 60 3.2.5 Egalitarianism and Utilitarianism 60 3.2.6 Set-Based SCSPs 61 3.3 About Arc-Consistency in SCSPs 61 3.3.1 Classical Arc-Consistency vs. Semiring-Based One 62 3.3.2 Removing Hidden Variables in SCSPs 65 3.3.3 Tree-Shaped SCSPs 67 3.3.4 Cycle-Cutsets in SCSPs 69 3.4 Labeling and Partial Local Consistency for SCSPs 70 3.4.1 Labeling in SCSPs 72 3.4.2 Partial Local Consistency 76 3.4.3 Domains 79 3.5 Constraint Propagation: Generalization and Termination Condi- tions 82 3.5.1 Some Useful Orderings over Semiring Constraints 83 3.5.2 Order-Related Properties of Soft Local Consistency Rules 86 3.5.3 The Generic Iteration Algorithm 86 3.5.4 Generalized Local Consistency for SCSPs via Algorithm GI 87 3.5.5 Termination of the GI Algorithm over Soft Constraints ... 89 3.6 Dynamic Programming for SCSPs 92 3.7 Conclusions 97 4. SCSP Abstraction 99 4.1 Abstraction 101 4.2 Abstracting Soft CSPs 103 4.3 Properties and Advantages of the Abstraction 105 4.3.1 Relating a Soft Constraint Problem and Its Abstract Version 105 4.3.2 Working on the Abstract Problem Ill 4.4 Some Abstraction Mappings 117 4.5 Abstraction vs. Local Consistency 120 4.6 Related Work 122 4.7 Conclusions 124 5. Higher Order Semiring-Based Constraints 125 5.1 Domains and Semirings 126 5.2 Constraint Problems and Solutions 127 5.3 A Small Language to Program with Soft Constraints 130 5.4 Solving SCSPs 133 5.4.1 Dynamic Programming Techniques 133 Contents XI 5.4.2 Local Consistency Techniques 134 5.4.3 Extending Local Propagation Rules 134 5.5 Constraint Problem as Semiring 135 5.6 Conclusions 136 6. Soft CLP 137 6.1 Syntax of SCLP Programs 139 6.2 Model-Theoretic Semantics 142 6.3 Fix-Point Semantics 146 6.4 Proof-Theoretic Semantics 149 6.4.1 Universal Closure 151 6.4.2 Existential Closure 156 6.5 A Semi-decidability Result 157 6.6 SCLPs with no Functions 160 6.7 An Operational Model for the SCLP Language Using ASM 162 6.7.1 The Gurevich’s Abstract State Machine 163 6.7.2 The Abstract Operational Model of SCLP 164 6.8 Related Work 168 6.9 Conclusions 169 7. SCLP and Generalized Shortest Path Problems 171 7.1 Classical SP Problems 172 7.2 Partially-Ordered SP Problems 175 7.3 Modality-Based SP Problems 180 7.4 An SP Algorithm for a Class of SCLP Programs 182 7.5 Best-Tree Search in AND-OR Graphs 183 7.5.1 AND-OR Graphs and Best Solution Trees 184 7.5.2 AND-OR Graphs Using SCLP 186 7.6 Conclusions 189 8. Soft Concurrent Constraint Programming 191 8.1 Concurrent Constraint Programming 192 8.2 Concurrent Constraint Programming over Soft Constraints 195 8.3 Soft Concurrent Constraint Programming 199 8.4 A Simple Example 202 8.5 Observables and Cuts 203 8.5.1 Capturing Success Computations 204 8.5.2 Failure 207 8.6 An Example from the Network Scenario 208 8.7 Conclusions 212 9. Interchangeability in Soft CSPs 213 9.1 Interchangeability 214 9.2 Interchangeability in Soft CSPs 216 9.2.1 Degradations and Thresholds 218 9.2.2 Properties of Degradations and Thresholds 221 XII Contents 9.2.3 Computing 5 / a / Q _ set -Substitutability/Interchangeability . 225 9.3 An Example 229 9.4 Partial Interchangeability 233 9.5 Conclusions 235 10. SCSPs for Modelling Attacks to Security Protocols 237 10.1 Constraint Programming for Protocol Analysis 240 10.1.1 The Security Semiring 241 10.1.2 The Network Constraint System 242 10.1.3 Computing the Security Levels by Entailment 243 10.1.4 The Initial SCSP 244 10.1.5 The Policy SCSP 245 10.1.6 Assessing the Expected Risk 246 10.1.7 The Imputable SCSPs 248 10.1.8 Formalising Confidentiality 248 10.1.9 Formalising Authentication 250 10.2 An Empirical Analysis of Needham-Schroeder 252 10.3 The Kerberos Protocol 255 10.4 Analysing Kerberos 257 10.4.1 Confidentiality 257 10.4.2 Authentication 260 10.5 Conclusions 260 11. Conclusions and Directions for Future Work 263 11.1 Summary and Main Results 263 11.2 Directions for Future Research 265 11.2.1 Abstraction 265 11.2.2 High Order Semirings 265 11.2.3 SCLP 265 11.2.4 SCLP for Operational Research Problems 266 11.2.5 Soft Concurrent Constraints 266 11.2.6 Soft Constraints for Security 266 11.2.7 Soft Constraint Databases 267 11.2.8 Soft Web Query 267 References 269 List of Figures 1.1 A possible solution to the 8-queens problem 6 1.2 A CSP which is not solved 9 1.3 Tuple redundancy 12 1.4 The CLP framework 13 2.1 Two SCSPs 33 2.2 A CSP and the corresponding SCSP 35 2.3 Combination and projection in classical CSPs 36 2.4 From SCSPs to VCSPs 43 2.5 From VCSP to SCSP 45 2.6 From SCSP to VCSP and back to SCSP again 46 2.7 From VCSP to SCSP, and to VCSP again 47 2.8 Diagrams representing the thesis of Theorem 2.3.11 and 2.3.11 .. . 49 3.1 A CSP which is not AC 63 3.2 A fuzzy CSP 63 3.3 An S AC-consistent FCSP and the corresponding AC-consistent CSP 64 3.4 Redundant hidden variables in CSPs 66 3.5 Redundant hidden variables in SCSPs 66 3.6 New semiring value for the extended tuple 67 3.7 A tree-shaped SCSP and a top-down instantiation order 68 3.8 An SCSP with a cycle over x, y , z and a tree shape over the other variables 69 3.9 The search tree for the SCSP of Figure 3.8 70 3.10 Disjunction example 72 3.11 AC and labeling 73 3.12 A fuzzy CSP and its solution 74 3.13 The set of the {x, y}-labelings corresponding to the problem 74 3.14 A 3-up-down-stair 81 4.1 A Galois insertion 103 4.2 A fuzzy CSP and its solutions 104 4.3 The concrete and the abstract problem 106 4.4 An example of the abstraction fuzzy-classical 107 4.5 An abstraction which is not order-preserving 108 XIV List of Figures 4.6 The general abstraction scheme, with x idempotent 112 4.7 The scheme when / does not modify anything 113 4.8 The scheme when the concrete semiring has a total order 114 4.9 An example with x idempotent 114 4.10 The scheme when x is not idempotent 115 4.11 An example with x not idempotent 116 4.12 Several semirings and abstractions between them 119 5.1 A 3-variable fuzzy CSP 127 5.2 The fuzzy CSP after the application of rule r\ 134 7.1 An SP problem 173 7.2 An SP problem with labeled arcs 174 7.3 A multi-criteria SP problem 176 7.4 An SP problem with modalities 181 7.5 An example of an AND-OR graph 184 7.6 An example of an AND tree 185 7.7 A weighted AND-OR graph problem 187 7.8 A typical connector 187 7.9 The best tree corresponding to the program in Table 7.5.2 188 8.1 The SCSP describing part of a process network 210 8.2 The ordered process network 211 9.1 An example of CSP with interchangeable values 214 9.2 An example of CSP with computation of neighborhood inter- changeable values 216 9.3 A fuzzy CSP 218 9.4 Example of a CSP modeling car configuration with 4 variables . . . 230 9.5 Example of how (5-substitutability and a-substitutability varies in the weighted CSP over the values of variable E from Fig. 9.4 230 9.6 Example of how a— set-substitutability varies in the weighted CSP over the values of variable E from Fig. 9.4 231 9.7 Example of how (5-substitutability and a-substitutability varies in the opposite-fuzzy CSP over the values of variable E from Fig. 9.4 232 9.8 Example of how a— set-substitutability varies in the opposite- fuzzy CSP over the values of variable E from Fig. 9.4 232 9.9 Example of a search of a-interchangeability computing by the use of discrimination trees 233 10.1 Computation rules for security levels 243 10.2 Algorithm to construct the policy SCSP for a protocol CP 246 10.3 Implementation for a simple risk function 247 10.4 Algorithm to construct an imputable SCSP for CP (fragment) 249 List of Figures XV 10.5 The asymmetric Needham-Schroeder protocol 252 10.6 Lowe’s attack to the Needham-Schroeder Protocol 253 10.7 Fragment of the initial SCSP for Needham-Schroeder protocol . . . 253 10.8 Fragment of the policy SCSP for the Needham-Schroeder protoc 254 10.9 Fragment of the Imputable SCSP corresponding to Lowe’s attack 255 10.10 The Kerberos layout 256 10.11 The Kerberos protocol 256 10.12 The initial SCSP for Kerberos (fragment) 257 10.13 The policy SCSP for Kerberos (fragment) 258 10.14 An imputable SCSP for Kerberos (fragment) 259 List of Tables 5.1 Relationships between semiring elements 126 6.1 BNF for the SCLP syntax 139 6.2 Soft n-queens problem 140 6.3 Clauses for the 5-queens problem 141 6.4 Our running example 144 6.5 The Tp operator applied at the running example 148 7.1 The SCLP program representing the SP problem in Figure 7.1 173 7.2 The SCLP program representing the multi-criteria SP problem in Figure 7.3 177 7.3 The SCLP program representing the SP problem with modalities. . . . 181 7.4 The general form of an SCLP program representing an SP problem. . 182 7.5 The system of equations corresponding to the SCLP program form of Table 7.4 183 7.6 The SCLP program representing the AND-OR graph problem in Figure 7.7 188 8.1 cc syntax 194 8.2 see syntax 199 8.3 Transition rules for see 201 8.4 Failure in the sec language 207 1. Introduction “Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it. ” Eugene C. Freuder, Constraints, April 1997 Overview Constraint programming is an emergent software technology for declara- tive description and effective solving of large, particularly combinatorial, prob- lems especially in areas of planning and scheduling. It has recently emerged as a research area that combines researchers from a number of fields, includ- ing Artificial Intelligence, Programming Languages, Symbolic Computing and Computational Logic. Constraint networks and constraint satisfaction prob- lems have been studied in Artificial Intelligence starting from the seventies. Systematic use of constraints in programming has started in the eighties. In constraint programming the programming process consists of the generation of requirements (constraints) and solution of these requirements, by specialized constraint solvers. Constraint programming has been successfully applied in numerous do- mains. Recent applications include computer graphics (to express geometric coherence in the case of scene analysis), natural language processing (construc- tion of efficient parsers), database systems (to ensure and/or restore consis- tency of the data), operations research problems (like optimization problems), molecular biology (DNA sequencing), business applications (option trading), electrical engineering (to locate faults) and circuit design (to compute layouts) . This book is centered around the notion of constraint solving [189] and pro- gramming [141]. The interest in constraint satisfaction problems can be easily justified, since they represent a very powerful, general, and declarative knowl- edge representation formalism. In fact, many real-life situations can be faithfully described by a set of objects, together with some constraints among them. Ex- amples of such situations can be found in several areas, like VLSI, graphics, typesetting, scheduling, planning, as well as CAD, decision-support systems and robotics. 1.1 From the Beginning . . . The constraint idea comes from the early 1960’s when Sutherland introduced Sketchpad [187], the first interactive graphical interface that solved geometric S. Bistarelli: Semirings for Soft Constraint Solving..., LNCS 2962, pp. 1—20, 2004. (c) Springer- Verlag Berlin Heidelberg 2004 2 1. Introduction constraints. After that came Fikes’ REF-ARF [97] and at the beginning of 1970’s Montanari described fundamental properties of the constraints when applied to picture processing [149]. Another study in finite domain constraint satisfaction was done at the end of 1970’s in Lauriere’s ALICE [133], a system developed to solve prediction/detection problems in geology. After these, several constraint languages have been proposed in the literature: the language of Steele ( [184]), CONSTRAINTS [186] of Sussman & Steele, Thinglab ( [60]) and Bertrand ( [134]). From Sketchpad until now, a lot of research has been done and improvements made, and the classical constraint satisfaction problems (CSPs) [139, 150] have been shown to be a very expressive and natural formalism to specify many kinds of real-life problems. 1.2 Applications Today, the use of the constraint programming idea to solve many real-life prob- lem is reality. Many important companies develop tools based on the constraint technology to solve assignment , network management , scheduling , transport and many other problems: 1.2.1 Assignment Problems Assignment problems were one of the first type of industrial applications that were solved with the CLP technology. These problems usually have to handle two types of resources, and constraints among them, and try to assign one resource of the first kind to one of the second kind such that all constraints are satisfied. An example is the stand allocation for airports, where aircrafts (the first kind of resources) must be parked on the available stands (the second kind of resources) during their stay at the airport. The first industrial CLP application was developed for the HIT container harbor in Hong Kong [161], using the language CHIP: the objective was to allocate berths to container ships in the harbor, in such a way that resources and stacking space for the containers is available. Other Hong Kong applications are at the airport, where a CHIP- based system is used to solve the counter allocation problem [69], and another constraint-based system, which uses the ILOG libraries, is used for the stand allocation problem since mid-1998 [70]. Another system, called APACHE [88], was a demonstrator for stand allocation at Roissy airport in Paris: the objective was to replan the allocation when a change of arrival/departure times occurred. 1.2.2 Personnel Assignment Personnel assignment problems are a special case of assignment problems where one resource type consists of humans. This peculiarity makes them specific enough to be considered separately. In fact, changing work rules and regula- tions impose difficult constraints which evolve over time. Also, user preferences 1.2 Applications 3 often lead to over-constrained problems, which have no solution satisfying all constraints. Another important aspect is the requirement to balance the work among different persons, which leads to hard optimization problems. The Gymnaste system [65] produces rosters for nurses in hospitals, and is used in many hospitals in France. Around 250 technicians and journalists of the French TV and radio station RFO are scheduled with the OPTI-SERVICE system [73], which generates weekly workplans from the individual activities which must be covered by different persons with different qualifications. The personnel for the TGV high-speed train bar and restaurant services is scheduled with the EPPER application [92]: all services for a month are covered by a team of 250 people. Recently a distributed CLP system has been used to tackle a workforce management problem within British Telecom [131]. Also Telecom Italia is using a constraint-based system to schedule all its technical tasks (about 100.000 tasks involving 20.000 technicians) over its territory [113]; the system which controls the whole workforce management has a scheduling module, called ARCO, which dispatches activities to technicians, and which makes extensive use of constraint propagation techniques. 1.2.3 Network Management Another application domain for finite domain CLP is network management, where many different problems can be addressed and solved using CLP. The LOCARIM system was developed by COSYTEC for France Telecom: starting from an architectural plan of a building, it proposes a cabling of the telecommunication network of the building. The PLANETS system, developed by the University of Catalonia in Barcelona for the Spanish electricity company, is a tool for electrical power network reconfiguration which allows to schedule maintenance operations by isolating network segments without disrupting cus- tomer services. The company Icon in Italy produces a load-balancing application which is controlling network flow for the inter-banking system in Italy. The Esprit project CLOCWiSe (IN 103161) is using CHIP for the management and oper- ational control of water systems. The planning of wireless digital networks for mobile communication has been tackled by the system POPULAR [110], written in ECLiPSe and then in CHR: the main advantages with respect to other ap- proaches to this same problem (using traditional imperative programming) are a good balance among flexibility, efficiency, and rapid prototyping. 1.2.4 Scheduling Problems Perhaps the most successful application domain for finite domain CLP are scheduling problems. Given a set of resources with given capacities, a set of activities with given durations and resource requirements, and a set of temporal constraints between activities, a “pure” scheduling problem consists of deciding when to execute each activity, so that both temporal constraints and resource constraints are satisfied. 4 1. Introduction A typical example of a constraint-based scheduling application is ATLAS [181], which schedules the production of herbicides at the Monsanto plant in Antwerp. The PLANE system [26] is used by Dassault Aviation to plan the production of the military Mirage 2000 jet and the Falcon business jet. The ob- jective is to minimize changes in the production rate, which has a high set-up cost, while finishing the aircraft just in time for delivery. The MOSES applica- tion was developed by COSYTEC for an animal feed producer in the UK: it schedules the production of compound food for different animal species, elimi- nating contamination risk and satisfying costumer demand with minimal cost. The FORWARDC system is a decision support system, based on CHIP, which is used in three oil refineries in Europe to tackle all the scheduling problems occur- ring in the process of crude oil arrival, processing, finished product blending and final delivery [115]. Recently, Xerox has adopted a constraint-based system for scheduling various tasks in reprographic machines (like pothocopiers, printers, fax machines, etc.); the role of the constraint-based scheduler is to determine the sequence of print making and to coordinate the time-sensitive activities of the various hardware modules that make up the machine configuration [109]. Recent results on the tractability of classes of constraint problems have shown that such scheduling problems are indeed tractable, and thus amenable for an efficient solution [164]. 1.2.5 Transport Problems A variety of transport problems have been tackled using constraints. These prob- lems are often very complex due to their size, the number and variety of con- straints, and the presence of complex constraints on possible routes. Moreover, often these problems have a personnel allocation problem as a sub-aspect, usually with complex safety and union regulations. The COBRA system [180] generates diagrams representing workplans for train drivers of North Western Trains in the UK. For each week, around 25.000 activities must be scheduled in nearly 3.000 diagrams, taking a complex route network into account. The DAYSY Esprit project (8402) and the SAS-Pilot program [14] considers the operational re-assignment of airline crews to flights. This same problem is tackled also by another system [100], which uses a combi- nation of CLP and OR techniques. A recently developed system uses the ILOG constraint libraries to produce and optimize train operating plans for a freight railway company, by creating transport movements for rolling stock between sources, hubs and sinks while satisfying transport requirements [143]. 1.3 Crisp Constraints In this section we review some definitions and notions which will be fundamental for our work. The section is divided in three parts: In the first one we define the Constraint Satisfaction Problems (CSPs) and we introduce the classical solv- ing techniques; In the second one, we introduce Constraint Logic Programming 1.3 Crisp Constraints 5 (CLP) framework; lastly, we describe the concurrent constraint (cc) framework. There is also some other background material that will be used later in the book. That material, however, will be introduced only when needed. 1.3.1 CSPs Constraint Satisfaction Problems (CSPs) are a very powerful and general knowl- edge representation formalism, since many real situations can be faithfully de- scribed by a set of objects, together with some constraints among them. They were a subject of research in Artificial Intelligence for many years starting from the 1970s. From that date several classes of constraints were studied (e.g., tem- poral constraint problems, constraint problems over intervals and over reals, linear constraints) but in this book we will concentrate on the specific class of constraints over Finite Domain. We believe that finite domain constraint problems [85,105,138,150,152], i.e. , constraint problems where the objects may assume a finite number of distinct configurations, are of special interest, since they are significantly simpler to an- alyze than general constraint problems, while still being able to express, either faithfully or through a certain degree of abstraction, the main features of several classes of real life problems. Before providing the formal definition of the CSP and its solution methods, let’s look at some examples [168], also to illustrate the variety of the potential application fields. Example 1.3.1 (8-queens). Famous test-problem popular also in the CSP world is the 8-queens problem: place 8 queens on the chess board such that they do not attack each other (see Figure 1.1. In order to formulate this problem as a CSP, the location of the queens should be given by variables, and the “do not attack each other” requirement should be expressed in terms of a number of constraints. A simple way to do this is to assign a variable to each queen. As the 8 queens must be placed in 8 different columns, we can identify each queen by its column, and represent its position by a variable which indicates the row of the queen in question. Let Xi stand for the row of the queen in the i-th column. The domain of each of the variables Xi, . . . , Xs is {1, 2, ...8}. For any two different variables the following two constraints must hold, expressing that the queens should be in different rows and on different diagonals: Xi ^ Xj I Xi -Xj I ^ \i — j\ In this formulation of the problem, we have to find a solution out of the total possible instantiations of the variables, which is 8 s . This formulation, though seems natural, does contain a trick: a part of the requirements of the problem is reflected in the representation, not in the constraints. We could have used the most straightforward representation, namely identifying the squares of the chess board by the 1, 2, . . . , 64 numbers, and having 8 variables for the 8 queens all 6 1. Introduction A B C D E F G H w w w w w w w w Fig. 1.1. A possible solution to the 8-queens problem with the domain {1, 2, . . . , 64}. In this case, the “different columns” requirement should be expressed too by constraints, and all the three types of constraints become more intrinsic to formulate. The total number of possible arrangements becomes as large as 64 64 , containing a configuration of queens multiple times due to the identification of the 8 queens. So we have many reasons to prefer the first representation over the second one. It is true in general that a problem can be formulated as a CSP in a number of ways. The resulting CSPs may differ significantly considering the number and complexity of the constraints and the number of the possible instantiations of the variables, and thus may require very different amount of time and memory to be dealt with. Hence when modelling a problem as a CSP, one has to pay attention to different possibilities, and try to commit to the one which will be the easiest to cope with. The in-depth analysis of the different solution methods and of the characteristics of the CSPs may provide a basis to make a good choice. Several cases have been reported when a notoriously difficult problem could be solved finally as a result of change of the representation. Both representations of the 8-queens problem are pleasantly regular: the domain of all the variables is the same, all the constraints refer to 2 variables, and for each pair of variables the same type of constraints are prescribed. Hence the 8-queens problem is not appropriate as a test case for solution algorithms developed to solve general CSPs. In spite of this intuitive observation, earlier the 8-queens had been a favourite test problem: there had 1.3 Crisp Constraints 7 been a race to develop search algorithms which were able to solve the problem for bigger and bigger n. (It is possible to construct a solution analytically.) This practice was stopped by two discoveries. On the one hand, Sosic [183] came up with a polynomial-time search algorithm, which was heavily exploiting the above mentioned special characteristics of the problem. On the other hand, by analysing the search space of the n-queens problem, it was shown that the general belief that “the bigger the n the more difficult the problem is” does not hold - in fact, the truth is just the opposite [153]. Example 1.3.2 (graph colouring) . Another, equally popular test problem is graph colouring: colour the vertices of a given graph using k colours in such a way that connected vertices get different colours. It is obvious how to turn this problem into a CSP: there are as many variables as vertices, and the domain for each variable is {1,2,..., A} , where k is the allowed number of colours to be used. If there is an edge between the vertices represented by the variables Xi and Xj, then there is a constraint referring to these two variables, namely: Xi ^ Xj . Though for the first sight graph colouring may seem to be just as a toy problem as the n-queens, there are basic differences between the two problems. First of all, graph colouring is known to be NP-complete, so one does not expect a polynomial-time search algorithm to be found. Secondly, it is easy to generate a great number of test graphs with certain parameters, which are more or less difficult to be coloured, so the family of graph colouring problems is appropriate to test algorithms thoroughly. Finally, many practical problems, like ones from the field of scheduling and planning, can be expressed as an appropriate graph colouring problem. Let’s now provide a formal definition of constraint satisfaction problem: Definition 1.3.1 (constraint satisfaction problem). A Constraint Satis- faction Problem is a tuple { V , D , C, con , def, a) where — V is a finite set of variables, i.e., V = {iq, . . . , v n }; — D is a set of values, called the domain; — C is a finite set of constraints, i.e., C = {ci,...,c m }. C is ranked, i.e. C = (J fc Ck, such that c £ Ck if c involves k variables; — con is called the connection function and it is such that con : U(C fe - V k ), k where con(c) = (v\, ... , Vk) is the tuple of variables involved in c £ Ck', — def is called the definition function and it is such that def : (J(Cfc - p(D k )), k where p(D k ) is the powerset of D k , that is, all the possible subsets of k -tuple in D k ; 1. Introduction — a C V, and represent the distinguished variables of the problem. In words, function con describes which variables are involved in which con- straint, while function def specifies which are the domain tuples permitted by the constraint. The set a is used to point out the variables of interest in the given CSP, i.e. , the variables for which we want to know the possible assign- ments, compatibly with all the constraints. Note that other classical definitions of constraint problems do not have the notion of distinguished variables, and thus it is as if all variables are of interest. We choose this definition, however, for two reasons: first, the classical definition can be trivially simulated by having a set of distinguished variables containing all the variables, and second, we think that this definition is much more realistic. In fact, it is reasonable to think that the CSP representation of a problem contains many details (in terms of constraints and/or variables) which are needed for a correct specification of the problem but are not important as far as the solution of the problem is concerned. In other words, the non distinguished variables play the role of existential variables: we want to assure that they can be assigned to values consistently with the constraints, but we do not care to know the assignment. The solution Sol(P) of a CSP P = ( V , D, C, con, def, a) is defined as the set of all instantiations of the variables in a which can be extended to instantiations of all the variables which are consistent with all the constraints in C. Definition 1.3.2 (tuple projection and CSP solution). Given a tuple of domain values (v\, . . v n ), consider a tuple of variables (xn, . . ., Xi m ) such that Vj = 1 there exists a kj with kj £ {l,...,n} such that Xij = Xk r Then the projection of (vi, . . . , v n ) over (xn, . . . , Xi m ), written (v\, . . . , v n ) \( Xil ,..., Xim ) , is the tuple of values (vn , . . . , Vi m ). The solution Sol(P) of a CSP P = ( V, , D, C, con, def , a) is defined as {{vi,-- v n )\a such that Vi £ D for all v, Vce C, (v 1: . . . ,-y n )| con(c) G def(c). } The solution to a CSP is hence an assignment of a value from its domain to every variable, in such a way that every constraint is satisfied. We may want to find just one solution, with no preference as to which one, or all solutions. To give a graphical representation of a CSP problem, we use a labelled hy- pergraph which is usually called a constraint graph ( [85]). Definition 1.3.3 (labelled hypergraph). Given a set of labels L, a hyper- graph labelled over L is a tuple ( N , H, c, l) , where N is a set of nodes, H is a set of hyperarcs, c : (J k (Hk — > N k ), and l : (J k (Hk — > p(L k )). I.e., c gives the tuple of nodes connected by each hyperarc, and l gives the label of each hyperarc. Definition 1.3.4 (from CSPs to labelled hypergraphs). Consider a CSP P = ( V , D, C, con, def, a). Then the labelled hypergraph corresponding to P, written G(P), is defined as the hypergraph G(P) = ( V,C,con,def ) labelled over D. 1.3 Crisp Constraints 9 In the hypergraph corresponding to a CSP, the nodes represent the variables of the problem, and the hyperarcs represent the constraints. In particular, each constraint c can be represented as a hyperarc connecting the nodes representing the variables in con(c). Constraint definitions are instead represented as labels of hyperarcs. More precisely, the label of the hyperarc representing constraint c will be def(c). The representation of a CSP by a hypergraph turns out to be very useful when focusing on properties of the CSP which involve notions of sparseness and/or locality. In particular, locality can be defined in term of subgraphs, where a subgraph of a given graph consists of a subset S of the nodes together with some of the hyperarcs connecting subsets of S. For example, the theory of local consistency techniques for discrete CSPs (which we will review later), whose aim is to remove local inconsistencies, can be given in terms of operations on hyper graphs. As for the notion of solution of a finite domain CSP, consider for example the CSP depicted in Figure 1.2, where each arc is labeled by the definition of the corresponding constraint, given in terms of tuples of values of the domain, and the distinguished variables are marked with a *. The solution of this problem is the set {(a, 6)}. Solution Techniques. The methods to generate a solution for a CSP fall mainly into two classes [168]. In the first class are the variants of backtracking search. These algorithms construct a solution by extending a partial instantia- tion step by step, relying on different heuristics and using more or less intelligent backtracking strategies to recover from dead ends. The reduction of a problem is advantageous, resulting in a smaller solution space to be searched. The sec- ond class are the so-called constraint propagation algorithms do eliminate some non-solution elements from the search space. In general, these algorithms do not eliminate all the non-solution elements, hence, they do not produce a solution on their own. They are used either to pre-process the problem before another type of algorithm is applied, or interwoven with steps of another kind of - e.g. backtracking search - algorithm to boost its performance. All the algorithms from the above three classes investigate the solution space systematically. Hence all those algorithms of the above classes which are meant to find a solution, in theory really do the job as long as there is a solution. These algorithms are: Fig. 1.2. A CSP which is not solved 10 1. Introduction — sound , that is if they terminate with a complete instantiation of the variables than it is a solution; — complete , that is capable to investigate the entire search space and hence find all the solutions. These requirements seem to be very essential, however, often one has to be satisfied with algorithms which do not fulfill one or both of them. The systematic search algorithms require exponential time for the most difficult CSPs. A CSP is difficult if (almost) the entire search space has to be investigated before finding a solution or concluding that the problem has none. If the search space is large, then it may take days or weeks to run a complete and sound algorithm. This can be forbidding in case of applications where a solution can be used only if provided within a short time. In such cases a compromise is made, by using an algorithm which provides an answer fast, but the answer is not guaranteed to be a solution. However, it is “good enough” in the sense that not all the constraints are satisfied, but the number of non-satisfied constraints the and degree of violations can be accepted. Though such an algorithms cannot be used to generate all the (good) solutions for sure, usually it is possible to generate several quite different “almost solu- tions” (if they exist). The so-called local stochastic search algorithms have in common that they explore the solution space in a non-systematic way, stepping from one complete instantiation to another, based on random choices, and may navigate on the basis of heuristics, often adopted from systematic search meth- ods. In the recent years such algorithms have been used with success to solve large practical problems, and they are suitable to handle CSPs extended with some objective function to be optimised. Constraint Propagation. By eliminating redundant values from the problem definition, the size of the solution space decreases. Reduction of the problem can be done once, as pre-processing step for another algorithm, or step by step, interwoven with the exploration of the solution space by a search algorithm. In the latter case, subsets of the solution space are cut off, saving the search algo- rithm the effort of systematically investigating the eliminated elements, which otherwise would happen, even repeatedly. If as a result of reduction any domain becomes empty, then it is known immediately that the problem has no solu- tion. One should be careful with not spending more effort on reduction than what will “pay off” in the boosted performance of the search algorithm to be used to find a solution of the reduced problem. The reduction algorithms elim- inate values by propagating constraints. The amount of constraint propagation is characterised by the consistency level of the problem, hence these algorithms are also called consistency-algorithms. The iterative process of achieving a level of consistency is sometimes referred to as the relaxation process, which should not be mixed up with relaxation of constraints. Constraint propagation has a long tradition in CSP research. Below we introduce the most well-known and widely used algorithms. Node- and arc- consistency. A CSP is node- consistent, if all the unary constraints hold for all the elements of the domains. The straightforward node-consistency 1.3 Crisp Constraints 11 algorithm (NC), which removes the redundant elements by checking the domains one after the other has O (dn) time complexity, where d is the maxim of the size of the domains and n is the number of the variables. A CSP is arc-consistent, if for any u value from the domain of any variable x, any binary constraints which refers to x can be satisfied. k- consistency. Arc-consistency can be also understood as telling something about how far a partial solution can always be extended. Namely, any partial solution containing only one instantiated variable can be extended by instantiat- ing any second variable to a properly chosen value. Applying the same principle for more variables, we arrive at the concept of fc-consistency. Definition 1.3.5 (fc-consistency). A CSP is k-consistent, if any consistent instantiation of any k — 1 variables can be extended by instantiating any one of the remaining variables. It is important to understand clearly the significance of consistency. A CSP which is fc-consistent , is not necessarily solvable, and in the other way around, the solvability of a problem does not imply any level of consistency, not alone 1-consistency. The consistency as a feature of a problem does guarantee that cer- tain values and value /i-tuples which are not in the projection of the solution set have been removed form the domains and constraints. The level of consistency, k indicates for what /i-values has this been done. In general, the main idea is to improve the brute force backtracking by cutting down the search space. This is done by first modifying the original constraint network to a more explicit one (by eliminating redundancy), and then to run the search. In a finite domain CSP, redundancy can be found mainly in the definitions of the constraints. In other words, a tuple of domain values in a constraint definition may be considered to be redundant if its elimination does not change the solution of the problem. A sufficient condition for tuple redundancy is that the tuple be inconsistent with (all the tuples in) some other constraint in the CSP. In fact, if this condition holds, then the tuple will never be used in any solution of the CSP (otherwise the other constraint would be violated), and thus the solution will not change if the tuple is deleted. Consider, for example, a CSP which, among other variables and constraints, contains the variables x, y, and z , and the two constraints as depicted in Figure 1.3. Then, tuple (a, a) of the constraint between x and y is inconsistent with the constraint between y and z. In fact, if x and y are both instantiated to a , then there is no way to instantiate z so as to satisfy the constraint between y and z. Therefore, tuple (a, a) is redundant and may be eliminated from the CSP, yielding a new CSP which is obviously equivalent to the old one. More precisely, given a CSP P\ , the aim is to obtain a new CSP P 2 such that Pi and P 2 have the same solution and the same constraint graph, and P 2 has smaller constraint definitions. 12 1. Introduction Fig. 1.3. Tuple redundancy Given that in order to check the redundant status of a tuple we look at some constraints which are adjacent to the one containing that tuple (because constraints not sharing variables with the given one would not help), usually this kind of redundancy is also called local inconsistency. In fact, we do not look at the whole CSP, but only at some small portion of it (which contains the constraint with the tuple under consideration). Local inconsistency obviously implies global inconsistency, and this is why the condition of local inconsistency is sufficient for redundancy. 1.3.2 Constraint Logic Programming As far as we know, even though some languages for handling special kinds of constraints were developed in the past (like ThingLab [60], Bertrand [134], and ALICE ( [133]), no general linguistic support were given to constraint solving and constraint propagation until the development of the constraint logic program- ming (CLP) scheme. This scheme can be seen as a logic programming shell, supported by an underlying constraint system which may handle and solve any kind of constraints. For this reason the CLP scheme can be denoted by CLP(X), where X specifies the class of constraints we want to deal with. In this section we describe the basic concepts and the operational semantics of the constraint logic programming framework. For a longer and more detailed treatment, which also includes other kinds of semantics, we refer to [125,126,127]. We assume the readers to be already familiar with the logic programming formal- ism, as defined in [135]. The main idea in CLP is to extend logic programming, in such a way that — substitutions are replaced by constraints, — unification is replaced by a constraint solution, and — all the semantic properties of logic programming (mainly, the existence of declarative, denotational, and procedural semantics and the equivalence of these three objects) still hold. Figure 1.4 describes informally the CLP framework. As we can see, the logic programming shell and the underlying constraint system communicate by means 1.3 Crisp Constraints 13 of consistency checks, which are requested by the shell and performed by the constraint system. In constraint logic programs the basic components of a problem are stated as constraints. The problem as a whole is then represented by putting the various constraints together by means of rules. Definition 1.3.6 (constraint rule, goal, programs). Consider a particular instance of the CLP(X ) framework. — A constraint rule is of the form A . c, , . . . , B n . where n > 0, c is a constraint over the class X, and A and all Bi s are atoms over the Herbrand Universe. A is called the head of the rule, and c, B i, ... , B n the body. If n = 0 then such a constraint rule can also be called a fact. — A goal is a constraint rule without the head, i.e of the form : : —c. or : c, B\ , ... , B n . — A constraint logic program is a finite set of constraint rules. Let us now describe how the CLP system works to decide if a given goal is a logical consequence of the program; i.e., how the operational semantics of logic programming, which we assume is given by SLD-resolution, has to be extended in order to deal with constraints instead of (or, better, besides) substitutions. Definition 1.3.7 (derivation step). Given a CLP(X) program P, a deriva- tion step takes a goal . (c, Ai, . . . , A^ logic programming shell constraint system Fig. 1.4. The CLP framework 14 1. Introduction and a (variant of a) constraint rule A : c' , B\, . . . , B m . in P. If (c U c!) U ( Ai = A) is satisfiable, then the derivation step returns a new goal : -~((cU c') U (A = Ai), Ai, . . . , Aj_i, B\, . . . B m , Ai + 1 , . . . A n ) Definition 1.3.8 (derivation, answer constraint). A derivation is a se- quence of derivation steps. Derivation sequences are successful (and are called refutations) when the last goal therein contains only constraints. These answer constraints constitute the output of a CLP program. The satisfiability of Ai = A is the problem of finding, if there is one, an mgu, and thus, it is a task which can be accomplished by the logic programming engine that underlies the CLP system. On the contrary, to check the satisfiability of (cUc') we need to use the particular constraint solver corresponding to the chosen structure X . If, for example, we are considering arithmetic inequality constraints over the reals, then the constraint solver could be a simplex algorithm. Thus, at each derivation step two constraint solvers are needed: one for the Herbrand universe and one for the chosen class of other constraints. The fact that CLP can be interpreted as the possibility of using logic pro- gramming as a logic “shell” where to formally reason about constraints and solve constraint problems intuitively implies that logic programming is not only an instance of CLP, but it is always “present” in the CLP framework. More pre- cisely, since a constraint is simply a relation which must hold among a collection of objects, then term equalities, which are handled in logic programming while performing unification, are a special case of constraints. Therefore, it is safe to say that any logic program is a CLP program where the only allowed constraints are term equalities. On the other hand, it is also true that any CLP instance needs to perform unifications, and thus term equalities must always be among the allowed constraints. 1.4 Non-crisp Constraints All this constraint application, however, have some obvious limitations, mainly due to the fact that they do not appear to be very flexible when trying to represent real-life scenarios where the knowledge is neither completely available nor crisp. In fact, in such situations, the ability to state whether an instantiation of values to variables is allowed or not, is not sufficient or sometimes not even possible. For these reasons, it is natural to try to extend the CSP formalism in this direction. For example [91,165, 167], CSPs have been extended with the ability to as- sociate with each tuple, or to each constraint, a level of preference, and with the possibility of combining constraints using min-max operations. This extended 1.4 Non-crisp Constraints 15 formalism was called Fuzzy CSPs (FCSPs). Other extensions concern the ability to model incomplete knowledge of the real problem [96] , to solve over-constrained problems [108], and to represent cost optimization problems [24,31]. The constraints in classical constraint satisfaction problems are crisp, i.e. , they either allow a tuple (of values of involved variables) or not. In some real- life applications, this is not a desired feature and, therefore, some alternative approaches to constraint satisfaction were proposed to enable non-crisp con- straints, probabilities or weights respectively. These extensions can be used to solve optimization problems as well as over-constrained problems as they allow relaxing of constraints. 1.4.1 Partial Constraint Satisfaction Problems The Partial Constraint Satisfaction (PCSP) [108] scheme of Freuder and Wallace is an interesting extension of CSP, which allows the relaxation and optimization of problems via the weakening of the original CSP. A theory of Partial Constraint Satisfaction Problems (PCSPs) were devel- oped to weaken systems of constraints which have no solutions (over-constrained systems), or for which finding a solution would take too long. Instead of search- ing for a solution to a complex problem, we consider searching for a simpler problem that we know we can solve. Definition 1.4.1 (Partial Constraint Satisfaction Problems). The notion of a partial CSP is formalized by considering three components: ((P, U), ( PS , <), (M, ( N , S))) where: — ( PS , <) is a problem space with PS a set of problems and < a partial order over problems, — P £ PS is a constraint satisfaction problem (CSP), U is a set of ’universes’ i.e. a set of potential values for each of the variables in P, — M is a distance function over the problem space, and (N, S) are Necessary and Sufficient bounds on the distance between the given problem P and some solvable member of the problem space PS A solution to a PCSP is a problem P' from the problem space and its solution, where the distance between P and P' is less than N . If the distance between P and P' is minimal, then this solution is optimal. 1.4.2 Constraint Hierarchies Constraint hierarchies [61] were introduced for describing over-constrained sys- tems of constraints by specifying constraints with hierarchical strengths or pref- erences. It allows one to specify declaratively not only the constraints that are required to hold, but also weaker, so called soft constraints at an arbitrary but finite number of strengths. Weakening the strength of constraints helps in find- ing a solution of a previously over-constrained system of constraints. Intuitively, the hierarchy does not permit the weakest constraints to influence the result. 16 1. Introduction Moreover, constraint hierarchies allow “relaxing” of constraints with the same strength by applying, for example a weighted-sum, least-squares or similar com- parators. Definition 1.4.2 (Constraint Hierarchies). In constraint hierarchies, one uses labeled constraints which are constraints labeled with a strength or pref- erence. Then, a constraint hierarchy is a (finite) multiset of labeled con- straints. Given a constraint hierarchy H , let Hq denote the set of required con- straints in H, with their labels removed. In the same way, we define the sets Hi,H 2 , ■ ■ - for levelsl, 2, . . .. A solution to a constraint hierarchy H will consist of instantiations for vari- ables in H , that satisfies the constraints in H respecting the hierarchy. Formally (U , V are instantiations): Sh , o = {U | for each c in Ho, c is satisfied by U} Sh = {U | U £ Sh , o andVV £ Sh,o, V is not better than U respecting H}. The set Sh , o contains instantiations satisfying required constraints in H and Sh, called a solution set for H, is a subset of Sh,o containing all instantiations which are not worse than other instantiations in Sh. o- 1.4.3 Fuzzy, Probabilistic and Valued CSPs The Fuzzy [91, 165, 167], Probabilistic [96] and Valued CSPs [174] use values to express fuzzyness, probability or several preference values in the problem. In particular, Fuzzy CSPs are a very significant extension of CSPs since they are able to model partial constraint satisfaction (PCSP [108]) and also prioritised constraints (Constraint hierarchies [61]), that is, constraints with different levels of importance . We will give a detailed description of the fuzzy, probabilistic and VCSP framework in the next chapter, when will also show how to represent all this non-crisp extension in our framework. 1.5 Overview of the Book In this book we describe a constraint solving framework where most of these extensions, as well as classical CSPs, can be cast. The main idea is based on the observation that a semiring (that is, a domain plus two operations satisfying certain properties) is all that is needed to describe many constraint satisfaction schemes. In fact, the domain of the semiring provides the levels of consistency (which can be interpreted as either cost, degrees of preference, probabilities, or others), and the two operations define a way to combine constraints together. More precisely, we define the notion of constraint solving over any semiring. Specific choices of the semiring will then give rise to different instances of the framework, which may correspond to known or new constraint solving schemes. 1.5 Overview of the Book 17 With the definition of the new framework, we also need to extend the classical AI local consistency techniques [104, 105, 138, 139, 150, 152] that have proven to be very effective when approximating the solution of a problem in order to be applied in the semiring framework. We may say that all of them are variants or extensions of two basic algorithms, which started the field. One is the arc consistency algorithm (used for the first time in [193] but studied and named later in [138], where we may say that inconsistency is eliminated by each unary constraint (i.e., involving only one variable); or, that each unary constraint (i.e., connecting only one variable, say v) is propagated to all variables attached to the variable v by some binary constraint. The other pioneering algorithm is the path- consistency algorithm (which was proposed in [150]), where inconsistency is eliminated by each binary constraint; or, in other words, where each binary constraint connected to variables v and v' is propagated to all other variables attached to v and v' by some binary constraint. Then, a more general one is the k-consistency algorithm scheme [104], where inconsistency is eliminated by each set of constraints involving k variables (it is easy to see that arc-consistency is 2-consistency and that path-consistency is 3-consistency). We generalize these techniques to our framework, and we provide sufficient conditions over the semiring operations which assure that they can also be fruit- fully applied to the considered scheme. By “fruitfully applicable” we mean that 1) the algorithm terminates and 2) the resulting problem is equivalent to the given one and it does not depend on the nondeterministic choices made during the algorithm. The advantage of the SCSP framework is that one can hopefully see one’s own constraint solving paradigm as an instance of SCSP over a certain semiring, and can inherit the results obtained for the general scheme. In par- ticular, one can immediately see whether a local consistency and/or a dynamic programming technique can be applied. Also the study of generalized versions of AI algorithms for the SCSP frame- work seems to be very important. In particular, the partial local consistency algorithms seem to be efficient and useful. Moreover, we study the behavior of a class of algorithms able to eliminate from a semiring-based constraint problem some solutions that are not interesting (where interesting might mean optimal) and we will study their application to SCSPs. To solve an SCSP problem in a faster way, we try to “simplify” it by changing the structure of the semiring. The solutions obtained in the easier semiring have to be mapped back and used to solve the original problem. In order to capture some interesting properties we use a notion of abstract interpretation to represent this mapping. The idea is to take an SCSP problem P and map it over a new problem P' which is easier to handle and solve. As soon as we have solved (or partially solved) P' we have to map back the solutions (or the partial solutions) over the original problem. Depending on the properties of the semiring operations, we can perform some simplification steps over the original problem. Next we demonstrate how to extend the logic programming paradigm to deal with semiring based constraints. One of the ways to program with constraint is 18 1. Introduction to dip the constraints in the logic programming theory obtaining the CLP frame- work. Programming in CLP means choosing a constraint system for a specific class of constraints (for example, linear arithmetic constraints, or finite domain constraints) and embedding it into a logic programming engine. This approach is very flexible because one can choose among many constraint systems without changing the overall programming language, and it has been shown to be very successful in specifying and solving complex problems in terms of constraints of various kinds. It can, however, only handle classical constraint solving. Thus, it is natural to try to extend the CLP formalism in order to be able to also handle SCSP problems. We will call such an extension SCLP (for Semiring-based CLP). In passing from CLP to SCLP languages, we replace classical constraints with the more general SCSP constraints. By doing this, we also have to modify the notions of interpretation, model, model intersection, and others, since we have to take into account the semiring operations and not the usual CLP operations. For example, while CLP interpretations associate a truth value (either true or false) to each ground atom, here, ground atoms must be given one of the elements of the semiring. Also, while in CLP the value associated to an existentially quantified atom is the logical or among the truth values associated to each of its instantiations, here we have to replace the or with another operation which refers to one of the semiring ones. The same reasoning applies to the value of a conjunction of atomic formulas: instead of using the logical and we have to use a specific operation of the semiring. After describing the syntax of SCLP programs, we define three equivalent semantics for such languages: model-theoretic, fix-point, and operational. These semantics are conservative extensions of the corresponding ones for Logic Pro- gramming (LP), since by choosing a particular semiring (the one with just two elements, true and false , and the logical and and or as the two semiring opera- tions) we get exactly the LP semantics. The extension is in some cases predictable but it possesses some crucial new features. We also show the equivalence of the three semantics. In particular, we prove that, given the set of all refutations starting from a given goal, it is possible to derive the declarative meaning of both the existential closure of the goal and its universal closure. Moreover, we investigate the decidability of the semantics of SCLP programs and we prove that if a goal has a semiring value greater than a certain value in the semiring, then we can discover this in finite time. Classical Operational Research (OR) problems and their embedding in the SCLP framework are also studied. The embedding seems to be able to 1) give a new semantics w.r.t. the algorithmic one and 2) give some hints towards an ex- tension of the SCLP framework to handle multilevel and multisorted problems. More precisely, the “levels of preference” together with a constraint framework can be used fruitfully to describe and solve optimization problems. In fact, solv- ing a problem does not mean finding “a solution”, but finding the best one (in the sense of the semiring) . This intuition suggests we investigate around the op- erational research field in order to find out how to describe and solve classical problems that usually are solved using OR techniques. 1.5 Overview of the Book 19 In the last part of the book we describe some new results related to the semiring framework. An extension of the concurrent constraint language (cc) is presented. The language is able to deal with soft constraints instead of with the crisp ones. The idea of thresholds is added to the new language, and a new “branch&bound” semantics is given. Using the introduced language we show how to use the SCSP framework to discovery security problems in the network. In particular we study what happens while a protocol session is executed. To do this we first model the policy of the protocol and the initial state of the network as SCSPs, and then we compare the policy SCSP with the initial one, modified by the protocol session. Then a notion of Neighborhood Interchangeability for soft constraints is in- troduced. As in the crisp case, detecting interchangeabilities among domain val- ues improve the performance of the solver. Interchangeability can also be used as a basis for search heuristics, solution adaptation and abstraction techniques 1.5.1 Structure of Subsequent Chapter In Chapter 1 we introduce some background material: some basic notions re- lated to Constraint Satisfaction Problems (CSPs) and to the Constraint Logic Programming (CLP) framework. In Chapter 2 we introduce the Soft CSP (SCSP) framework. The framework is based on the notion of semiring, that is, a set plus two operations. Different instantiations of the two operations give rise to different existing frameworks (Fuzzy CSP, Probabilistic, Classical, VCSP, etc.). Each of these frameworks satisfies specific properties that are useful in testing the applicability of the constraint preprocessing and solving techniques described in Chapter 3. In Chapter 3 the properties studied in the previous chapter are applied to the different frameworks in order to prove the applicability of soft local consistency and dynamic programming techniques. These techniques are defined starting from the classical ones, by using the semiring operations. We also generalize the local consistency technique by reducing the needed properties of the semiring operators and by using different functions in the local consistency steps. Some ideas on the efficient applicability of these techniques are given, by looking at the graph structure of the problem. In Chapter 4 classical techniques of abstraction are applied to SCSPs. The problem is mapped in an ” easier” one, some solution related information is found and mapped back to the original problem. The soft local consistency techniques are also proven to be useful in the abstract framework to find the set of optimal solutions or one of its approximations. In Chapter 5 a more structured view of the SCSP framework is given: do- mains and semirings are used as basic elements for building high order functions representing solution or preprocessing algorithms. In chapter 6 the CLP framework is extended to deal with soft constraints. We define the Soft CLP (SCLP) framework and we give an operational, model- theoretic and fix-point semantics. Some equivalence and properties of the se- mantics are proven. 20 1. Introduction In Chapter 7 we show how the ability of the CLP language to deal with soft constraints can be used to represent and solve in a declarative fashion OR prob- lems. As an example we consider general shortest path problems over partially ordered criteria and we show how the SCLP framework can easily represent and solve them. Moreover, we give a semantics to a class of SCLP programs by using a classical shortest-path algorithm. In Chapter 8 the extension of the concurrent constraint language (cc) able to deal with soft constraints is presented. We first give a functional formalization of the semiring framework that will also be used in the next two chapter. Then syntax and semantics of the new language is given. In Chapter 9 we describe the notion of soft Neighborhood Interchangeability. As in the crisp case interchangeabilities are very rare. For this reason we extend the interchangeability definition with a notion of threshold and degradation. In Chapter 10 we try to enlarge the applicability domain of the constraint framework, by defining a mapping between a network of agents executing a protocol and an SCSP. Some security properties of the network are translated into specific properties of the SCSP solutions. In Chapter 11 we give some final remarks and some directions for future research. 1.5.2 The Origin of the Chapters Many chapters of this book are based on already published papers, jointly with Giampaolo Bella, Philippe Codognet, Boi Faltings, Helene Fargier, Rossella Gen- nari, Yan Georget, Ugo Montanari, Nicoleta Neagu, Elvinia Riccobene, Francesca Rossi, Thomas Schiex and Gerard Verfaillie. In particular: — The basic definitions and properties of the soft constraints’ framework de- scribed in Chapter 2 appear in [45,47]; moreover the mapping between SC- SPs and VCSPs is based on the ideas developed in [38,39]; — The solutions and preprocessing techniques described in Chapter 3 are in- stead introduced in [45,47] and extended in [34,43,44,54]; — Chapter 4 describe the abstraction framework and develops the ideas pre- sented in [33,35,36]; — Chapter 5 is only based on some preliminary work presented in [49]; — The logic language to program with soft constraints of Chapter 6 is intro- duced in [46,53]; an extended version of the work appeared in [50]; — Chapter 7 is based on the ideas developed in [48,51]; — The soft concurrent constraint framework described in Chapter 8 appeared in [52]; — Chapter 9 is based on the ideas developed in [37, 55] . — The use of soft constraints for security protocol quantitative analysis intro- duced in Chapter 10 is based on the works presented in [17,18,19]. 2. Soft Constraint Satisfaction Problems Three Rings for the Elven-kings under the sky, Seven for the Dwarf-lords in their halls of stone, Nine for the Mortal Men doomed to die. One for the Dark Lord on his dark throne. In the Land of Mordor where the Shadows lie. One Ring to rule them all, One Ring to find them, One Ring to bring them all and in the darkness bind them. In the Land of Mordor where the Shadows lie. Tolkien, J.R.R. The Lord of the Rings Overview We introduce a general framework for constraint satisfaction and opti- mization where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. The framework is based on a se- miring structure, where the carrier set of the semiring specifies the values to be associated with each tuple of values of the variable domain, and the two semiring operations (+ and x) model constraint projection and combination respectively. Classical constraint satisfaction problems (CSPs) [139, 150] are a very ex- pressive and natural formalism to specify many kinds of real-life problems. In fact, problems ranging from map coloring, vision, robotics, job-shop scheduling, VLSI design, and so on, can easily be cast as CSPs and solved using one of the many techniques that have been developed for such problems or subclasses of them [104,105,138,140,150]. They also, however, have evident limitations, mainly due to the fact that they do not appear to be very flexible when trying to represent real-life scenarios where the knowledge is neither completely available nor crisp. In fact, in such situations, the ability of stating whether an instantiation of values to variables is allowed or not, is not enough or sometimes not even possible. For these reasons, it is natural to try to extend the CSP formalism in this direction. For example, in [91,165,167] CSPs were extended with the ability to associate with each tuple, or to each constraint, a level of preference, and with the possibil- ity of combining constraints using min-max operations. This extended formalism were called Fuzzy CSPs (FCSPs) . Other extensions concern the ability to model incomplete knowledge of the real problem [96], to solve over-constrained prob- lems [108], and to represent cost optimization problems [31]. S. Bistarelli: Semirings for Soft Constraint Solving..., LNCS 2962, pp. 21—50, 2004. (c) Springer- Verlag Berlin Heidelberg 2004 22 2. Soft Constraint Satisfaction Problems In this chapter we describe a constraint solving framework where all such extensions, as well as classical CSPs, can be cast. We do not, however, relax the assumption of a finite domain for the variables of the constraint problems. The main idea is based on the observation that a semiring (that is, a domain plus two operations satisfying certain properties) is all that is needed to describe many constraint satisfaction schemes. In fact, the domain of the semiring provides the levels of consistency (which can be interpreted as cost, or degrees of preference, or probabilities, or others), and the two operations define a way to combine constraints together. More precisely, we define the notion of constraint solving over any semiring. Specific choices of the semiring will then give rise to different instances of the framework, which may correspond to known or new constraint solving schemes. The notion of semiring for constraint solving was used also in [114]. However, the use of such a notion is completely different from ours. In fact, in [114] the semiring domain (hereby denoted by A) is used to specify the domain of the variables, while here we always assume a finite domain (hereby denoted by D) and A is used to model the values associated with the tuples of values of D. The chapter is organized as follows. Section 2.1 defines c-semirings and their properties. Then Section 2.2 introduces constraint problems over any semirings and the associated notions of solution and consistency. Then Section 2.3 studies several instances of the SCSP framework, and in particular studies the differences between the framework presented in [174] and ours. The basic definitions and properties of the soft constraints’ framework de- scribed in this chapter appear in [45,47]; moreover the mapping between SCSPs and VCSPs [174] is based on the ideas developed in [38,39]. 2.1 C-semirings and Their Properties We extend the classical notion of constraint satisfaction to allow also for 1) non- crisp statements and 2) a more general interpretation of the operations on such statements. This allows us to model both classical CSPs and several extensions of them (like fuzzy CSPs [91,167], partial constraint satisfaction [108], and so on). To formally do that, we associate a semiring with the standard notion of constraint problem, so that different choices of the semiring represent different concrete constraint satisfaction schemes. In fact, such a semiring will give us both the domain for the non-crisp statements and also the allowed operations on them. Definition 2.1.1 (semiring). A semiring is a tuple {A, sum, x,0, 1) such that — A is a set and 0,1 € A; — sum, called the additive operation, is a commutative (i.e., sum(a,b) = sum(b,a)) and associative (i.e., sum(a, sum(b, c)) = sum(sum(a,b), c)) op- eration with 0 as its unit element (i.e., sum(a,0) = a = sum(0, a)J; — x, called the multiplicative operation, is an associative operation such that 1 is its unit element and 0 is its absorbing element (i.e., a x 0 = 0 = 0 x a);