
Table 1: Problem categories that have been included in the experiments and the corresponding

number of tested instances

CSP category **number of instances**

Real world 80

Patterned 36

Academic 48

Quasi random 28

Pure random 36

Boolean 92

one value during constraint propagation and if a DWO is detected, it increases the weight of all these variables by one.

## 4. Experiments And Results

We now report results from the experimental evaluation of the selected DVOs described above on several classes of problems. All benchmarks are taken from C. Lecoutre's web page (http://www.cril.univ-artois.fr/∼lecoutre/research
/benchmarks/), where the reader can find additional details on how the benchmarks are constructed. In our experiments we included both satisfiable and unsatisfiable instances. Each selected instance involves constraints defined either in intension or in extension. Our solver can accept any kind of intentional constraints that are supported by the XCSP 2.1 format [32] (The XML format that were used to represent constraint networks in the last international competition of CSP solvers).

We have tried to include a wide range of of CSP instances from different backgrounds. Hence, we have experimented with instances from real world applications, instances following a regular pattern and involving a random generation, academic instances which do not involve any random generation, random instances containing a small structure, pure random instances and, finally, instances which involve only Boolean variables. The selected instances include both binary and non-binary constraints. In Table 1 we give the total number of tested instances on each problem category. In this section we only present results from a subset of the tried instances. In some cases different instances within the same problem class displayed very similar behavior with respect to their difficulty (measured in cpu times and node visits). In such cases we only include results from one of these instances. Also, we do not present results from some very easy and some extremely hard instances.

The CSP solver1 used in our experiments is a generic solver (in the sense that it can handle constraints of any arity) and has been implemented in the Java programming language. This solver essentially implements the M(G)AC search algorithm, where (G)AC-3 is used for applying (G)AC. Although numerous other generic (G)AC algorithms exist in the literature, especially for binary constraints, (G)AC-3 is quite competitive despite being one of the simplest.