Constraint Solving

Basic Introductory Tutorial on Soft Constraints

INTRODUCTION

Constraint logic programming has evolved as a major programming paradigm for solving real-life problems. All instances of problems can be represented as relationships between the objects involved and the problem can be solved by making sure that those relationships can be satisfied.

Lot of problems in real-life cannot be expected to have a perfect solution. Most of the problems that are required to be solved are over-constrained and so most of the times don’t lead to any solution. In such situations we need to relax the restrictions so that we can at least find a solution which is as close as possible to the expected solution. This is definitely much better than not finding a solution at all solitaire. Some of the constraints can be differentiated as required while others as preferential constraints.

Constraint hierarchy forms the set of both hard and soft constraints. So in such cases what we need to do is soften the restrictions or constraints on those problems and then try to obtain a solution that is as optimal as possible. Soft constraints give more scope for relaxing the restrictions and attaching concepts such as cost and priorities to the constraints depending on the preference of the constraint being satisfied in the CSP. They are comparatively very expressive as they provide us with an idea of which constraint is preferred over the other and this is helpful in cases where we don’t find a solution spiele spielen ohne herunterladen. However soft constraints at the same time can be more difficult to handle.

So the concept of soft constraints is that constraints are ranked according to their importance and the form that satisfies the maximum high ranking constraints is considered the optimal.

CONSTRAINT HANDLING RULES

CHR provide simplification and propagation of user defined constraints.

Simplification in the sense that they replace constraints by constraints which are much simpler and propagation adds new constraints which are logically redundant but may cause further simplification

Soft Constraints can be described by the type of ordering or scoring that can be done. It can be classified in to two types basically

a) Assigning values to each possible tuple in a constraint

b) Assigning a value to the actual constraint itself.

MODELING OF SOFT CONSTRAINTS

Soft Constraints can be modeled in a number of ways using these two methods.

– Fuzzy CSP’s for example allow constraint tuples to have an associated preference, like for example 1 = best and 0 = worst markt.de.

– While fuzzy CSPs associate a level of preference with each tuple in each constraint, in weighted CSPs (WCSPs) tuples come with an associated cost. This allows one to model optimization problems where the goal is to minimize the total cost (time, space, number of resources, …) of the proposed solution

– According to Roman Bartak Fuzzy CSP aims at maximizing the overall level of consistency while balancing the level of all constraints. On the other hand Weighted CSP’s aim at getting the minimum cost globally, even though some constraints may be neglected and thus present a big cost.

BASIC FRAMEWORK OF SOFT CONSTRAINTS

A more general way of explaining over-constrained problems has been proposed by Stefano Bistarelli where can I mojave. He calls this framework as the Semiring-based Constraint Satisfaction problem.

Bistarelli’s main idea is that:

A semi-ring (that is, a domain plus two operations satisfying certain properties) is all that is needed to satisfy 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 preferences 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 semiring will then give rise to different instances of the framework which may correspond to new constraint solving schemes.

A c-semiring is a quintuple (A,+, x, 0, 1) such that

OTHER SOFT CSP FRAMEWORKS

Bistarelli showed that some of the previous constraint satisfaction approaches can be seen as instances of this theory differing only in the choice of the semiring.

Classical: Constraints in a classical CSP can be modeled with a semi-ring containing only 1 and 0 in A. Also constraint combination can be modeled with logical and the projection over some of the variables with logical or. Thus a CSP can be seen as a SCSP with the following semiring

S (CSP) = ({0, 1}, ⋁, ⋀, 0, 1)

Fuzzy CSP: Fuzzy CSP’s allow for associating a preference level with each tuple of values. This level of preference lies between 0 and 1. The solution of a fuzzy CSP is defined as a set of tuples of values for all the variables which have a maximal value Download photoimpact 6 for free. Fuzzy CSP’s can be modeled in the SCSP framework by choosing the following semiring.

S (FCSP) = ({x/x ∈ [0, 1]}, max, min, 0, 1)

Probablistic CSP: In Probabilistic CSP’s each constraint c has an associated probability p(c). c has probability p means that the situation corresponding to c has probability p of occurring in the real-life problem. The semi-ring corresponding to the probabilistic CSP is as follows.

S (prob) = ({x/x ∈ [0, 1]}, max, X, 0,1)

Weighted CSP: While Fuzzy CSPs’ come with preferences, Constraints are associated with costs in weighted CSP’s. The solution to a problem in such models is the one with minimum cost. The associated semiring for a weighted CSP is

S (WSCP) = (R^*, min, +, ∞, 0)

APPLICATIONS OF SOFT CONSTRAINTS