1:0 1|0 3|10:1 2|1 3|2 0|2 1|1:3 1 This example may also be written equivalently on several lines:
1: 0 1|0 3| 10: 1 2|1 3|2 0|2 1| 1: 3 1 Note that using the abridged representation to associate costs with tuples allows us to save a large amount of space.

## 3 Representing Csp Instances

In order to avoid any ambiguity, we briefly introduce constraint networks. A
constraint network consists of a finite set of variables such that each variable X
has an associated domain dom(X) denoting the set of values allowed for X, and a finite set of constraints such that each constraint C has an associated relation rel(C) denoting the set of tuples allowed for the variables scp(C) involved in C. A solution to a constraint network is the assignment of a value to each variable such that all the constraints are satisfied. A constraint network is said to be satisfiable if it admits at least a solution. The Constraint Satisfaction Problem
(CSP), whose task is to determine whether or not a given constraint network is satisfiable, is NP-hard. A constraint network is also called a CSP instance. For an introduction to constraint programming, see for example [7, 1].

Each CSP instance is represented following the format given in Figure 1 where q, n, r, p and e respectively denote the number of distinct domains, the number of variables, the number of distinct relations, the number of distinct predicates and the number of constraints. Note that q ≤ n as the same domain definition can be used for different variables, r ≤ e and p ≤ e as the same relation or predicate definition can be used for different constraints. Thus, each instance is defined by an XML element which is called <instance> and which contains four, five or six elements. Indeed, it is possible to have one instance defined without any reference to a relation or/and to a predicate. Then, the elements <relations> and <predicates> may be missing (if both are missing, it means that only global constraints are referenced).

Each basic element (<presentation>, <domain>, <variable>, <relation>,
<predicate> and <constraint>) of the representation admits an attribute called name. The value of the attribute name must be a valid identifier (as introduced in the previous section). In the representation of any instance, it is not possible to find several attributes "name" using the same identifier.

Remark 1 *In the body of any element of the document, one can insert an*
<extension> *element in order to put any information specific to a solver.*

## 3.1 Presentation

The XML element called <presentation> admits a set of attributes and may contain a description (a string) of the instance: