
## 4.3 Illustrations

Let the domain of all the variables we introduce be {1, 2, 3, 4}.

- An XML encoding of the QCSP:
∃W, X ∀Y ∃Z W + X = Y + *Z, Y* 6= Z
is given in Figure 9.

- An XML encoding of the QCSP+:
∃*W, X*[W+X < 8, W−X > 2] ∀Y [W 6= Y, X 6= Y ] ∃Z[Z < W−Y ] W+X = Y +Z
is given in Figure 10.

## 5 Representing Wcsp Instances

The classical CSP framework can be extended by associating weights (or costs)
with tuples [4]. The WCSP (Weighted CSP) is a specific extension that rely on a specific valuation structure S(k) defined as follows.

Definition 1 *S(k) is a triple* ([0, . . . , k], ⊕, ≥) *where:* k ∈ [1, . . . , ∞] *is either a strictly positive natural or infinity,*
[0, 1, . . . , k] *is the set of naturals less than or equal to* k, ⊕ is the sum over the valuation structure defined as: a ⊕ b = min{k, a + b},
≥ *is the standard order among naturals.*
A WCSP instance is defined by a valuation structure S(k), a set of variables
(as for classical CSP instances) and a set of constraints. A domain is associated with each variable and a cost function with each constraint. More precisely, for each constraint C and each tuple t that can be built from the domains associated with the variables involved in C, a value in [0, 1*, . . . , k*] is assigned to t. When a constraint C assigns the cost k to a tuple t, it means that C forbids t. Otherwise, t is permitted by C with the corresponding cost. The cost of an instantiation of variables is the sum (using operator ⊕) over all constraints involving variables instantiated. An instantiation is consistent if its cost is strictly less than k. The goal of the WCSP problem is to find a full consistent assignment of variables with minimum cost.

It is rather easy to represent WCSP in XML in format XCSP 2.1. This is described below.

## 5.1 Presentation

Here are the extensions to the XML element called <presentation> in order to deal with a WCSP instance:
- the attribute format must be given the value "XCSP 2.1". - the attribute type is required and its value must be "WCSP".