Abstracting soft constraints.
Soft constraints are very flexible and expressive. However, they are also very complex to handle. For this reason, it may be reasonable in several cases to pass to an abstract version of a given soft constraint problem, and then to bring some useful information from the abstract problem to the concrete one. This will hopefully make the search for a solution, or for an optimal solution, of the concrete problem, faster.In this paper we propose an abstraction scheme for soft constraint problems and we study its main properties. We show that processing the abstracted version of a soft constraint problem can help us in finding good approximations of the optimal solutions, or also in obtaining information that can make the subsequent search for the best solution easier.We also show how the abstraction scheme can be used to devise new hybrid algorithms for solving soft constraint problems, and also to import constraint propagation algorithms from the abstract scenario to the concrete one. This may be useful when we don't have any (or any efficient) propagation algorithm in the concrete setting.
Introduction
Classical constraint satisfaction problems (CSPs) [18] are a very convenient and
expressive formalism for many real-life problems, like scheduling, resource al-
location, vehicle routing, timetabling, and many others [23]. However, many of
these problems are often more faithfully represented as soft constraint satisfaction
problems (SCSPs), which are just like classical CSPs except that each
assignment of values to variables in the constraints is associated to an element
taken from a partially ordered set. These elements can then be interpreted as
levels of preference, or costs, or levels of certainty, or many other criteria.
There are many formalizations of soft constraint problems. In this paper
we consider the one based on semirings [4, 3], where the semiring species the
partially ordered set and the appropriate operation to use to combine constraints
together.
Although it is obvious that SCSPs are much more expressive than classical
CSPs, they are also more di-cult to process and to solve. Therefore, sometimes it
may be too costly to nd all, or even only one, optimal solution. Also, although
classical propagation techniques like arc-consistency [17] can be extended to
SCSPs [4], even such techniques can be too costly to be used, depending on the
size and structure of the partial order associated to the SCSP.
For these reasons, it may be reasonable to work on a simplied version of the
given problem, trying however to not loose too much information. We propose to
dene this simplied version by means of the notion of abstraction, which takes
an SCSP and returns a new one which is simpler to solve. Here, as in many
other works on abstraction [16, 15], \simpler" may mean many things, like the
fact that a certain solution algorithm nds a solution, or an optimal solution, in
a fewer number of steps, or also that the abstracted problem can be processed
by a machinery which is not available in the concrete context.
There are many formal proposals to describe the process of abstracting a
notion, be it a formula, or a problem [16], or even a classical [11] or a soft CSP
[21]. Among these, we chose to use one based on Galois insertions [5], mainly
to refer to a well-know theory, with many results and properties that can be
useful for our purposes. This made our approach compatible with the general
theory of abstraction in [16]. Then, we adapted it to work on soft constraints:
given an SCSP (the concrete one), we get an abstract SCSP by just changing
the associated semiring, and relating the two structures (the concrete and the
abstract one) via a Galois insertion. Note that this way of abstracting constraint
problems does not change the structure of the problem (the set of variables
remains the same, as well as the set of constraints), but just the semiring values
to be associated to the tuples of values for the variables in each constraint.
Once we get the abstracted version of a given problem, we propose to
1. process the abstracted version: this may mean either solving it completely,
or also applying some incomplete solver which may derive some useful information
on the abstract problem;
2. bring back to the original problem some (or possibly all) of the information
derived in the abstract context;
3. continue the solution process on the transformed problem, which is a concrete
problem equivalent to the given one.
All this process has the main aim of nding an optimal solution, or an approximation
of it, for the original SCSP, within the resource bounds we have. The
hope is that, by following the above three steps, we get to the nal goal faster
than just solving the original problem.
A deep study of the relationship between the concrete SCSP and the corresponding
abstract one allows us to prove some results which can help in deriving
useful information on the abstract problem and then take some of the derived
information back to the concrete problem. In particular, we can prove the following

