*Guide to Constraint
Programming*
*©
Roman Barták, 1998*
**Up**

The constraints in classical constraint satisfaction problems are crisp, i.e., they 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 constraints, probabilities or weights respectively. These extensions can be used to solve optimization problems as well as to solve over-constrained problems as they allow relaxing of constraints.

Fuzzy CSPs extend the notion of classical CSPs by allowing non-crisp constraints, that is, constraints which associate a preference level with each tuple of values. Such level is always between 0 and 1, where 1 represents the best value (i.e., the tuple is allowed) and 0 the worst one (i.e., the tuple is not allowed). The solution of a fuzzy CSP is then defined as the set of tuples of values (for all variables) which have the maximal value. The way they associate a values with an n-tuple is by minimizing the values of all its subtuples. The reason for such a max-min framework relies on the attempt to maximize the value of the least preferred tuple.A

Fuzzy Constraint Satisfaction Problem(FCSP) consist of:

- a set of
variablesX={x_{1},...,x_{n}},- for each variable x
_{i}, a finite set D_{i}of possible values (itsdomain),- and a set of
constraints; each constraintcis defined by a function fuzzy levelfl (c,A), that assigns a real number between 0 and 1 to each tupleAof valuesA

solution to a FCSPis an assignment of a value from its domain to every variable such that the expression min{fl(c,A)|cis a constraint in FCSP} is maximized among all possible assignmentsAof values.

Probabilistic CSP (Prob-CSP)

Probabilistic CSPs (Prob-CSPs) have been introduced to model those situation where each constraintchas a certain probabilityp(c), independent from the the probability of the other constraints, to be part of the given problem (actually, the probability is not of the constraint, but of the situation which corresponds to the constraint: saying thatchas probabilitypmeans that the situation corresponding tochas probabilitypof occurring in the real-life problem).This allows one to reason also about problems which are only partially known. The probability levels on constraints gives then, to each instantiation of all variables, a probability that it is a solution of the real problem. This is done by first associating with each subset of constraints the probability that it is in the real problem (by multiplying probabilities of the involved constraints), and then by summing up all the probabilities of the subsets of constraints where the considered instantiation is a solution. Alternatively, the probability associated with an n-tuple t can also be seen as the probability that all constraints that t violates are indeed in the real problem. This is just the product of all 1-p(c) for all c violated by t. Finally, the aim is to get those instantiations with the maximum probability.

A

Probabilistic Constraint Satisfaction Problem(Prob-CSP) consist of:

- a set of
variablesX={x_{1},...,x_{n}},- for each variable x
_{i}, a finite set D_{i}of possible values (itsdomain),- and a set of
constraintsrestricting the values that the variables can simultaneously take; each constraintchas also assigned a certain probabilityp(c)to be part of the given problem.There are two alternative approaches to define the

solution to a Prob-CSP. Again, the solution is an assignment of a value from its domain to every variable such that

- the expression Sum{Product{
p(c)) |cis a constraint in S} | S is a subset of the set of all constraints satisfied byA} is maximized among all possible assignmentsAof values, or- the expression Product{(1-
p(c)) |cis a constraint in FCSP violated byA} is maximized among all possible assignmentsAof values.

Weighted CSP (WCSP)

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. Therefore, in WCSPs the cost function is defined by summing up the costs of all constraints (indented as the cost of the chosen tuple for each constraint). Thus, the goal is to find the n-tuples (wherenis the number of all variables) which minimize the total sum the costs of their subtuples (one for each constraint).A

Weighted Constraint Satisfaction Problem(WCSP) consist of:

- a set of
variablesX={x_{1},...,x_{n}},- for each variable x
_{i}, a finite set D_{i}of possible values (itsdomain),- and a set of
constraints; each constraintcis defined by a function costw(c,A), that assigns a non-negative real number to each tupleAof valuesA

solution to a WCSPis an assignment of a value from its domain to every variable such that the expression Sum{w(c,A)|cis a constraint in FCSP} is minimized among all possible assignmentsAof values.

Egalitarianism and Utilitarianism

The FCSP and the WCSP systems can be seen as two different approaches to give a meaning to the notion of optimization. The two models correspond in fact to two definitions of social welfare in utility theory:

egalitarianism, which maximizes the minimal individual utility, andutilitarianism, which maximizes the sum of the individual utilities.FCSPs are based on the egalitarianistics approach to optimization problems (that is, they aim at maximizing the overall level of consistency while balancing the levels of all constraints), while WCSPs have an utilitarianistics approach (that is, they aim at getting the minimum cost globally, even though some constraints may be neglected and thus present a big cost).

based on S. Bistarelli, U. Montanary, F. Rossi: Semiring-based Constraint Satisfaction and Optimization

**Up**
*Designed and
maintained by **Roman
Barták*