Skip to main content

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);