Fuzzy CSP (FCSP)Guide to Constraint
Programming ©
Roman Barták, 1998
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 CSP (FCSP)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 variables X={x1,...,xn},
- for each variable xi, a finite set Di of possible values (its domain),
- and a set of constraints; each constraint c is defined by a function fuzzy level fl (c,A), that assigns a real number between 0 and 1 to each tuple A of values
A solution to a FCSP is an assignment of a value from its domain to every variable such that the expression min{fl(c,A) | c is a constraint in FCSP} is maximized among all possible assignments A of values.
Probabilistic CSP (Prob-CSP)Probabilistic CSPs (Prob-CSPs) have been introduced to model those situation where each constraint c has a certain probability p(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 that c has probability p means that the situation corresponding to c has probability p of 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 variables X={x1,...,xn},
- for each variable xi, a finite set Di of possible values (its domain),
- and a set of constraints restricting the values that the variables can simultaneously take; each constraint c has also assigned a certain probability p(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)) | c is a constraint in S} | S is a subset of the set of all constraints satisfied by A} is maximized among all possible assignments A of values, or
- the expression Product{(1-p(c)) | c is a constraint in FCSP violated by A} is maximized among all possible assignments A of 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 (where n is 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 variables X={x1,...,xn},
- for each variable xi, a finite set Di of possible values (its domain),
- and a set of constraints; each constraint c is defined by a function cost w(c,A), that assigns a non-negative real number to each tuple A of values
A solution to a WCSP is an assignment of a value from its domain to every variable such that the expression Sum{w(c,A) | c is a constraint in FCSP} is minimized among all possible assignments A of values.
Egalitarianism and UtilitarianismThe 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, and
- utilitarianism, 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