
## 4 Approximating Cp-Nets With Soft Constraints

In addition to testing consistency and determining preferentially optimal outcomes, we can be interested in the *preferential comparison* of two outcomes. Unfortunately, determining dominance between a pair of outcomes with respect to a set of qualitative preferential statements under the *ceteris paribus* assumption is PSPACE-complete in general [Lang, 2002], and is NP-hard even for acyclic CPnets [Domshlak and Brafman, 2002]. However, given a set Ω of preference statements, instead of using a preference relation ≻ induced by Ω, one can use an approximation ≫ of
≻, achieving tractability while sacrificing precision to some degree. Clearly, different approximations ≫ of ≻ are not equally good, as they can be characterized by the precision with respect to ≻, time complexity of generating ≫, and time complexity of comparing outcomes with respect to ≫. In addition, it is vital that ≫ faithfully extends ≻ (i.e. α ≻ β should entail α ≫ β). We call this *information preserving*. Another desirable property of approximations is that of preserving the *ceteris paribus* property (we call this the *cpcondition* for short).

For acyclic CP-nets, two approximations that are information preserving have been introduced, both comparing outcomes in time linear in the number of features. The first is based on the relative position of the features in the CPnet graph [Boutilier *et al.*, 2002]. This approximation does not require any preprocessing of the CP-net. However, it is problematic when there are hard constraints. The second, based on UCP-nets [Boutilier *et al.*, 2001], can be used as a quantitative approximation of acyclic CP-nets. UCPnets resemble weighted CSPs, and thus they can be used in constraint optimization using the soft constraints machinery. However, generating UCP-nets is exponential in the size of CP-net node's Markov family2, and thus in the CP-net node out-degree. An additional related work is described in [McGeachie and Doyle, 2002], where a numerical value function is constructed using graph-theoretic techniques by examining the graph of the preference relation induced by a set of preference statements. Note that this framework is also computationally hard, except for some special cases.

Here we study approximating CP-nets via soft constraints
(SCSPs). This allows us to use the rich machinery underlying SCSPs to answer comparison queries in linear time.

Moreover, this provides us a uniform framework to combine user preferences with both hard and soft constraints. Given an acyclic CP-net, we construct a corresponding SCSP in two steps. First, we build a constraint graph, which we call SC-net. Second, we compute the preferences and weights for the constraints in the SC-net, and this computation depends on the actual semi-ring framework being used. Here we present and discuss two alternative semi-ring frameworks, based on *min+* and SLO (Soft constraint Lexicographic Ordering) semi-rings, respectively. In both cases, our computation of preferences and weights ensures information preserving and satisfies the cp-condition. We illustrate the con2*Markov family* of a node X contains X, its parents and children, and the parents of its children.

![0_image_0.png](0_image_0.png)

_

b−>p2
struction of the SCSP using the example in Figure 2, which continues our running example from Figure 1.

Given a CP-net N, the corresponding SC-net Nc has two types of nodes: First, each feature X ∈ N is represented in Nc by a node VX that stands for a SCSP variable with D(VX ) = D(X). Second, for each feature X ∈ N, such that |P a(X)| ≥ 2, we have a node VP a(X) ∈ Nc, with D(VP a(X)) = ΠY ∈P a(X)D(Y ). Edges in Nc correspond to hard and soft constraints, where the latter are annotated with weights. Each node VX corresponding to an "independent feature" X ∈ N has an incoming (source-less) soft constraint edge (e.g., see VA and VB). For each node VX corresponding to a "single-parent" feature X ∈ N with P a(X) = {Y }, we have a soft constraint edge between X and Y (e.g., see VD).

Finally, for each node VX such that |P a(X)| ≥ 2, we have (i)
hard constraint edges between VP a(X) and each Y ∈ P a(X)
to ensure consistency (e.g., the edges between VA,B and both VA and VB), and (ii) a soft constraint edge between VP a(X)
and VX (e.g., the edge between VA,B and VC ).

To assign preferences to variable assignments in each soft constraint, each soft constraint c (between VP a(X) and VX)
is associated with two items: wc, a real number which can be interpreted as a weight (will be defined in the next section),
and Pc = {p1**, ..., p**|D(VX)|}, a set of reals which can be interepreted as "quantitative levels of preference". We will see in the next section how to generate the preference for each assignment to the variables of c, depending on the chosen semiring. In any case, each preference will be obtained by combining (via multiplication over naturals) the weight of the constraint wc and one of the elements of Pc.

## 4.1 Weighted Soft Constraints

The weighted SCSP is based on the *min+* semi-ring SW CSP = hR+**, min,** +, +∞, 0i. We assign preferences using real positive numbers (or penalties) and prefer assignments with smaller total penalty (i.e. the sum of all local penalties). In a soft constraint c on VP a(X) and VX , there are |D(VX )| penalties. Without loss of generality, we assume they range between 0 and |D(VX )| − 1, that is, p1 =
0, ..., pD(VX)| = |D(VX )| − 1. In our example, since all variables are binary, there are only two penalties i.e., p1 = 0 and p2 = 1, in all the constraints.

To ensure the cp-condition, similar to [Boutilier *et al.*, 2001], we need to ensure that each variable dominates its children. We therefore set the mini-