{ If the abstraction satises a certain property, all optimal solutions of the
concrete SCSP are also optimal in the corresponding abstract SCSP (see
Theorem 4). Thus, in order to nd an optimal solution of the concrete prob-
lem, we could nd all the optimal solutions of the abstract problem, and
then just check their optimality on the concrete SCSP.
{ Given any optimal solution of the abstract problem, we can nd upper and
lower bounds for an optimal solution for the concrete problem (see Theorem
5). If we are satised with these bounds, we could just take the optimal
solution of the abstract problem as a reasonable approximation of an optimal
solution for the concrete problem.
{ If we apply some constraint propagation technique over the abstract problem,
say P , obtaining a new abstract problem, say P some of the information in
can be inserted into P , obtaining a new concrete problem which is closer
to its solution and thus easier to solve (see Theorem 6 and 8).
This however can be done only if the semiring operation which describes how
to combine constraints on the concrete side is idempotent (see Theorem 6).
{ If instead this operation is not idempotent, still we can bring back some information
from the abstract side. In particular, we can bring back the inconsistencies
(that is, tuples with associated the worst element of the semiring),
since we are sure that these same tuples are inconsistent also in the concrete
SCSP (see Theorem 8).
In both the last two cases, the new concrete problem is easier to solve, in the
sense, for example, that a branch-and-bound algorithm would explore a smaller
(or equal) search tree before nding an optimal solution.
The paper is organized as follows. First, in Section 2 we give the necessary
notions about soft CSPs and abstraction. Then, in Section 3 we dene our notion
of abstraction, and in Section 4 we prove properties of our abstraction scheme
and discuss some of their consequences. Finally, in Section 7 we summarize our
work and give hints about future directions.
Background
In this section we recall the main notions about soft constraints [4] and abstract
interpretation [5], that will be useful for the developments and results of this
paper.
2.1 Soft constraints
In the literature there are many formalizations of the concept of soft constraints
[21, 8, 13, 10]. Here we refer to the one described in [4, 3], which however can be
shown to generalize and express many of the others [4, 2]. In a few words, a soft
constraint is just a classical constraint where each instantiation of its variables
has an associated value from a partially ordered set. Combining constraints will
then have to take into account such additional values, and thus the formalism
has also to provide suitable operations for combination () and comparison (+)
of tuples of values and constraints. This is why this formalization is based on
the concept of semiring, which is just a set plus two operations.
Denition 1 (semirings and c-semirings). A semiring is a tuple hA;
such
{ A is a set and 0; 1 2 A;
{ + is commutative, associative and 0 is its unit element;
{  is associative, distributes over +, 1 is its unit element and 0 is its absorbing
element.
A c-semiring is a semiring is idempotent with 1 as
its absorbing element and  is commutative.
Let us consider the relation S over A such that a S b i a
it is possible to prove that (see [4]):
{ S is a partial
{ and  are monotone on S ;
{ 0 is its minimum and 1 its maximum;
{ lattice and, for all a; b 2 A, a
Moreover, if  is idempotent, then hA; S i is a complete distributive lattice and
is its glb. Informally, the relation S gives us a way to compare (some of the)
tuples of values and constraints. In fact, when we have a S b, we will say that
b is better than a.
Denition 2 (constraints). Given a c-semiring
set D (the domain of the variables), and an ordered set of variables V , a constraint
is a pair hdef; coni where con  V and A.
Therefore, a constraint species a set of variables (the ones in con), and assigns
to each tuple of values of D of these variables an element of the semiring set
A. This element can then be interpreted in several ways: as a level of preference,
or as a cost, or as a probability, etc. The correct way to interpret such elements
depends on the choice of the semiring operations.
Constraints can be compared by looking at the semiring values associated to
the same tuples: Consider two constraints c
with (t). The relation
vS is a partial order. In the following we will also use the obvious extension
of this relation to sets of constraints, and also to problems (seen as sets of con-
straints). Therefore, given two SCSPs P 1 and P 2 with the same graph topology,
we will write P 1 vS P 2 if, for each constraint c 1 in P and the corresponding
constraint c 2 in P 2 , we have that c 1 vS c 2 .
Denition 3 (soft constraint problem). A soft constraint satisfaction problem
(SCSP) is a pair hC; coni where con  V and C is a set of constraints.
Note that a classical CSP is a SCSP where the chosen c-semiring is:
Fuzzy CSPs [8, 19, 20] can instead be modeled in the SCSP framework by
choosing the c-semiring:

Figure

1 shows a fuzzy CSP. Variables are inside circles, constraints are represented
by undirected arcs, and semiring values are written to the right of the
corresponding tuples. Here we assume that the domain D of the variables contains
only elements a and b.
. 0.9
b . 0.5
a . 0.9
b . 0.1
aa . 0.8
ab . 0.2
ba . 0
bb . 0
Fig. 1. A fuzzy CSP.
Denition 4 (combination). Given two constraints c
combination cc 2 is the constraint hdef; coni dened
by
. The combina-
tion
operator
can be straightforward extended also to sets of constraints: when
applied to a set of constraints C, we will write
In words, combining two constraints means building a new constraint involving
all the variables of the original ones, and which associates to each tuple of
domain values for such variables a semiring element which is obtained by multiplying
the elements associated by the original constraints to the appropriate
subtuples.
Using the properties of  and +, it is easy to prove that:
{
is associative, commutative, and monotone over vS ;
{ if  is
idempotent,
is idempotent as well.
Denition 5 (projection). Given a constraint c = hdef; coni and a subset I
of V , the projection of c over I, written c I , is the constraint
t=t# con
I\con =t 0 def(t).
Informally, projecting means eliminating some variables. This is done by
associating to each tuple over the remaining variables a semiring element which is
the sum of the elements associated by the original constraint to all the extensions
of this tuple over the eliminated variables.
Denition 6 (solution). The solution of a SCSP problem is the
constraint
That is, to obtain the solution of an SCSP, we combine all constraints, and
then project over the variables in con. In this way we get the constraint over con
which is \induced" by the entire SCSP.
For example, each solution of the fuzzy CSP of Figure 1 consists of a pair
of domain values (that is, a domain value for each of the two variables) and
an associated semiring element (here we assume that con contains all variables).
Y we mean the projection of tuple t, which is dened over the set of variables
X, over the set of variables Y  X.
Such an element is obtained by looking at the smallest value for all the subtuples
(as many as the constraints) forming the pair. For example, for tuple ha; ai (that
we have to compute the minimum between 0:9 (which is the value
(which is the value for (which is the value
for Hence, the resulting value for this tuple is 0:8.
Denition 7 (optimal solution). Given an SCSP problem P , consider Sol(P
hdef; coni. An optimal solution of P is a pair ht; vi such that
there is no t 0 such that v <S def(t 0 ).
Therefore optimal solutions are solutions which have the best semiring element
among those associated to solutions. The set of optimal solutions of an
SCSP P will be written as Opt(P ).
Denition 8 (problem ordering and equivalence). Consider two problems
then they have the same solution, thus we say that they are equivalent and we
The relation vP is a preorder. Moreover,
is an equivalence relation.
SCSP problems can be solved by extending and adapting the technique usually
used for classical CSPs. For example, to nd the best solution we could
employ a branch-and-bound search algorithm (instead of the classical backtrack-
ing), and also the successfully used propagation techniques, like arc-consistency
[17], can be generalized to be used for SCSPs.
The detailed formal denition of propagation algorithms (sometimes called
also local consistency algorithms) for SCSPs can be found in [4]. For the purpose
of this paper, what is important to say is that the generalization from classical
CSPs concerns the fact that, instead of deleting values or tuples, obtaining local
consistency in SCSPs means changing the semiring values associated to some
tuples or domain elements. The change always brings these values towards the
worst value of the semiring, that is, the 0. Thus, it is obvious that, given an SCSP
problem P and the problem P 0 obtained by applying some local consistency
algorithm to P , we must have Another important property of such
algorithms is that Sol(P local consistency algorithms do not
change the set of solutions.
2.2 Abstraction
Abstract interpretation [1, 5, 6] is a theory developed to reason about the relation
between two dierent semantics (the concrete and the abstract semantics). The
idea of approximating program properties by evaluating a program on a simpler
domain of descriptions of \concrete" program states goes back to the early 70's.
The inspiration was that of approximating properties from the exact (concrete)
semantics into an approximate (abstract) semantics, that explicitly exhibits a
structure (e.g., ordering) which is somehow present in the richer concrete structure
associated to program execution.
The guiding idea is to relate the concrete and the abstract interpretation of
the calculus by a pair of functions, the abstraction function  and the concretization
function
, which form a Galois connection.
Let (C; v) (concrete domain) be the domain of the concrete semantics, while
(abstract domain) be the domain of the abstract semantics. The partial
order relations re
ect an approximation relation. Since in approximation theory
a partial order species the precision degree of any element in a poset, it is
obvious to assume that if  is a mapping associating an abstract object in
concrete element in (C v), then the following holds: if (x)  y,
then y is also a correct, although less precise, abstract approximation of x. The
same argument holds if x v
(y). Then y is also a correct approximation of x,
although x provides more accurate information than
(y). This gives rise to the
following formal denition.
Denition 9 (Galois insertion). Let (C; v) and (A; ) be two posets (the
concrete and the abstract domain). A Galois connection h;
is a pair of maps
C such that
1.  and
are monotonic,
2. for each x 2 C; x v
3. for each y 2 A; (
Moreover, a Galois insertion (of A in C) h;
connection where
Property 2 is called extensivity of
. The map  (
is called the lower
(upper) adjoint or abstraction (concretization) in the context of abstract interpretation

The following basic properties are satised by any Galois insertion:
1.
is injective and  is surjective.
2.
is an upper closure operator in (C; v).
3.  is additive and
is co-additive.
4. Upper and lower adjoints uniquely determine each other. Namely,
A
fy 2 A j x
5.  is an isomorphism from (
)(C) to A, having
as its inverse.
An example of a Galois insertion can be seen in Figure 2. Here, the concrete
lattice is h[0; 1]; i, and the abstract one is hf0; 1g; i. Function  maps all real
numbers in [0; 0:5] into 0, and all other integers (in (0:5; 1]) into 1. Function
maps 0 into 0:5 and 1 into 1.
One property that will be useful later relates to a precise relationship between
the ordering in the concrete lattice and that in the abstract one.
}abstract lattice
concrete lattice1
a
a
Fig. 2. A Galois insertion.
Theorem 1 (total ordering). Consider a Galois insertion from (C; v) to
is a total order, also  is so.
Proof. It easy follows from the monotonicity of  (that is, x v y implies (x)
(y), and from its surjectivity (that is, there is no element in A which is not the
image of some element in C via ). 2
Usually, both the concrete and the abstract lattice have some operators that
are used to dene the corresponding semantics. Most of the times it is useful,
and required, that the abstract operators show a certain relationship with the
corresponding concrete ones. This relationship is called local correctness.
Denition C be an operator over the
concrete lattice, and assume that ~
f is its abstract counterpart. Then ~
f is locally
correct w.r.t. f if 8x
Abstracting soft CSPs
Given the notions of soft constraints and abstraction, recalled in the previous
sections, we now want to show how to abstract soft constraint problems. The
main idea is very simple: we just want to pass, via the abstraction, from an SCSP
P over a certain semiring S to another SCSP ~
P over the semiring ~
S, where the
lattices associated to ~
S and S are related by a Galois insertion as shown above.
Denition 11 (abstracting SCSPs). Consider the concrete SCSP problem
semiring S, where
{
{
we dene the abstract SCSP problem ~
C; coni over the semiring ~
where
~
{ ~
c n g with ~
{ if is the lattice associated to S and ~
i the lattice associated
to ~
S, then there is a Galois insertion h;
i such that  :
{ ~
is locally correct with respect to .
Notice that the kind of abstraction we consider in this paper does not change
the structure of the SCSP problem. That is, C and ~
C have the same number
of constraints, and c i and ~
involve the same variables. The only thing that is
changed by abstracting an SCSP is the semiring. Thus P and ~
P have the same
graph topology (variables and constraints), but dierent constraint denitions,
since if a certain tuple of domain values in a constraint of P has semiring value a,
then the same tuple in the same constraint of ~
P has semiring value (a). Notice
also that  and
can be dened in several dierent ways, but all of them have
to satisfy the properties of the Galois insertion, from which it derives, among
others, that
Example 1. As an example, consider any SCSP over the semiring for optimiza-
tion
(where costs are represented by negative reals) and suppose we want to abstract
it onto the semiring for fuzzy reasoning
In other words, instead of computing the maximum of the sum of all costs, we
just want to compute the maximum of the minimum of all costs, and we want to
normalize the costs over [0::1]. Notice that the abstract problem is in the FCSP
class and it has an idempotent  operator (which is the min). This means that
in the abstract framework we can perform local consistency over the problem
in order to nd inconsistencies. As noted above, the mapping
can be dened in dierent ways. For example one can decide
to map all the reals below some xed real x onto 0 and then to map the reals
in [x; 0] into the reals in [0; 1] by using a normalization function, for example
x .
Example 2. Another example is the abstraction from the fuzzy semiring to the
classical one:
Here function  maps each element of [0; 1] into either 0 or 1. For example, one
could map all the elements in [0; x] onto 0, and all those in (x; 1] onto 1, for some
xed x.

Figure

2 represents this example with
We have dened Galois insertions between two lattices hL; S i and h ~
~
of semiring values. However, for convenience, in the following we will often use
Galois insertions between lattices of problems hPL; vS i and h ~
contains problems over the concrete semiring and ~
PL over the abstract semiring.
This does not change the meaning of our abstraction, we are just upgrading the
Galois insertion from semiring values to problems. Thus, when we will say that
~
mean that ~
P is obtained by P via the application of  to all
the semiring values appearing in P .
An important property of our notion of abstraction is that the composition
of two abstractions is still an abstraction. This allows to build a complex abstraction
by dening several simpler abstractions to be composed.
Theorem 2 (abstraction composition). Consider an abstraction from the
lattice corresponding to a semiring S 1 to that corresponding to a semiring S 2 ,
denoted by the pair h 1 ;
1 i. Consider now another abstraction from the lattice
corresponding to the semiring S 2 to that corresponding to a semiring S 3 , denoted
by the pair h 2 ;
i. Then the
is an abstraction as well.
Proof. We rst have to prove that h;
the four
properties of a Galois insertion:
{ since the composition of monotone functions is again a monotone function,
we have that both  and
are monotone functions;
{ given a value x from the rst abstraction we have that x v 1
Moreover, for any element y we have that y v 2
This holds
also for thus by monotonicity of
1 we have x v 1
{ a similar proof can be used for the third property;
{ the composition of two identities is still an identity .
To prove that  3 is locally correct w.r.t.  1 , it is enough to consider the
local correctness of  2 w.r.t.  1 and of  3 w.r.t.  2 , and the monotonicity of
4 Properties and advantages of the abstraction
In this section we will dene and prove several properties that hold on abstractions
of soft constraint problems. The main goal here is to point out some of the
advantages that one can have in passing through the abstracted version of a soft
constraint problem instead of solving directly the concrete version.
4.1 Relating a soft constraint problem and its abstract version
Let us consider the scheme depicted in Figure 3. Here and in the following
pictures, the left box contains the lattice of concrete problems, and the right
one the lattice of abstract problems. The partial order in each of these lattices is
shown via dashed lines. Connections between the two lattices, via the abstraction
and concretization functions, is shown via directed arrows. In the following, we
will call the concrete semiring and ~
1i the
abstract one. Thus we will always consider a Galois insertion h;
abstract problems
concrete problems
a
a
a
a
Fig. 3. The concrete and the abstract problem.
In

Figure

3, P is the starting SCSP problem. Then with the mapping  we
get ~
which is an abstraction of P . By applying the mapping
to ~
we get the problem
us rst notice that these two problems (P and
((P ))) are related by a precise property, as stated by the following theorem.
Theorem 3. Given an SCSP problem P over S, we have that P vS
Proof. Immediately follows from the properties of a Galois insertion, in particular
from the fact that x S
for any x in the concrete lattice. In fact,
((P means that, for each tuple in each constraint of P , the semiring
value associated to such a tuple in P is smaller (w.r.t. S ) than the corresponding
value associated to the same tuple in
Notice that this implies that, if a tuple in
((P semiring value 0, then
it must have value 0 also in P . This holds also for the solutions, whose semiring
value is obtained by combining the semiring values of several tuples.
Corollary 1. Given an SCSP problem P over S, we have that Sol(P ) vS
Proof. We recall that Sol(P ) is just a constraint, which is obtained as
Thus the statement of this corollary comes from the monotonicity of  and +.Therefore, by passing from P to
((P )), no new inconsistencies are intro-
duced: if a solution of
((P )) has value 0, then this was true also in P . However,
it is possible that some inconsistencies are forgotten (that is, they appear to be
consistent after the abstraction process).
If the abstraction preserves the semiring ordering (that is, applying the abstraction
function and then combining gives elements which are in the same
ordering as the elements obtained by combining only), then there is also an interesting
relationship between the set of optimal solutions of P and that of (P ).
In fact, if a certain tuple is optimal in P , then this same tuple is also optimal in
us rst investigate the meaning of the order-preserving property.
Denition 12 (order-preserving abstraction). Consider two sets I 1 and I 2
of concrete elements. Then an abstraction is said to be order-preserving if
~
Y
~
Y
Y
Y
x
where the products refer to the multiplicative operations of the concrete (
the abstract ( ~
semirings.
In words, this notion of order-preservation means that if we rst abstract and
then combine, or we combine only, we get the same ordering (but on dierent
semirings) among the resulting elements.
Example 3. An abstraction which is not order-preserving can be seen in Figure 4.
Here, the concrete and the abstract sets, as well as the additive operations of the
two semirings, can be seen from the picture. For the multiplicative operations,
we assume they coincide with the glb of the two semirings.
In this case, the concrete ordering is partial, while the abstract ordering is
total. Functions  and  are depicted in the gure by arrows going from the
concrete semiring to the abstract one and vice versa. Assume that the concrete
problem has no solution with value 1. Then all solutions with value a or b are
optimal. Suppose a solution with value b is obtained by computing
we have a = 1a. Then the abstract counterparts will have values (1) 0
1. Therefore the solution with value a,
which is optimal in the concrete problem, is not optimal anymore in the abstract
problem.a b1g
a
a
a
a
Fig. 4. An abstraction which is not order-preserving.
Example 4. The abstraction in Figure 2 is order-preserving. In fact, consider two
abstract values which are ordered, that is 0  0 1. Then
where both x and y must be greater than 0:5. Thus their concrete combination
(which is the min), say v, is always greater than 0:5. On the other hand, 0 can
be obtained by combining either two 0's (therefore the images of two elements
smaller than or equal to 0:5, whose minimum is smaller than 0:5 and thus smaller
than v), or by combining a 0 and a 1, which are images of a value greater than
0:5 and one smaller than 0:5. Also in this case, their combination (the min) is
smaller than 0:5 and thus smaller than v. Thus the order-preserving property
holds.
Example 5. Another abstraction which is not order-preserving is the one that
passes from the semiring hN [ f+1g; min; sum; 0; +1i, where we minimize the
sum of values over the naturals, to the semiring hN [ f+1g; min; max; 0; +1i,
where we minimize the maximum of values over the naturals. In words, this
abstraction maintains the same domain of the semiring, and the same additive
operation (min), but it changes the multiplicative operation (which passes from
sum to max). Notice that the semiring orderings are the opposite as those usually
used over the naturals: if i is smaller than j then j S i, thus the best element
is 0 and the worst is +1. The abstraction function  is just the identity, and
also the concretization function
In this case, consider in the abstract semiring two values and the way they are
obtained by combining other two values of the abstract semiring: for example,
9). In the abstract ordering, 8 is higher than 9.
Then, let us see how the images of the combined values (the same values, since
is the identity) relate to each other: we have sum(7;
and 15 is lower than 10 in the concrete ordering. Thus the order-preserving
property does not hold.
Notice that, if we reduce the sets I 1 and I 2 to singletons, say x and y, then
the order-preserving property says that (x)  ~
S (y) implies that x S y. This
means that if two abstract objects are ordered, then their concrete counterparts
have to be ordered as well, and in the same way. Of course they could never be
ordered in the opposite sense, otherwise  would not be monotonic; but they
could be incomparable. Therefore, if we choose an abstraction where incomparable
objects are mapped by  onto ordered objects, then we don't have the
order-preserving property. A consequence of this is that if the abstract semiring
is totally ordered, and we want an order-preserving abstraction, then the
concrete semiring must be totally ordered as well.
On the other hand, if two abstract objects are not ordered, then the corresponding
concrete objects can be ordered in any sense, or they can also be not
comparable. Notice that this restriction of the order-preserving property to singleton
sets always holds when the concrete ordering is total. In fact, in this case,
if two abstract elements are ordered in a certain way, then it is impossible that
the corresponding concrete elements are ordered in the opposite way, because,
as we said above, of the monotonicity of the  function.
Theorem 4. Consider an abstraction which is order-preserving. Given an SCSP
problem P over S, we have that Opt(P )  Opt((P )).
Proof. Let us take a tuple t which is optimal in the concrete semiring S, with
value v. Then v has been obtained by multiplying the values of some subtuples.
Suppose, without loss of generality, that the number of such subtuples is two
(that is, we have two us then take the value
of this tuple in the abstract problem, that is, the abstract combination of the
abstractions of v 1 and We have to show that if v
is optimal, then also v 0 is optimal.
Suppose then that v 0 is not optimal, that is, there exists another tuple t 00
with value v 00 such that v 0 S 0 v 00 . Assume v
2 . Now let us see the
value of tuple t 00 in P . If we set v 00
have that this value is
us now compare v with  v. Since v 0  ~
we get that v S
v. But this means that v is not optimal, which was our initial
assumption. Therefore v 0 has to be optimal. 2
Therefore, in case of order-preservation, the set of optimal solutions of the
abstract problem contains all the optimal solutions of the concrete problem. In
other words, it is not allowed that an optimal solution in the concrete domain becomes
non-optimal in the abstract domain. However, some non-optimal solutions
could become optimal by becoming incomparable with the optimal solutions.
Thus, if we want to nd an optimal solution of the concrete problem, we could
nd all the optimal solutions of the abstract problem, and then use them on the
concrete side to nd an optimal solution for the concrete problem. Assuming
that working on the abstract side is easier than on the concrete side, this method
could help us nd an optimal solution of the concrete problem by looking at just
a subset of tuples in the concrete problem.
Another important property, which holds for any abstraction, concerns computing
bounds that approximate an optimal solution of a concrete problem. In
any optimal solution, say t, of the abstract problem, say with value ~ v, can
be used to obtain both an upper and a lower bound of an optimum in P . In
fact, we can prove that there is an optimal solution in P with value between
(~v) and the value of t in P . Thus, if we think that approximating the optimal
value with a value within these two bounds is satisfactory, we can take t as an
approximation of an optimal solution of P .
Theorem 5. Given an SCSP problem P over S, consider an optimal solution
of (P ), say t, with semiring value ~
v in (P ) and v in P . Then there exists an
optimal solution  t of P , say with value  v, such that v
(~v).
Proof. By local correctness of the multiplicative operation of the abstract semir-
ing, we have that v S
(~v). Since v is the value of t in P , either t itself is
optimal in P , or there is another tuple which has value better than v, say
v. We
will now show that
v cannot be greater than
(~v).
In fact, assume by absurd that
local correctness of the
multiplicative operation of the abstract semiring, we have that (v) is smaller
than the value of  t in (P ). Also, by monotonicity of , by
that ~
(v). Therefore by transitivity we obtain that ~
v is smaller than the
value of  t in (P ), which is not possible because we assumed that ~ v was optimal.
Therefore there must be an optimal value between v and
(~v). 2
Thus, given a tuple t with optimal value ~
v in the abstract problem, instead
of spending time to compute an exact optimum of P , we can do the following:
{ compute
(~v), thus obtaining an upper bound of an optimum of P ;
{ compute the value of t in P , which is a lower bound of the same optimum
of
{ If we think that such bounds are close enough, we can take t as a reasonable
approximation (to be precise, a lower bound) of an optimum of P .
Notice that this theorem does not need the order-preserving property in the
abstraction, thus any abstraction can exploit its result.
4.2 Working on the abstract problem
Consider now what we can do on the abstract problem, (P ). One possibility is
to apply an abstract function ~
f , which can be, for example, a local consistency
algorithm or also a solution algorithm. In the following, we will consider functions
~
f which are always intensive, that is, which bring the given problem closer to the
bottom of the lattice. In fact, our goal is to solve an SCSP, thus going higher in
the lattice does not help in this task, since solving means combining constraints
and thus getting lower in the lattice. Also, functions ~
f will always be locally
correct with respect to any function f sol which solves the concrete problem. We
will call such a property solution-correctness. More precisely, given a problem
P with constraint set C, f sol (P ) is a new problem P 0 with the same topology
as P whose tuples have semiring values possibly lower. Let us call C 0 the set of
constraints of P 0 . Then, for any constraint c
In other
words, f sol combines all constraints of P and then projects the resulting global
constraint over each of the original constraints.
Denition 13. Given an SCSP problem P over S, consider a function ~
f on
f is solution-correct if, given any f sol which solves P , ~
f is locally
correct w.r.t. f sol .
We will also need the notion of safeness of a function, which just means that
it maintains all the solutions.
Denition 14. Given an SCSP problem P and a function f : PL ! PL, f is
safe if Sol(P
It is easy to see that any local consistency algorithm, as dened in [4], can
be seen as a safe, intensive, and solution-correct function.
From ~
f((P )), applying the concretization function
, we get
which therefore is again over the concrete semiring (the same as P ). The following
property says that, under certain conditions, P and

f((P ))) are
equivalent. Figure 5 describes such a situation. In this gure, we can see that
several partial order lines have been drawn:
{ on the abstract side, function ~
f takes any element closer to the bottom,
because of its intensiveness;
{ on the concrete side, we have that

f((P ))) is smaller than both P and
because of the
properties
of
f((P ))) is smaller than
because of the monotonicity of
f((P ))) is higher than f sol (P ) because of the solution-correctness of
~
f sol (P ) is smaller than P because of the way f sol (P ) is constructed;
if  is idempotent, then it coincides with the glb, thus we have that

f((P ))) is higher than f sol (P ), because by denition the glb is
the higher among all the lower bounds of P and
a
a
x
O
a
a
a
a
a
a
x idempotent
concrete problems abstract problems
Fig. 5. The general abstraction scheme, with  idempotent.
Theorem 6. Given an SCSP problem P over S, consider a function ~
f on (P )
which is safe, solution-correct, and intensive. Then, if  is idempotent, Sol(P

Proof. Take any tuple t with value v in P , which is obtained by combining
the values of some subtuples, say two: us now consider the
abstract versions of v 1 and
f changes these values
by lowering them, thus we get ~
1 and ~
.
Since ~
f is safe, we have that v 0
~
f is solution-correct, thus v S
(v 0 ). By monotonicity of
, we have that
(v 0
2. This implies that
(v 0
(v 0
2 )), since
is idempotent by assumption and thus it coincides with the glb. Thus we have
that v S (
(v 0
(v 0
To prove that P and

f((P ))) give the same value to each tuple, we
now have to prove that
(v 0
(v 0
)). By commutativity of ,
we can write this as (v 1
(v 0
(v 0
and we have shown that v S
(v 0
(v 0
(v 0
(v 0
theorem does not say anything about the power of ~
f , which could make
many modications to (P ), or it could also not modify anything. In this last
case,
Figure 6), so

means that we have not gained anything in abstracting P . However, we can
always use the relationship between P and (P ) (see Theorem 4 and 5) to nd
an approximation of the optimal solutions and of the inconsistencies of P .
a f( ~ (P))
a
a
abstract problems
concrete problems
a
a
a
Fig. 6. The scheme when ~
f does not modify anything.
If instead ~
f modies all semiring elements in (P ), then if the order of the
concrete semiring is total, we have that


Figure

7), and thus we can work on
f((P ))) to nd the solutions of P . In
f((P ))) is lower than P and thus closer to the solution.
Theorem 7. Given an SCSP problem P over S, consider a function ~
f on (P )
which is safe, solution-correct, and intensive. Then, if  is idempotent, ~
f mod-
ies every semiring element in (P ), and the order of the concrete semiring is
total, we have that P wS
Proof. Consider any tuple t in any constraint of P , and let us call v its semiring
value in P and v sol its value in f sol (P ). Obviously, we have that v sol S v.
Now take v
((v)). By monotonicity of , we cannot have v <S v 0 . Also,
by solution-correctness of ~
f , we cannot have v 0 <S v sol . Thus we must have
which proves the statement of the theorem. 2
Notice that we need the idempotence of the  operator for Theorem 6 and
7. If instead  is not idempotent, then we can prove something weaker. Figure
8 shows this situation. With respect to Figure 5, we can see that the possible
non-idempotence of  changes the partial order relationship on the concrete
side. In particular, we don't have the problem

f((P ))) any more, nor the
problem f sol (P ), since these problems would not have the same solutions as P
a
a
a
l
r
d
e
r
abstract problems
concrete problems
a
a
a
a
a
Fig. 7. The scheme when the concrete semiring has a total order.
and thus are not interesting to us. We have instead a new problem P 0 , which is
constructed in such a way to \insert" the inconsistencies of
obviously lower than P in the concrete partial order, since it is the same
as P with the exception of some more 0's, but the most important point is that
it has the same solutions as P .
a
a
a
a
a
a
a
x not idempotent
concrete problems abstract problems
Fig. 8. The scheme when  is not idempotent.
Theorem 8. Given an SCSP problem P over S, consider a function ~
f on (P )
which is safe, solution-correct and intensive. Then, if  is not idempotent, consider
P 0 to be the SCSP which is the same as P except for those tuples which
have semiring value 0 in
these tuples are given value 0 also in P 0 .
Then we have that Sol(P
Proof. Take any tuple t with value v in P , which is obtained by combining
the values of some subtuples, say two: us now consider the
abstract versions of v 1 and
f changes these values
by lowering them, thus we get ~
1 and ~
.
Since ~
f is safe, we have that v 0
f is
solution-correct, thus v S
(v 0 ). By monotonicity of
, we have that
(v 0
2. Thus we have that v S
(v 0
2.
Now suppose that
(v 0
This implies that also Therefore, if we
set again the combination of v 1 and v 2 will result in v, which is 0. 2
Summarizing, the above theorems can give us several hints on how to use the
abstraction scheme to make the solution of P easier: If  is idempotent, then
we can replace P with

f(P ))), and get the same solutions (by Theorem
6). If instead  is not idempotent, we can replace P with P 0 (by Theorem 8). In
any case, the point in passing from P to

is that the new
problem should be easier to solve than P , since the semiring values of its tuples
are more explicit, that is, closer to the values of these tuples in a completely
solved problem.
More precisely, consider a branch-and-bound algorithm to nd an optimal
solution of P . Then, once a solution is found, its value will be used to cut away
some branches, where the semiring value is worse than the value of the solution
already found. Now, if the values of the tuples are worse in the new problem
than in P , each branch will have a worse value and thus we might cut away
more branches. For example, consider the fuzzy semiring (that is, we want to
maximize the minimum of the values of the subtuples): if the solution already
found has value 0:6, then each partial solution of P with value smaller than
or equal to 0:6 can be discarded (together with all its corresponding subtree in
the search tree), but all partial solutions with value greater than 0:6 must be
considered; if instead we work in the new problem, the same partial solution with
value greater than 0:6 may now have a smaller value, possibly also smaller than
0:6, and thus can be disregarded. Therefore, the search tree of the new problem
is smaller than that of P .
Another point to notice is that, if using a greedy algorithm to nd the initial
solution (to use later as a lower bound), this initial phase in the new problem
will lead to a better estimate, since the values of the tuples are worse in the new
problem and thus close to the optimum. In the extreme case in which the change
from P to the new problem brings the semiring values of the tuples to coincide
with the value of their combination, it is possible to see that the initial solution
is already the optimal one.
Notice also that, if  is not idempotent, a tuple of P 0 has either the same
value as in P , or 0. Thus the initial estimate in P 0 is the same as that of P
(since the initial solution must be a solution), but the search tree of P 0 is again
smaller than that of P , since there may be partial solutions which in P have
value dierent from 0 and in P 0 have value 0, and thus the global inconsistency
may be recognized earlier.
The same reasoning used for Theorem 4 on (P ) can also be applied to
~
f((P )). In fact, since ~
f is safe, the solutions of ~
have the same values
as those of (P ). Thus also the optimal solution sets coincide. Therefore we have
that Opt( ~
contains all the optimal solutions of P if the abstraction is
order-preserving. This means that, in order to nd an optimal solution of P , we
can nd all optimal solutions of ~
use such a set to prune the
search for an optimal solution of P .
Theorem 9. Given an SCSP problem P over S, consider a function ~
f on P
which is safe, solution-correct and intensive, and let us assume the abstraction
is order-preserving. Then we have that Opt(P )  Opt( ~
Proof. Easy follows from Theorem 4 and from the safeness of ~
f . 2
Theorem 5 can be adapted to ~
thus allowing us to use an
optimal solution of ~
f((P )) to nd both a lower and an upper bound of an
optimal solution of P .
5 Some abstraction mappings
In this section we will list some semirings and several abstractions between them,
in order to provide the reader with a scenario of possible abstractions that he/she
can use, starting from one of the semirings considered here. Some of these semirings
and/or abstractions have been already described in the previous sections
of the paper, however here we will re-dene them to make this section self-
contained. Of course many other semirings could be dened, but here we focus
on the ones for which either it has been dened, or it is easy to imagine, a system
of constraint solving. The semirings we will consider are the following ones:
{ the classical one, which describes classical CSPs via the use of logical and
and logical or:
{ the fuzzy semiring, where the goal is to maximize the minimum of some
values over [0; 1]:
{ the extension of the fuzzy semiring over the naturals, where the goal is to
maximize the minimum of some values of the naturals:
{ the extension of the fuzzy semiring over the positive reals:
{ the optimization semiring over the naturals, where we want to maximize the
sum of costs (which are negative integers):
{ the optimization semiring over the negative reals:
{ the probabilistic semiring, where we want to maximize a certain probability
which is obtained by multiplying several individual probabilities. The idea
here is that each tuple in each constraint has associated the probability of
being allowed in the real problems we are modeling, and dierent tuples in
dierent constraints have independent probabilities (so that their combined
probability is just the multiplication of their individual probabilities) [10].
The semiring is:
{ the subset semiring, where the elements are all the subsets of a certain set,
the operations are set intersection and set union, the smallest element is the
empty set, and the largest element is the whole given set:
We will now dene several abstractions between pairs of these semirings. The
result is drawn in Figure 9, where the dashed lines denote the abstractions that
have not been dened but can be obtained by abstraction composition. In reality,
each line in the gure represents a whole family of abstractions, since each h;
pair makes a specic choice which identies a member of the family. Moreover,
by dening one of this families of abstractions we do not want to say that there
do not exist other abstractions between the two semirings.
It is easy to see that some abstractions focus on the domain, by passing to
a given domain to a smaller one, others change the semiring operations, and
others change
1. from fuzzy to classical CSPs: this abstraction changes both the domain and
the operations. The abstraction function is dened by choosing a threshold
within the interval [0; 1], say x, and mapping all elements in [0; x] to F and
all elements in (x; 1] to T. Consequently, the concretization function maps T
to 1 and F to x. See Figure 2 as an example of such an abstraction. We recall
that all the abstractions in this family are order-preserving, so Theorem 4
can be used.
2. from fuzzy over the positive reals to fuzzy CSPs: this abstraction changes
only the domain, by mapping the whole set of positive reals into the [0; 1]
interval. This means that the abstraction function has to set a threshold, say
x, and map all reals above x into 1, and any other real, say r, into r
x . Then,
the concretization function will map 1 into +1, and each element of [0; 1),
say y, into y  x. It is easy to prove that all the members of this family of
abstractions are order-preserving.
3. from probabilistic to fuzzy CSPs: this abstraction changes only the multiplicative
operation of the semiring, that is, the way constraints are combined.
In fact, instead of multiplying a set of semiring elements, in the abstracted
version we choose the minimum value among them. Since the domain remains
the same, both the abstraction and the concretization functions are
the identity (otherwise they would not have the properties required by a Galois
insertion, like monotonicity). Thus this family of abstractions contains
just one member.
It is easy to see that this abstraction is not order-preserving. In fact, consider
for example the elements 0:6 and 0:5, obtained in the abstract domain by
These same combinations in
the concrete domain would be 0:7
resulting in two elements which are in the opposite order with respect to 0:5
and 0:6.
4. from optimization-N to fuzzy-N CSPs: here the domain remains the same
(the negative integers) and only the multiplicative operation is modied.
Instead of summing the values, we want to take their minimum. As noted in
a previous example, these abstractions are not order-preserving.
5. from optimization-R to fuzzy-R CSPs: similar to the previous one but on
the negative reals.
6. from optimization-R to optimization-N CSPs: here we have to map the negative
reals into the negative integers. The operations remain the same. A
possible example of abstraction is the one where
It is not order-preserving.
7. from fuzzy-R to fuzzy-N CSPs: again, we have to map the positive reals into
the naturals, while maintaining the same operations. The abstraction could
be the same as before, but in this case it is order-preserving (because of the
use of min instead of sum).
8. from fuzzy-N to classical CSPs: this is similar to the abstraction from fuzzy
CSPs to classical ones. The abstraction function has to set a threshold, say x,
and map each natural in [0; x] into F , and each natural above x into T . The
concretization function maps T into +1 and F into x. All such abstractions
are order-preserving.
9. from subset CSPs to any of the other semirings: if we want to abstract to
a semiring with domain A, we start from the semiring with domain P(A).
The abstraction mapping takes a set of elements of A and has to choose
one of them by using a given function, for example min or max. The concretization
function will then map an element of A into the union of all the
corresponding sets in P(A). For reason similar to those used in Example 3,
some abstractions of this family may be not order-preserving.
S_prob S_fuzzy S_CSP
Fig. 9. Several semiring and abstractions between them.
6 Related work
We will compare here our work to other abstraction proposals, more or less
related to the concepts of constraints.
Abstracting valued CSPs. The only other abstraction scheme for soft constraint
problems we are aware of is the one in [7], where valued CSPs [21] are abstracted
in order to produce good lower bounds for the optimal solutions. The concept of
valued CSPs is similar to our notion of SCSPs. In fact, in valued CSPs, the goal
is to minimize the value associated to a complete assignment. In valued CSPs,
each constraint has one associated element, not one for each tuple of domain
values of its variables. However, our notion of soft CSPs and that in valued
CSPs are just dierent formalizations of the same idea, since one can pass from
one formalization to the other one without changing the solutions, provided that
the partial order is total [2]. However, our abstraction scheme is dierent from
the one in [7]. In fact, we are not only interested in nding good lower bounds
for the optimum, but also in nding the exact optimal solutions in a shorter
time. Moreover, we don't dene ad hoc abstraction functions but we follow the
classical abstraction scheme devised in [5], with Galois insertions to relate the
concrete and the abstract domain, and locally correct functions on the abstract
side. We think that this is important in that it allows to inherit many properties
which have already been proven for the classical case. It is also worth noticing
that our notion of an order-preserving abstraction is related to their concept of
aggregation compatibility, although generalized to deal with partial orders.
Abstracting classical CSPs. Other work related to abstracting constraint problems
proposed the abstraction of the domains [11, 12, 22], or of the graph topology
(for example to model a subgraph as a single variable or constraint) [9]. We
did not focus on these kinds of abstractions for SCSPs in this paper, but we believe
that they could be embedded into our abstraction framework: we just need
to dene the abstraction function in such a way that not only we can change the
semiring but also any other feature of the concrete problem. The only dierence
will be that we cannot dene the concrete and abstract lattices of problems by
simply extending the lattices of the two semirings.
A general theory of abstraction. A general theory of abstraction has been proposed
in [16]. The purpose of this work is to dene a notion of abstraction that
can be applied to many domains: from planning to problem solving, from theorem
proving to decision procedures. Then, several properties of this notion are
considered and studied. The abstraction notion proposed consists of just two
formal systems  1 and  2 with languages L 1 and L 2 and an eective total function
Much emphasis is posed in
[16] onto the study of the properties that are preserved by passing from the concrete
to the abstract system. In particular, one property that appears to be very
desirable, and present in most abstraction frameworks, is that what is a theorem
in the concrete domain, remains a theorem in the abstract domain (called the
TI property, for Theorem Increasing).
It is easy to see that our denition of abstraction is an instance of this general
notion. Then, to see whether our concept of abstraction has this property, we
rst must say what is a theorem in our context. A natural and simple notion
of a theorem could be an SCSP which has at least one solution with a semiring
value dierent from the 0 of the semiring. However, we can be more general that
this, and say that a theorem for us is an SCSP which has a solution with value
greater than or equal to k, where k  0. Then we can prove our version of the
TI property:
Theorem 10 (our TI property). Given an SCSP P which has a solution
with value v  k, then the SCSP (P ) has a solution with value v 0  (k).
Proof. Take any tuple t in P with value v > k. Assume that
abstracting, we have solution correctness of  0 , we have
that v S
(v 0 ). By monotonicity of , we have that (v) S 0 (
(v
again by monotonicity of , we have thus by transitivity
Notice that, if we consider the boolean semiring (where a solution has either
value true or false), this statement reduces to saying that if we have a solution
in the concrete problem, then we also have a solution in the abstract problem,
which is exactly what the TI property says in [16]. Thus our notion of abstraction,
as dened in the previous sections, on one side can be cast within the general
theory proposed in [16], while on the other side it generalizes it to concrete and
abstract domains which are more complex than just the boolean semiring. This
is predictable, because, while in [16] formulas can be either true (thus theorems)
or false, here they may have any level of satisfaction which can be described by
the given semiring.
Notice also that, in our denition of abstraction of an SCSP, we have chosen
to have a Galois insertion between the two lattices (which corresponds to
the concrete semiring S) and h ~
(which corresponds to the abstract semiring
~
S). This means that the ordering in the two lattices coincide with those of the
semirings. We could have chosen dierently: for example, that the ordeing of
the lattices in the abstraction be the opposite of those of those in the semirings.
In that case, we would not have had property TI. However, we would have the
dual property (called TD in [16]), which states that abstract theorems remain
theorems in the concrete domain. It has been shown that such a property can
be useful in some application domains, such as databases.
7 Conclusions and future work
We have proposed an abstraction scheme for abstracting soft constraint prob-
lems, with the goal of nding an optimal solution, or a good approximation of it,
in shorter time. The main idea is to work on the abstract version of the problem
and then bring back some useful information to the concrete problem, to make
it easier to solve.
This paper is just a rst step towards the use of abstraction for helping to
nd the solution of a soft constraint problem in a shorter time. More properties
can probably be investigated and proved, and also an experimental phase is
necessary to check the real practical value of our proposal. We plan to perform
such a phase within the clp(fd,S) system developed at INRIA [14], which
can already solve soft constraints in the classical way (branch-and-bound plus
propagation via partial arc-consistency).
Another line for future research concerns the generalization of our approach
to include also domain and topological abstractions, as already considered for
classical CSPs.

Acknowledgments

This work has been partially supported by Italian MURST project TOSCA.



--R



Constraint Solving over Semirings.

Abstract interpretation: A uni
Systematic design of program analyis.

The calculus of fuzzy restrictions as a basis for exible constraint satisfaction.
Synthesis of abstraction hierarchies for constraint satisfaction by clustering approximately equivalent objects.
Uncertainty in constraint satisfaction problems: a probabilistic approach.
Eliminating interchangeable values in constraint satisfaction sub- problems
Interchangeability supports abstraction and reformulation for constraint satisfaction.
Partial constraint satisfaction.
Compiling semiring-based constraints with clp(fd

A theory of abstraction.
Consistency in networks of relations.
Constraint satisfaction.
Fuzzy constraint satisfaction.
Possibilistic constraint satisfaction problems
Valued Constraint Satisfaction Problems: Hard and Easy Problems.
An evaluation of domain reduction: Abstraction for unstructured csps.
Practical applications of constraint programming.
--TR
Partial constraint satisfaction
Possibilistic constraint satisfaction problems or MYAMPERSANDldquo;how to handle soft constraints?MYAMPERSANDrdquo;
A theory of abstraction
Semiring-based constraint satisfaction and optimization
Theories of abstraction
Abstract interpretation
Systematic design of program analysis frameworks
A CSP Abstraction Framework
An Abstraction Framework for Soft Constraints and Its Relationship with Constraint Propagation
Uncertainty in Constraint Satisfaction Problems
Abstracting Soft Constraints
Compiling Semiring-Based Constraints with clp (FD, S)
AbsCon
Semiring-Based CSPs and Valued CSPs

--CTR
Thomas Ellman , Fausto Giunchiglia, Introduction to the special volume on reformulation, Artificial Intelligence, v.162 n.1-2, p.3-5, February 2005
Didier Dubois , Henri Prade, Editorial: fuzzy set and possibility theory-based methods in artificial intelligence, Artificial Intelligence, v.148 n.1-2, p.1-9, August
Salem Benferhat , Didier Dubois , Souhila Kaci , Henri Prade, Bipolar possibility theory in preference modeling: Representation, fusion and optimal solutions, Information Fusion, v.7 n.1, p.135-150, March, 2006
Stefano Bistarelli , Francesco Bonchi, Soft constraint based pattern mining, Data & Knowledge Engineering, v.62 n.1, p.118-137, July, 2007
Giampaolo Bella , Stefano Bistarelli, Soft constraint programming to analysing security protocols, Theory and Practice of Logic Programming, v.4 n.5-6, p.545-572, September 2004
fuzzy reasoning;abstraction;constraint propagation;constraint solving;soft constraints