Semirings for Soft Constraint Solving and Programming

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 ×, 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 × 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 × 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) 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.