## 2.2. PARALLEL COMPUTING

<figure><img src="image_37.png" /><figcaption>Figure 2.14: Illustrating Amdahl’s Law (total work).</figcaption></figure>

We get:

$$S(p) = \alpha^* + p(1 - \alpha^*) = p - \alpha^*(p - 1) \quad (2.9)$$

Thus, if $\alpha$ is small enough (i.e. the parallelizable part is big enough), the speedup is approximately $p$. This type of scaling is known as *weak scaling*. Figure 2.15 illustrates the total work evolution with respect to Gustafson’s law. The assumption is “the computation time is constant”.

<figure><img src="image_38.png" /><figcaption>Figure 2.15: Illustrating Gustafson’s Law (total work).</figcaption></figure>

It is true that speedup might be one of the most important measures to evaluate a parallel solution. However, there are also other metrics that provide additional information about the quality of a parallel algorithm, such as the *efficiency*.
## 2.2. PARALLEL COMPUTING

### Efficiency

Efficiency metric of an algorithm using $p$ processors estimates how well the processors are being used in solving a problem, compared to how much effort is wasted in communication and synchronization. It is expressed as follows:

$$E_p = \frac{S_p}{p} \qquad (2.10)$$

In fact, mostly, $E_p \le 1$ except for a super-linear speedup which is difficult to obtain in practice (except for some cases like satisfiable instances in CP). It is equal to 1 when we can achieve a perfect linear. Efficiency metric is as important as speedup since it tells how well the algorithm exploits machine power.

### 2.2.3 Parallel programming models

Several parallel programming models are used to express a parallel algorithm with an abstraction of a computer system. They basically describe the way the different processors interacts or not with each other.

#### Communication model

**Shared memory** In a shared memory model, several threads (or processes) share a common memory, i.e threads can read and write asynchronously within this memory. Parallel algorithms using this model need to manage concurrent access to the memory when reading/writing data. Synchronization features are used to control concurrent threads, such as monitors [Hoare, 1974], semaphores [Dunstan, 1991], atomic operations [Herlihy and Wing, 1987] and mutexes to control inputs/ outputs of a common memory.

Symmetric Shared Memory multiprocessor (SMP), depicted in Figure 2.16, is a parallel hardware and software architecture which owns identical processors, so as to increase the computing power, while maintaining a single shared memory.

Non-uniform memory access (NUMA), depicted in Figure 2.17, is a computer memory model. While SMP is a “share everything” system, NUMA adds an intermediate level of memory. In fact, under NUMA, each processor has its own local memory to which it can access faster than non-local ones.

**Message passing** This model is basically used in distributed systems in which components are located on networked computers. These components communicate and coordinate their actions by asynchronously or synchronously passing (sending or/and receiving) messages. Different data structures are used depending on the way messages are sent. Several algorithms use queue data structure to manage the different messages. Dijkstra introduced many new ideas for distributed systems based on exclusion mechanisms [Dijkstra, 2001]. Figure 2.18
## 2.2. PARALLEL COMPUTING

<figure><img src="image_39.png" /><figcaption>Figure 2.16: Symmetric Shared Memory multiprocessor architecture.</figcaption></figure>

<figure><img src="image_40.png" /><figcaption>Figure 2.17: Non-uniform memory access model.</figcaption></figure>

describes the message passing model where queues are used for each component to manage messages.

The main disadvantage of this model is the expensive cost of communication between the different components and especially managing messages.

### Parallel strategies

**Divide and conquer** Figure 2.19 describes Divide and conquer model which is a two-phase skeleton:

* *divide phase* consists in splitting the work up into sub-problems or tasks until sub tasks may be directly solved;
## 2.2. PARALLEL COMPUTING

<figure><img src="image_41.png" /><figcaption>Figure 2.18: Message passing model.</figcaption></figure>

* conquer phase where the result is recursively rebuild from partial results; we merge the results from that work serially again.

<figure><img src="image_42.png" /><figcaption>Figure 2.19: Divide and conquer model.</figcaption></figure>

**MapReduce** MapReduce [Dean and Ghemawat, 2008] is a well-known parallel programming tool. In fact, MapReduce model is composed of *Map()* and *Reduce()* procedures. *Map()* performs filtering and sorting operations on data whereas *Reduce()* procedure performs a summary operation of the treated data. Figure 2.20 describes MapReduce model for word counting problem. In fact, words are divided to be treated in parallel. In a first step, the different words are tagged: each world belongs to a category, such as “Friend” or “Sun”. Then, the same words are gathered together and counted: the words of each category
## 2.2. PARALLEL COMPUTING

are brought together. Finally, all results are regrouped as depicted in the final result of Figure 2.20. MapReduce model is different from divide and conquer systems in tagging the intermediate results. In MapReduce, we divide the work up serially, execute tasks in parallel, and then, tag the results to indicate which results go with which other results. The merging is then serial for all the results with the same tag, but can be executed in parallel for results that have different tags.

<figure><img src="image_43.png" /><figcaption>Figure 2.20: MapReduce model.</figcaption></figure>
### 2.2.4 CSP solving using parallel programming models

We introduced previously different models of parallel programming used in several fields. In constraint programming, several search/inference algorithms were proposed in order to speed up the search process sequentially. With the development of parallel programming techniques, the CSP community tried to benefit from such parallel architecture when solving constraint problems. In this section, we introduce:

* Distributed Arc Consistency

* Work Sharing

* Work Stealing

* Multi-Agent Search

* Portfolios

An interesting survey of parallel approaches in the literature for constraint solving is proposed in [Gent et al., 2011].

#### Distributed Arc Consistency

In order to speed up the solving CSP process, several works were proposed in order to distribute computing to a set of parallel processes. Another justification is that the problem itself may be distributed geographically or due to organizational structures.

Consistencies correspond to a certain level of coherence maintained during search as introduced in Section 1.2. Enforcing consistency when the problem is distributed is different from the classical sequential way to enforce consistencies.

Using a shared memory model was a first natural way to enforce AC in a parallel way, but the proposed algorithms using such model were personalized with communication/synchronization costs. In a distributed context, problems cannot be solved by a centralized solver. We call such problems: Distributed Constraint Satisfaction Problems (DisCSP). We distinguish: Sensor networks [Domshlak et al., 2005], distributed resource allocation problems [Prosser et al., 1992] and distributed meeting scheduling [Maheswaran et al., 2004]. Several distributed arc consistency algorithms were proposed in the 1960s using asynchronous message passing (Section 2.2.3).

Asynchronous Backtracking algorithm (ABT) [Yokoo et al., 1992, Yokoo et al., 1998] is the first algorithm that maintains arc consistency in DisCSP. Consistency is maintained based on nogood exchange between agents. Each agent stores a set of received nogoods as justification of inconsistent values. When an agent cannot make any assignment with respect to its current
## 2.2. PARALLEL COMPUTING

domains, either due to the original constraints or due to the received nogoods, new nogoods are generated by resolution of its set of nogoods and each one is sent to the closest agent involved, causing backtracking.

In [Nguyen and Deville, 1998], Distributed Arc Consistency (DisAC4) algorithm is based on AC4 (time-optimal sequential algorithm [Mohr and Henderson, 1986]). DisAC4 is a coarse-gained parallel algorithm designed for distributed memory models. In fact, AC4 is maintained in each node where a list of domains deletion is stored. After reaching a fixed point, a node broadcasts its list of domains deletion and waits for messages from other nodes. When the whole system reaches a fixed point, each node should proceed to domain deletion. This algorithm has $O(n^2d^2/p)$ time complexity. DisAC4 reaches, on some instances, a speedup close to linear with respect to the number of processors *p*. However, with the other instances DisAC4 reaches a 1,5 speedup over 8 processors. The strongest feature of DisAC4, as the authors claim, is its suitability to be implemented on very common hardware infrastructures.

DisAC9 [Hamadi, 1999] improves the asynchronous message passing process since it is a difficult issue due to dependencies between deletions. DisAC9 is optimal according to the number of message passing operations and it is considered the quickest processing algorithm of the Distributed Constraint Satisfaction Problems (DCSP) since it minimizes the number of messages transmitted between workers ($O(n^2d^3)$ complexity). In fact, a worker informs other workers about domain deletion *only if* it has the unique support for their values considering a constraint *c*. In the other case, it is useless to send a message and the worker stores it in the list of domains deletion that will be sent iff other significant (unique support) deletion occurs. The crucial point while distributing CSPs is the distribution of information among workers. In particular, partitioning variables in order to obtain a distributed problem is the main issue.

### Work Sharing

Parallel search made simple [Schulte, 2000] is one of the well-known approaches where the authors used work splitting technique in order to share work. They assume that for simple and reusable parallel constraint solving, we should separate: search, concurrency and distribution. Using concurrent language Oz [Henz et al., 1993] (Mozart implementation), they are referring to search nodes by the term computation spaces. The main feature of their approach is assuming that resources are cheap and mostly idle, which differs from the classical idea, in order to obtain a good speedup rather than a good resource use. In fact, workers use work sharing to dynamically distribute work on them. Each worker maintains a work pool which includes all nodes to be explored. The work is managed by a single manager through the usage of messages described in Figure 2.21. We distinguish three major steps: initialization, finding work and collecting a solution.
## 2.2. PARALLEL COMPUTING

In fact, in a first step a manager sends an *explore*-message to an idle worker corresponding to the root of the search tree. This worker becomes busy and starts to explore the search tree. The worker generates in turn new work which corresponds to the unexplored branches of the search tree. The available work is stored in its work pool. An idle worker contacts the manager in order to obtain work by sending a *find*-message. The manager in its turn sends a *share*-message to the first busy worker (a list of busy workers is maintained in the manager). In case where the contacted worker has a work in its pool to give, it sends to the manager which sends it back to the idle worker by an *explore*-message. Finally, when a worker finds a solution it sends it to the manager by a *collect*-message. This approach reaches an almost linear speedup.

<figure><img src="image_44.png" /><figcaption>Figure 2.21: Messages communicated between workers and manager.</figcaption></figure>
## 2.2. PARALLEL COMPUTING

More recently, the authors in [Régin et al., 2013] proposed another approach called “embarrassingly parallel search”, which statically decomposes the initial problem into many small sub-problems that are available to the workers and puts them in a queue. When a worker is idle, it takes dynamically a job from the job queue and solves it. The master maintains the concurrent access of the queue. The resolution is finished when all sub-problems are solved. In this approach there is no communication between workers so when a worker finds a better solution, the other workers cannot benefit from it to improve their current resolution. A good balancing is observed in practice. The decomposition algorithm is improved in [Régin et al., 2014].

### Work Stealing

*Work stealing*, first proposed in [Sleep, 1981], is the most popular architecture for parallel search where nodes steal work from each other if they are out of work. In fact, the problem is dynamically split during the solving process. This guarantees that workers are always busy and ensure a dynamic load balance. Figure 2.22 describes this architecture. In Figure 2.22(a) the work is not split in an equitable way: we suppose that *Worker*<sub>4</sub> has finished its work. *Worker*<sub>4</sub> remains without work that is why it steals work *w*<sub>1</sub> from *Worker*<sub>1</sub> in Figure 2.22(b). The disadvantage of this approach is the communication costs between workers in order to obtain work especially at the end of the problem solving when many workers have no sub-problems to solve. Moreover, when asking for work, a worker should not be given an easy work so it will not steal another work again almost instantly. This architecture is also used in [Chu et al., 2008, Schubert et al., 2008, Chu et al., 2009]

<figure><img src="image_45.png" /><figcaption>Figure 2.22: Work stealing architecture.</figcaption></figure>

In [Xie and Davenport, 2010], a masters/workers approach is proposed where
## 2.2. PARALLEL COMPUTING

the search space is divided between the different masters. Each master puts its attributed sub-trees in a work pool in order to dispatch them to the workers. In fact, an idle worker requests its master for work and does not steal work directly from a busy worker. If there is no unexplored nodes the worker remains idle until new jobs become available.

Another work stealing approach is presented in [Kotthoff and Moore, 2010]. The authors describe a model splitting approach which consists in modifying the constraint model of the problem. In fact, the problem model is converted into new models, when assigning variables for example. Added to that, several constraints used to partition the search space are appended to the models. This approach does not share any information between workers. The approach uses the work stealing technique, while outputting restart nogoods for the problem in order to prevent the worker from exploring the space just explored before (In Figure 2.23(a), the restart nogood is $x \neq 1$ and $x \neq 2$). A job server is also used to avoid implementing distribution. Clearly, parents give up all their search space and split themselves into $n$ parts. To the best of our knowledge, there is no experiments done. Figure 2.23 describes this architecture where the search space is split in two different conditions. In Figure 2.23(a), the search space is split before search where the 3 branches corresponding to the assignment of variable $x$ is partitioned between workers. We call this an *n-way* branching. The main problem of such splitting is that it is impossible to predict the size of the search space for each of the splits: some parts could lead to a failure and then one of the workers will be idle while the others do most of the work. The search-space splitting in Figure 2.23(b) is done in a different way. In fact, during search and after the two decisions, $x \neq 1$ and $x \neq 2$, the search space is split between worker. In [Kotthoff and Moore, 2010], authors add restart nogoods which are additional constraints to the search space of each worker.

In [Chu et al., 2009], different work stealing strategies are described which are based on a *confidence* measure. This latter is the estimated ratio of solution densities between the sub-trees at each node obtained with respect to the branching heuristic used at each node and it is updated during search. The authors present a quantitative analysis discussing the effect of the different work stealing strategies on the work amount performed. A function can be used to determine the relation between the strength of the branching heuristic and the density of solutions and, thus, ensure automatically an optimal work stealing. For example, sometimes it appears that stealing *left* and *low* could be much better, but sometimes stealing *high* can be better. The authors show that in practice stealing low increases the communication cost. This is the reason why they defined a bound above the average fail depth below which work cannot be stolen. These different strategies show an effectiveness ranging from speedups of 7 times to a super linear speedup on the benchmarks in the paper using 8 threads for the parallel search algorithm.
## 2.2. PARALLEL COMPUTING

<figure><img src="image_46.png" /><figcaption>(a) Search-space splitting before search (n-way branching).</figcaption></figure>

<figure><img src="image_47.png" /><figcaption>(b) Search-space splitting during search (2-way branching).</figcaption></figure>

Figure 2.23: Search-space splitting architecture.
### Multi-Agent Search

In multi-agent search architecture, we have one problem and different agents. In fact, each agent solves the problem independently and may communicate with the other agents. This approach could achieve super-linear speed up even-though the diversity among agents increases communication costs. This idea was, first, explored in [Rao and Kumar, 1988].

In [Bordeaux et al., 2009], the authors present some “Experiments with Mas- sively Parallel Constraint Solving” where they explore approaches avoiding com- munication between workers. In fact, the problem is split over workers with respect to hashing constraints. The hashing constraint of each core is unique. The authors present promising results on more than 64 cores.

### Portfolios

In this multi-core architecture, a portfolio of solvers use a variety of algo- rithms to have a globally better solver. This architecture could be consid- ered a multi-agent search. The idea of *portfolio-based search* was explored in [Gomes and Selman, 2001]. Portfolios have been extremely used by the SAT community and a variety of solvers were proposed. To the best of our knowl- edge, there are two CSP portfolio solvers CPHydra [O'Mahony et al., 2008] and Sunny-CP [Amadini et al., 2015]. CPHydra, a sequential portfolio, won the 2008 CSP solver competition <fnref n="2" />. It uses a case-based reasoning and solves a problem based on the *k* most similar instances (K-nearest neighbor) from a base. In fact, CPHydra computes a schedule of the portfolio constituent solvers to be run in sequence. This schedule of solvers allocates a duration to each solver. Three main solvers are used in CPHydra: AbsCon, Choco and Mistral.

Sunny-CP attended the MiniZinc Challenge (MZC) [Stuckey et al., 2010] with respectable results (4^th^ out of 18). Sunny-CP is a CSP/COP portfolio solver using MiniZinc Language. Using different solvers, features, data-sets and parameters tuning, Sunny-CP is able to outperform state-of-the-art constraint solvers. For an input problem, Sunny-CP selects the *k* closest instances using the *k*-Nearest Neighbors (k-NN) algorithm. Based on these instances, Sunny-CP selects the promising solvers to run.

In [Dasygenis and Stergiou, 2014], the authors proposed a way to build port- folios for parallel solving by varying the local consistency during search. In fact, authors use different heuristics for adaptive propagator selection proposed in [Stergiou, 2008] which switch dynamically between a weak and a strong propa- gator for each individual constraint during search. A constraint *c* is made *strong* or *weak* with respect to user predefined thresholds considering different propa- gation events such as Domain Wipe Out (DWO) and domain deletions. Two main thresholds are used in this portfolio: *l*<sub>dwo</sub> and *l*<sub>del</sub>. A constraint *c* is made

<footnote n="2">²http://cpai.ucc.ie/08/</footnote>
## 2.2. PARALLEL COMPUTING

strong if the number of revisions of *c* since the last time it caused a DWO (respectively at least one value deletion) is less or equal to *l*<sub>dwo</sub> (respectively *l*<sub>del</sub>). Experiments in this paper use *H*<sub>1</sub>(*l*<sub>dwo</sub>), *H*<sub>2</sub>(*l*<sub>del</sub>) or *H*<sub>4</sub> heuristics, introduced in [Stergiou, 2008], or a combination of them while varying thresholds for each solver. Each solver uses MAC. Experimental results demonstrated that this approach constantly outperforms the sequential solver and competes with the other portfolio approaches using randomized variable ordering heuristic.
# Part II

## Contributions
# Chapter 3

## Compressing Table Constraints

### Contents

<table><tr><td>3.1</td><td>Introduction</td><td>110</td></tr><tr><td>3.2</td><td>STR<sup>c</sup></td><td>110</td></tr><tr><td>3.2.1</td><td>Patterns Definition</td><td>110</td></tr><tr><td>3.2.2</td><td>Compression Method</td><td>112</td></tr><tr><td>3.2.3</td><td>Filtering algorithm</td><td>120</td></tr><tr><td>3.2.4</td><td>Experimental results</td><td>125</td></tr><tr><td>3.3</td><td>STR-slice</td><td>129</td></tr><tr><td>3.3.1</td><td>Pattern Definition</td><td>130</td></tr><tr><td>3.3.2</td><td>Compression Method</td><td>134</td></tr><tr><td>3.3.3</td><td>Filtering Sliced Table Constraints</td><td>138</td></tr><tr><td>3.3.4</td><td>Experimental results</td><td>146</td></tr><tr><td>3.4</td><td>Conclusions and discussion</td><td>149</td></tr></table>
### 3.1 Introduction

In Chapter 2, we introduced the context of compressing table constraints. Several approaches and data structures are presented. Moreover, for each of them, we introduced the corresponding filtering algorithm.

In this chapter, we propose two different compression techniques for table constraints. Each of them presents a different form of compressed table constraint aiming to reduce time and space complexity.

This chapter is organized as follows:

* In the first Section, we introduce a first work (STR^c) [Gharbi et al., 2013] that was presented at *JFPC 2013* and *CP 2013* (*Doctoral Program*);

* The second Section presents a second work (STR-slice) [Gharbi et al., 2014] presented at *CPAIOR 2014*;

* Finally, we conclude.

### 3.2 STR^c

The first approach, called compressed STR (STR^c), consists in combining STR with a compression algorithm based on “tries”, which is different from the ones described in [Katsirelos and Walsh, 2007] and [Xia and Yap, 2013] where a Cartesian Product representation is used for compression. The idea is to identify the recurrent patterns (sub-tuples) in the tuples of each constraint, and replace their occurrences by references to a patterns table. The filtering process is an adaptation of STR in order to take into consideration the patterns appearing at different positions.

This section is organized as follows. In Section 31, we describe the way patterns are defined. Then, we give details about the compression process in Section 3.2.2. Next, we present in Section 3.2.3 the filtering algorithm used for the “compressed” form of table constraints. Finally, we present some experimental results in Section 3.2.4.

#### 3.2.1 Patterns Definition

In our context, a pattern is defined as follows:

**Definition 31 (pattern)** A pattern $\mu$ is a sequence of consecutive values (a sub-tuple) in a tuple $\tau$ of a table constraint. We note $|\mu|$ the length of a pattern $\mu$, $nbOcc(\mu)$ the number of occurrences of the pattern in the tuples of a given constraint.
## 3.2. STR<sup>C</sup>

**Example 24** Let $\mu_1$ be a pattern such that $\mu_1=(a, a, b)$ and $\mu_1$ appears 4 times in a table constraint. We say that $|\mu_1| = 3$, nbOcc($\mu_1$) = 4.

Since the main idea of this approach is to reduce the spatial complexity of table constraints through using the most frequent patterns, we defined a pattern in a way that maximizes its frequency. It is important to note that the patterns extracted in our approach are independent from their position in the scope of the table constraint. According to that, a pattern does not correspond necessarily to the assignment of the same values to the same variables, but rather the same sequence of values. This choice was made to hopefully maximize the frequency of possible patterns, and, thus, to obtain a better compression. Therefore, the longer the patterns and the more frequent they are, the smaller the table constraint representation will be.

**Example 25** Figure 3.1 describes the detection of the pattern $(c, b, c)$. This pattern which appears in four tuples $(\tau_1, \tau_3, \tau_4$ and $\tau_6)$, does not involve the same variables. In tuple $\tau_1$ this pattern involves $x_1$, $x_2$ and $x_3$, whereas, in the case of tuple $\tau_4$ the pattern involves $x_3$, $x_4$ and $x_5$. It is evident that if we consider the same variables when looking for a pattern and that the variables must be consecutive, we will not have the same patterns neither the same number of occurrences as the patterns found applying Definition 31. This is shown by colors in Figure 3.1. The pattern $\{(x_1, c), (x_2, b), (x_3, c)\}$ appears just one time. The pattern $\{(x_2, c), (x_3, b), (x_4, c)\}$ appears two times.

<figure><img src="image_48.png" /><figcaption>Figure 3.1: Patterns detection according to positions in the table constraint $C_{x_1,x_2,x_3,x_4,x_5}$.</figcaption></figure>

**Example 26** Through Tables 3.2(a) and 3.2(b), we illustrate the effect of scope order on patterns detection. Let us consider, for example, the pattern $(c, b, c)$ in Table 3.2(a) which appears four times. If we change the scope order arbitrarily in Table 3.2(b) this pattern does not appear anymore. On the other hand, the pattern $(a, b, b)$ that appears two times in Table 3.2(a), happens to be more frequent in Table 3.2(b) (appearing three times).
## 3.2. STR<sup>c</sup>

<figure><img src="image_49.png" /><figcaption>Figure 3.2: Patterns detection according to the scope in the table constraint $C_{x_2,x_4,x_1,x_3,x_5}$.</figcaption></figure>

From Example 26, we conclude that the scope order of the constraint can affect advantageously or not patterns detection: the detected patterns change and also their number of occurrences. We note that in our first approach (STR<sup>c</sup>), we consider that the scope is ordered in a lexicographical order. Whereas, for the second approach (Section 3.3) we use another patterns definition that depends only on variables, and so, the scope order doesn't influence patterns detection.

### 3.2.2 Compression Method

**Collecting patterns** In this step, we identify the relevant patterns from the various tuples of a given table constraint. To do that, we use tries (Section 2.1.1) as data structures to store all these patterns. We first introduce the different algorithms for manipulating this data structure.

Algorithms 19, 20 and 21 describes the way that patterns are managed in the trie data structure. In Algorithm 19, when a new pattern candidate $\mu$ is extracted, we check first if it is already stored into *patternsTrie* or there exists a pattern $\mu' \subset \mu$ such that $\mu'$ is already in the trie (Lines 3 - 9). If $\mu$ does not exist in the trie or only a part of $\mu$ exists *nbOcc* counters of the new added nodes are initially fixed to 1 (Line 11). If $\mu$ shares its first value(s) with a path the trie, the *nbOcc* counters of the shared nodes are incremented (Line 7) and the remaining part is inserted at the right place. Algorithm 20 describes the way a pattern is extracted from the trie. In a ascending way (from a node to the root), we extract the pattern corresponding to the path going from the root to a fixed node. Algorithm 21 describes the way that the length of a path is calculated.

In order to collect all possible patterns, we read each tuple in the table constraint. For each possible pattern, we first verify if it already exists in the trie. If it is the case, the corresponding nodes counters are updated (incremented). If the pattern shares its first values with an existing path in the trie, only the
3.2. STR<sup>C</sup>

<caption>**Algorithm 19:** addPattern(root:Node,μ:Pattern)</caption>

1 node ← root
2 i ← 0
3 **while** i < μ.length **do**
4 &nbsp;&nbsp;&nbsp;&nbsp;node ← node探查(μ[i])
5 &nbsp;&nbsp;&nbsp;&nbsp;**if** node ≠ nil **then**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i ← i + 1
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node.nbOcc ← node.nbOcc + 1
8 &nbsp;&nbsp;&nbsp;&nbsp;**else**
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**break**
10 **while** i < μ.length **do**
11 &nbsp;&nbsp;&nbsp;&nbsp;Add( node, μ[i]) // nbOcc is initialized to 1
12 &nbsp;&nbsp;&nbsp;&nbsp;node ← node探查(μ[i])
13 &nbsp;&nbsp;&nbsp;&nbsp;i ← i + 1

<caption>**Algorithm 20:** getPattern(node:Node):pattern</caption>

1 pattern ← <>
2 **while** node ≠ root **do**
3 &nbsp;&nbsp;&nbsp;&nbsp;pattern ← label(node.getParent(), node) + pattern
4 &nbsp;&nbsp;&nbsp;&nbsp;node ← node.getParent()
5 **return** pattern

<caption>**Algorithm 21:** getLengthPath(node:Node):Integer</caption>

1 length ← 0
2 **while** node ≠ root **do**
3 &nbsp;&nbsp;&nbsp;&nbsp;length ← length + 1
4 &nbsp;&nbsp;&nbsp;&nbsp;node ← node.getParent()
5 **return** length

corresponding nodes counters are updated and the remaining part of the pattern
is added at its right place of the trie. If the pattern does not exist in the trie and
it does not share any first value with the trie prefixes, a new path corresponding
to this pattern is created from the root. A trie contains, thus, all the existing
sequences of values and their number of occurrences.

**Example 27** This example shows the different steps of the trie construction for the first tuple τ₁ of the table constraint in Figure 3.1. We detect all possible
## 3.2. STR<sup>C</sup>

patterns of scope at least equal to 3 and at most 4 (we explain this choice in the next paragraph). Starting from the first position, (c, b, c) is the first extracted pattern. Since the trie is empty, it is inserted in the trie creating a first path from the root (Figure 3.3(a)). The nodes' counters are initially equal to 1. (c, b, c, a) is also a pattern candidate of length 4 starting from position 1. (c, b, c, a) is not included in the trie but it is the continuity of the path (c, b, c). Thus, only the value a is added at the end of this path (Figure 3.3(b)). The nodes' counters are not updated in this case because there are not two different paths sharing their first values (edges). Starting from position 2, (b, c, a) a pattern of length 3 is inserted in Figure 3.3(c). (b, c, a, c) a pattern of length 4 is added in the same way as the pattern (c, b, c, a): the value c is put at the end of the path (3.3(d)). Starting from position 3 the only possible pattern candidate is (c, a, c) which shares its first value c with the path c → b → c → a. The node's counter corresponding to the value c is updated to 2. The path (a, c) is put as a child of the ending node of edge c.

<table><caption>Table 3.1: Table constraint $C_{x_1,x_2,x_3,x_4,x_5}$.</caption><thead><tr><th></th><th>x<sub>1</sub></th><th>x<sub>2</sub></th><th>x<sub>3</sub></th><th>x<sub>4</sub></th><th>x<sub>5</sub></th></tr></thead><tbody><tr><td>⇒ τ<sub>1</sub></td><td>(c, b, c, a, c)</td><td></td><td></td><td></td><td></td></tr><tr><td>τ<sub>2</sub></td><td>(a, a, b, b, a)</td><td></td><td></td><td></td><td></td></tr><tr><td>τ<sub>3</sub></td><td>(a, c, b, c, a)</td><td></td><td></td><td></td><td></td></tr><tr><td>τ<sub>4</sub></td><td>(b, a, c, b, c)</td><td></td><td></td><td></td><td></td></tr><tr><td>τ<sub>5</sub></td><td>(b, a, a, b, b)</td><td></td><td></td><td></td><td></td></tr><tr><td>τ<sub>6</sub></td><td>(a, c, b, c, b)</td><td></td><td></td><td></td><td></td></tr><tr><td>τ<sub>7</sub></td><td>(a, c, a, c, a)</td><td></td><td></td><td></td><td></td></tr></tbody></table>

First experiments show that choosing 1 or 2 as minimal length for patterns, is not effective to obtain a high ratio of compression. That is why the minimal length for patterns is fixed to 3 in our approach. The maximal possible length of a pattern, in our approach, is defined as the constraint arity minus 1.

Algorithm 22 describes the different steps used to build all possible patterns. Lines 3-6 of the algorithm iterate over all tuples of the table and collect all candidate patterns of different sizes starting from different positions of the tuple. The size of patterns is between the minimal length of patterns, which is fixed in our approach to 3, and the maximal length, which represents the constraint arity minus 1. All these patterns are stored in *patternsTrie*. The remaining steps (Line 8) of Algorithm 22 are introduced in the next paragraph.

**Detecting frequent patterns** In a second step, it is necessary to identify the most relevant patterns for the compression process. To do that, we introduce
3.2. STR<sup>C</sup>

<figure><img src="image_50.png" /><figcaption>Figure 3.3: The patterns trie built from $\tau_1$ of the constraint given in Table 3.1.

the notion of **score** of a pattern $\mu$ as follows:</figcaption></figure>

$$ score(\mu) = |\mu| \times nbOcc(\mu) \qquad (3.1) $$

In fact, the score of each pattern expresses the space occupied by all of its occurrences in the table constraint. The bigger the score is, the bigger the occupied space is and, thus, the smaller the table constraint will be if we replace each occurrence of the pattern by a reference towards it. Consequently, this definition of score allows us to choose the patterns that make the table smaller and then obtain a better compression. A selection threshold is fixed, and only the patterns having a score greater than this threshold are retained in the compression
3.2. STR<sup>C</sup>

<caption>**Algorithm 22:** buildPatterns(c: Constraint): Queue</caption>

1 $maxSize \leftarrow |scp(c)| - 1$
   // Collecting all possible patterns in patterns Trie
2 $patterns Trie \leftarrow \emptyset$
3 **foreach** $\tau_i \in table(c)$ **do**
4 &nbsp;&nbsp;&nbsp;&nbsp;**foreach** $position \in [0, |scp(c)| - minSize]$ **do**
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**foreach** $size \in [minSize, min(maxSize, |scp(c)| - position)]$ **do**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // Adding pattern in patterns Trie
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\mu \leftarrow \tau_i(position), \dots, \tau_i(position + size) \succ$
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; addPattern(root pattens Trie), $\mu$)

// Maintaining only the frequent patterns
7 **FP-Queue** \leftarrow \emptyset
8 **extractBestFrequentPatterns** (patterns Trie. root, **FP-Queue**)
9 **return** **FP-Queue**

algorithm and stored in the patterns table. In the experimental section, Figures 3.14 and 3.15 show the impact of the threshold score variation on the number of used patterns and the compression ratio.

For efficiency reasons, the total number of retained patterns is limited by a
second parameter called nbMaxPatterns in order to control the compression time
and the memory space used to store the different patterns. This parameter is
useful in the case of class of instances having an important number of frequent
patterns.

Both parameters *scoreThreshold* and *nbMaxPatterns* enable us to obtain the
most frequent patterns having a score greater than *scoreThreshold*. Both of them
are important in the compression process.

Algorithm 23 describes the frequent patterns detecting step. In fact, after
collecting all candidate patterns in *patternsTrie* we calculate for each pattern
its score. Considering the pattern’s score, we decide if we put it in the *FP-
Queue*, which is a priority queue where patterns are stored in a decreasing order
of their score. This score is calculated as mentioned before. In the case that *FP-
Queue* is already full (Line 8), meaning that the number of patterns is equal to
*nbMaxPatterns*, every time we calculate the score of a new pattern we compare it
to the worst pattern which is the pattern having the smallest score meaning that
it is the last element of the queue (Line 9). This comparison (Line 10) allows us
to decide whether we keep the worst pattern in *FP-Queue* (in case that the new
pattern’s score is less than the worst pattern) or replace it by the new pattern,
otherwise (Lines 11 - 13).
3.2. STR<sup>C</sup>

**Algorithm 23:** extractBestFrequentPatterns(*node*: Node, *FP-Queue*: Queue)
1 &nbsp;&nbsp;score ← 0
2 &nbsp;&nbsp;if level(*node*) ≥ minSize then
3 &nbsp;&nbsp;&nbsp;&nbsp;score ← getLengthPath(*node*) × node nbOcc
4 &nbsp;&nbsp;if score > scoreThreshold then
5 &nbsp;&nbsp;&nbsp;&nbsp;if size(*FP-Queue*) < nbMaxPatterns then
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// Extract pattern from patternsTrie: the path from
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;root to node
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pattern ← getPattern(*node*)
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;addPatternQ(*pattern*, *score*, *FP-Queue*)
8 &nbsp;&nbsp;else
9 &nbsp;&nbsp;&nbsp;&nbsp;worstPattern ← getWorstPattern(*FP-Queue*)
10 &nbsp;&nbsp;&nbsp;&nbsp;if score > score(worstPattern) then
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;delete(worstPattern)
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pattern ← getPattern(*node*)
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;addPatternQ(*pattern*, *score*, *FP-Queue*)
14 &nbsp;&nbsp;foreach *child* ∈ *node*.getChildren() do
15 &nbsp;&nbsp;&nbsp;&nbsp;extractBestFrequentPatterns(*child*, *FP-Queue*);

**Compressing table constraints** After detecting the most relevant patterns, iterating over the constraint table is necessary to detect the presence of such patterns and replacing them with indexes. An illustration of the compressed data structure is described in Figure 3.4. In fact, once a pattern is found, it is replaced by a reference towards a patterns table where the frequent patterns are stored. The reference is encoded by a negative integer **(-patternId)**. In fact, the tuple will no more contain the values composing the pattern, but rather a reference that points to the pattern stored in the patterns table.

<figure><img src="image_51.png" /><figcaption>Figure 3.4: Compressing tuples.</figcaption></figure>

Algorithm 24 describes the compression step. First, for each tuple in the table constraint we look for the best contained pattern in *FP-Queue*. When searching
3.2. STR<sup>C</sup>

**Algorithm 24:** compress-STR<sup>c</sup>(c: Constraint, FP-Queue: Queue)
1 &nbsp;&nbsp;foreach $\tau_i \in table(c)$ do
2 &nbsp;&nbsp;&nbsp;&nbsp;repeat
3 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// searching for the best frequent pattern contained in $\tau_i$
4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bestPattern $\leftarrow \prec$
5 &nbsp;&nbsp;&nbsp;&nbsp;foreach $\mu_i \in FP-Queue$ do
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if contains($\mu_i, \tau_i$) then
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bestPattern $\leftarrow \mu_i$
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bestPatterniltion $\leftarrow index(\mu_i, \tau_i)$
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break
10 &nbsp;&nbsp;&nbsp;&nbsp;if bestPattern $\neq$ nil then
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// Compressing each tuple $\tau_i$ of c: $\tau_i^c$ is the prospective compressed tuple which is encoded as an array of maximal length $|scp(c)|$. Its length is denoted $length^c$
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;position $\leftarrow 0$
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;length$^c$ $\leftarrow 0$
14 &nbsp;&nbsp;&nbsp;&nbsp;while position $< \tau_i$.length do
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if position = bestPattern. position then
16 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\tau_i^c$[length$^c$] $\leftarrow$ -bestPattern.id // a reference
17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;towards the pattern
18 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;position $\leftarrow$ position + bestPattern.length
19 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else
20 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\tau_i^c$[length$^c$] $\leftarrow$ $\tau_i$[position]
21 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;position $\leftarrow$ position + 1
22 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;length$^c$ $\leftarrow$ length$^c$ + 1
23 &nbsp;&nbsp;&nbsp;&nbsp;until bestPattern = nil
24 &nbsp;&nbsp;&nbsp;&nbsp;if length$^c$ $< \tau_i$.length then
25 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\tau_i$ $\leftarrow$ $\tau_i^c$

for the best pattern, we respect a decreasing order of patterns score. If a pattern
is found, we add it to the patterns table and then replace its occurrence in the
tuple by a reference towards it in the patterns table. This process continues
until there is no possible pattern that could be replaced in the tuple. We should
note that when searching for the best pattern contained in a tuple, we take into
consideration the replacement done before. As a consequence, patterns don't
overlap since we choose to replace always the occurrence of the best one. Once
we have iterated over all values of a tuple we check if we have already replaced at
## 3.2. STR<sup>C</sup>

least one pattern. If it is the case, the tuple $\tau_i$ of the constraint is removed and replaced by the compressed one $\tau_i^c$. It is important to note that our approach does not take into consideration the dynamic score variation. In other terms, the trie of frequent pattern is built statically before compression. However, if patterns share some values and we decide to use one of them in compression, the score of others will change during compression. Let us take the example of patterns "cacb" and "acb". If we suppose that $nbOcc(cacb) = 3$ and $nbOcc(acb) = 4$. If we decide to use the pattern cacb, $nbOcc(acb)$ should be updated to 1 and in this case it might be less frequent compared to the remaining patterns.

**Illustration** We give now an illustration of the whole process from patterns detection to table compression. Table 3.1 represents a positive table constraint of arity 5, involving variables $x_1, x_2, x_3, x_4$ and $x_5$. We can notice that several patterns are repeated among tuples such as cbc, aab and abb as patterns of length 3 and aabb, acbc and cbca as patterns of length 4. Through visiting all tuples of our constraint, we can build the trie illustrated in Figure 3.5, where the number of occurrences is given in each node. Every node identifies a path $\mu$ (going from the root to the leaf) associated with the $nbOcc(\mu)$ counter. In order to make clearer the frequent patterns detection step, in Figure 3.6, we present the same trie depicted in Figure 3.5 but by mentioning the *score* in each node rather than the *nbOcc* counter.

<figure><img src="image_52.png" /><figcaption>Figure 3.5: The trie of patterns built from the constraint given in Table 3.1: nbOcc are given in nodes.</figcaption></figure>

The compression algorithm allows us to have a compressed version of the table constraint; its logical representation is given in Figure 3.7 whereas the patterns table is given on the right of the table constraint. Tuples $\tau_1, \tau_3, \tau_4, \tau_6$ of the compressed table respectively reference the pattern $\mu_1$ at positions 1, 2, 3
## 3.2. STR<sup>C</sup>

<figure><img src="image_53.png" /><figcaption>Figure 3.6: The trie of patterns built from the constraint given in Table 3.1: score are given in nodes.</figcaption></figure>

and 2, and tuples $τ_2, τ_5$ respectively reference the pattern $μ_2$ at positions 1 and 2.

This mechanism of compression can entail an important reduction of the space occupied by the table. This is illustrated by the physical view given in Figure 3.8. The compressed tuples reference their corresponding patterns stored in the patterns table. The table constraint is, thus, composed of tuples of different sizes since they contain patterns of different sizes.

Figure 3.9 shows the space occupied by the two forms of table constraints: the classic and the compressed one. The space required to represent a table constraint is:

$Σ_i \text{ length}(τ_i) = \text{number of tuples} \times \text{length of a tuple} = t \times |scp(c)| = 7 \times 5 = 35$
The space required by the compressed form of the table constraint is:

$$Σ_i \text{ length}(τ_i) + Σ_i \text{ length}(μ_j) = (3+2+3+3+2+3+5) + (3+4) = 29$$

### 3.2.3 Filtering algorithm

During the filtering of a table constraint, it is necessary to check the validity of tuples, which implies to verify the validity of the patterns. When a pattern appears several times in the table at the same position, we wish to test the validity of the pattern only once, which allows us to speed up the filtering.

To do this, we use a counter `currentTime`, which is incremented every time we filter the table constraint, and an array of timestamps `stamps[μᵢ, j]`. For a pattern $μ_i$, which occurs at a position `j`, `stamps[μᵢ, j]` gives the result of the last test of validity ($μᵢ, j$) (field `valid`) as well as the value of the counter `time` when this test was made. Every time the validity of ($μᵢ, j$) must be tested, we
## 3.2. STR<sup>C</sup>

<figure><img src="image_54.png" /><figcaption>patterns Table</figcaption></figure>

(a) Detecting patterns and filling the patterns table.

<figure><img src="image_55.png" /><figcaption>patterns Table</figcaption></figure>

(b) Replacing patterns by their *id*.

<caption>Figure 3.7: Compressed table (logical view).</caption>

verify first if the value *time* of *stamps*[$\mu_i$, *j*] is equal to the current value of *currentTime*. If it is the case, the validity was already tested in the current step of filtering and, thus, the value *valid* of *stamps*[$\mu_i$, *j*] directly supplies the answer, which avoids useless calculations. Otherwise, it is necessary to test the validity of ($\mu_i$, *j*) and to store the result in *stamps*[$\mu_i$, *j*].

Figure 3.10 presents an example of the evolution of the structure *stamps*. First, all elements are initialized at *currentTime*=0 and the fields *valid* remain unassigned (see Figure 3.10(a)). During the first filtering of the table, the global counter *currentTime* is set to 1. To determine whether tuple $\tau_3$ (for example) is valid, it is necessary to ensure that $\mu_1$ at position *j* = 2 is valid. As the value *time* of *stamps*[$\mu_1$, 2] is not equal to the current value of *currentTime*, we know that this test was not already made in the current filtering step. Thus, we verify whether *c*, *b* and *c* are still present in the domains of $x_2$, $x_3$ and $x_4$ respectively. We suppose here that the result is positive. Hence, the values 1 and *true* are stored respectively in the fields *time* and *valid* of *stamps*[$\mu_1$, 2]. Later, when we test the validity of tuple $\tau_6$, we notice immediately (our assumption) that the
## 3.2. STR<sup>C</sup>

<figure><img src="image_56.png" /><figcaption>(a) Compressing table constraint using references towards the patterns table.</figcaption></figure>

<figure><img src="image_57.png" /><figcaption>(b) Overview of the compressed space.</figcaption></figure>

<figure><img src="image_58.png" /><figcaption>(a) Before compression.</figcaption></figure>

<caption>(b) Overview of the compressed space.</caption>

<caption>Figure 3.9: Compressed table (Gained space).</caption>

validity of $\mu_1$ was tested during the current filtering and it is enough to use the stored result in the field `valid` of `stamps[\mu_1, 2]`. Assuming that $\mu_1$ is invalid at
## 3.2. STR<sup>C</sup>

<table><caption>(a) Initialisation (currentTime=0).</caption><thead><tr><th>id</th><th>position</th><th>1</th><th>2</th><th>3</th></tr></thead><tbody><tr><td>μ<sub>1</sub></td><td>time = 0<br>valid =?</td><td>time = 0<br>valid =?</td><td>time = 0<br>valid =?</td></tr><tr><td>μ<sub>2</sub></td><td>time = 0<br>valid =?</td><td>time = 0<br>valid =?</td><td>time = 0<br>valid =?</td></tr></tbody></table>

<table><caption>(b) At the end ofoserTime=1.</caption><thead><tr><th>id</th><th>position</th><th>1</th><th>2</th><th>3</th></tr></thead><tbody><tr><td>μ<sub>1</sub></td><td>time = 1<br>valid = F</td><td>time = 1<br>valid = T</td><td>time = 1<br>valid = F</td></tr><tr><td>μ<sub>2</sub></td><td>time = 1<br>valid = T</td><td>time = 1<br>valid = T</td><td>time = 0<br>valid =?</td></tr></tbody></table>

<caption>Figure 3.10: Evolution of the stamps structure.</caption>

position 1 and 3, valid at position 2 and $\mu_2$ valid at position 1 and 2, we obtain at the end of the filtering the result presented in Figure 3.10(b).

For a constraint of arity $r$ and a pattern $\mu$, there is at most $r - |\mu| + 1$ possible pairs of $(\mu, j)$ (because $1 \le j \le r - |\mu| + 1$). So, the structure stamps has a size $O(mr)$ where $m$ is the number of detected patterns.

Algorithm 25 describes the filtering process based on STR. It first goes through all current (valid) compressed tuples. In fact, current tuples are de-limited by a pointer called currentLimit. This technique is used in almost all STR algorithms to separate valid tuples from the invalid ones in the table constraint (Section 1.3.2). The test of validity of compressed tuples is done by Algorithm 26, which indicates whether the compressed tuple is still valid from the last test or not. If the tuple is valid atoserTime, Algorithm 25 updates the set of values to be supported by the future (unassigned) variables of the con-straint scope (Lines 8 - 10) as in STR. Otherwise, if the tuple remains not valid, it is removed from the valid tuples set by updating the currentLimit pointer. At the end of the algorithm, updating domains is required.

To test the validity of a compressed tuple, we should test every value com-posing it including the prospective patterns. A value is considered valid if it is present in the current domain of its variable. If the tuple references a pattern (Line 7), we verify if the stamps data structure is updated atoserTime. If it is the case, we benefit from the result of the test of validity stored in the field valid (Lines 9 - 11), otherwise, we proceed to the test of validity and we store it for further tests (Lines 13 - 19).

**Illustration** Figure 3.11 describes the evolution of the stamps data structure by the call of Algorithm 25 due to the event $x_3 \neq c$. In Figure 3.11(a), we test the validity of $\tau_1$. Since $\tau_1$ references the pattern $\mu_1$ at its first position, we start by testing the validity of the different values composing $\mu_1$. The pattern $\mu_1$ involves the literal $(x_3,c)$ which implies its invalidity. The result is, thus, stored in stamps[$\mu_1$,1], $\tau_1$ is considered invalid (swapping it with the last valid tuple) and currentLimit is decremented. Figures 3.11(b), 3.11(c), 3.11(d), 3.11(e), 3.11(f) and 3.11(g) illustrate the different tests of validity done respectively over tuples
3.2. STR<sup>*c*</sup>

<caption>**Algorithm 25:** STR<sup>*c*</sup>(P:constraint network, c: constraint):set of variables</caption>

```c
    // Initialization of sets gacValues, as in STR
  1    foreach variable x ∈ scp(c) | x ∉ past(P) do
  2    ⏐ gacValues[x] ← ∅
    // Iteration over all current compressed tuples of c
  3    i ← 1
  4    while i ≤ currentLimit[c] do
  5        index ← position[c][i]
  6        τ ← table[c][index]
  7        if isValidTuple<comp>(c, τ) then
  8            foreach variable x ∈ scp(c) | x ∉ past(P) do
  9            if τ[x] ∉ gacValues[x] then
 10                ⏐ gacValues[x] ← gacValues[x] ∪ {τ[x]}
 11            i ← i + 1
 12        else
 13            ⏐ removeTuple(c, i, |past(P)|) // currentLimit[c] decremented
    // domains are now updated and X<sub>evt</sub> computed
 14    X<sub>evt</sub> ← ∅
 15    foreach variable x ∈ scp(c) | x ∉ past(P) do
 16        if gacValues[x] ⊂ dom(x) then
 17            dom(x) ← gacValues[x]
 18        if dom(x) = ∅ then
 19            ⏐ throw INCONSISTENCY
 20        X<sub>evt</sub> ← X<sub>evt</sub> ∪ {x}
 21    return X<sub>evt</sub>
```
## 3.2. STR<sup>C</sup>

**Algorithm 26: `isValidTuple<comp>(c: Constraint, τ: Tuple): Boolean`**
1 &nbsp;&nbsp;&nbsp;&nbsp;oldPosition ← 0
2 &nbsp;&nbsp;&nbsp;&nbsp;foreach i ∈ [0..|scp(c]| do
3 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// compressed tuples contain values and references to patterns
4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if `isValue(τ[i])` then
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if `τ[i] ∉ dom(scp(c)[oldPosition])` then
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return false
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;oldPosition ← oldPosition + 1
8 &nbsp;&nbsp;&nbsp;&nbsp;else
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// The case of a reference towards a pattern
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;μ ← patterns(|τ[i]|)
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if `stamps[μ, i].time = currentTime` then
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// The pattern was tested at the instant `currentTime` and it is not valid
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if `stamps[μ, i].valid = false` then
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return false
15 &nbsp;&nbsp;&nbsp;&nbsp;else
16 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// The pattern is not tested yet at `currentTime`
17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`stamps[μ, i].time ← currentTime`
18 &nbsp;&nbsp;&nbsp;&nbsp;foreach j ∈ [0..|μ|] do
19 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if `μ[j] ∉ dom(scp(c)[oldPosition])` then
20 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`stamps[μ, i].valid ← false`
21 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return false
22 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;oldPosition ← oldPosition + 1
23 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`stamps[μ, i].valid ← true`
24 &nbsp;&nbsp;&nbsp;&nbsp;return true

`τ<sub>7</sub>`, `τ<sub>2</sub>`, `τ<sub>3</sub>`, `τ<sub>4</sub>`, `τ<sub>6</sub>` and `τ<sub>5</sub>`. We can also observe the evolution of the `stamps` structure after each test. In Figure 3.11(f), we test the validity of tuple `τ<sub>6</sub>`, which references pattern `μ<sub>1</sub>` at position 2. Thanks to the result stored previously in `stamps[μ<sub>1</sub>, 2]` when testing the validity of `τ<sub>3</sub>`, we avoid re-checking the validity of the different values composing `μ<sub>1</sub>`. The final result of validity tests at `currentTime=1` is given by Figure 3.11(g).

### 3.2.4 Experimental results

In order to show the practical interest of our approach (STR<sup>c</sup>), we compared the behavior of STR1 [Ullmann, 2007], STR2 [Lecoutre, 2011], STR3
3.2. STR<sup>C</sup>

<figure><img src="image_59.png" /><figcaption>Figure 3.11: Example of the stamps data structure evolution at `currentTime = 1` (event $x_3 \neq c$).</figcaption></figure>
## 3.2. STR<sup>c</sup>

[Lecoutre et al., 2012] and STR<sup>c</sup> algorithms when they are integrated into the search algorithm MAC (which maintains the property of generalized arc consistency during search) on one hand and enforcing GAC using MDD on the other hand. To validate our approach, we made some tests on instances of four distinct problems available at http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html: mdd [Cheng and Yap, 2010], bdd, crosswords, nonograms [Pesant et al., 2012] and random series. The experimental results on representative instances are given in Table 3.2; the heuristic dom/ddeg is used to ensure the same search path and lexico as value ordering heuristic.

We have conducted an experimentation with our solver AbsCon (Section 1.1.4) using a cluster of bi-quad cores Xeon processors at 2.66 GHz node with 16GiB of RAM under Linux. A time-out of 1,200 seconds was set per instance.

On such instances (given in Table 3.5), STR<sup>c</sup> allows an important spatial reduction that may achieve 90 % (the crossword case) compared to the constraints used by the other approaches. For STR<sup>c</sup> we give resolution times, the compression ratio defined as the size of compressed tables over the size of initial tables and the time required to build the instance (including compression). The size of a compressed table is the size of compressed tuples and the patterns table. When we consider the time of search, it seems that STR<sup>c</sup> competes with STR1, but stay, however, supplanted by STR2. Compared to MDD, in the case where MDD supplants STR approaches, STR<sup>c</sup> doesn't give better times (mdd and nonograms). However, in the other case our approach competes with MDD and could even give better times (bdd-21-133, crossword).

Figures 3.12 and 3.13 give the number of patterns used per length for two constraints of two different problems as an example to show the distribution of used patterns based on their length. Figure 3.12 gives the distribution of patterns used for a constraint of arity 9 on a crossword-m1-ogd-23-04 instance. 69% of patterns are of length 5 which allows an efficient compression. Figure 3.13 gives the number of patterns used for a bigger constraint of arity 38 on a nonogram - gp - 108 instance. The most used patterns have lengths between 17 and 21.

Figure 3.14 shows two different curves: the dashed one for the detected frequent patterns using the trie data structure and the continuous one representing the patterns used in compressing the table constraint. There is a big difference that reaches the double, between the number of detected patterns and the used ones in the beginning of the curves. This means that when scoreThreshold is small there are many patterns detected, but when replacing their occurrences the algorithm uses only few of them. This could be explained by the decreasing order of scores used when compressing: the more frequent pattern is replaced first. Coming to the less frequent pattern, there is no tuples left. It is important to note that the number of used and detected patterns decreases when the score starts to be bigger. More and more patterns tends to be infrequent. The patterns
3.2. STR<sup>c</sup>

<table><caption>Table 3.2: CPU time (in seconds) on some selected instances solved by MAC. Compression ratio and CPU time are given for STR<sup>c</sup> between parentheses.</caption><thead><tr><th>Instance</th><th>MDD</th><th>STR1</th><th>STR2</th><th>STR3</th><th>STR<sup>c</sup></th></tr></thead><tbody><tr><td>a7-v24-d5-ps0.5-psh0.7-9</td><td><strong>17.819</strong></td><td>879</td><td>334</td><td>367</td><td>780.318<br>(43.775% - 12.192)</td></tr><tr><td>a7-v24-d5-ps0.5-psh0.9-2</td><td><strong>5.536</strong></td><td>256</td><td>145</td><td>143</td><td>283.828<br>(43.776% - 11.511)</td></tr><tr><td>a7-v24-d5-ps0.5-psh0.9-6</td><td><strong>11.397</strong></td><td>353</td><td>195</td><td>324</td><td>420.739<br>(43.776% - 11.628)</td></tr><tr><td>bdd-21-2713-15-79-9</td><td>77.171</td><td>80.2</td><td><strong>23.3</strong></td><td>60.0</td><td>84.608<br>(82.612% - 1.05)</td></tr><tr><td>bdd-21-2713-15-79-11</td><td>55.752</td><td>78.5</td><td><strong>23.5</strong></td><td>48.5</td><td>74.796<br>(82.643% - 1.164)</td></tr><tr><td>bdd-21-133-18-78-11</td><td>47.157</td><td>38.4</td><td><strong>11,0</strong></td><td>250</td><td>33.538<br>(83.975% - 1.751)</td></tr><tr><td>crossword-m1-ogd-23-04</td><td>104.485</td><td>82.7</td><td><strong>78.2</strong></td><td>103</td><td>80.085<br>(10.688% - 2.919)</td></tr><tr><td>crossword-m1c-lex-vg5-7-</td><td>86.475</td><td>43.5</td><td><strong>31.4</strong></td><td>36.6</td><td>49.393<br>(20.134% - 0.5)</td></tr><tr><td>crossword-m1c-ogd-vg10-13</td><td>TO</td><td>TO</td><td>897</td><td><strong>765</strong></td><td>TO</td></tr><tr><td>nonogram-gp-108</td><td>55.732</td><td>290</td><td><strong>78.7</strong></td><td>118</td><td>319.613<br>(94.519% - 20.561)</td></tr><tr><td>nonogram-gp-116</td><td>16.658</td><td>102</td><td><strong>21.7</strong></td><td>21.9</td><td>108.098<br>(95.7% - 7.948)</td></tr><tr><td>nonogram-gp-137</td><td>8.359</td><td>166</td><td><strong>45.4</strong></td><td>56.8</td><td>146.142<br>(92.967% - 42.072)</td></tr><tr><td>rand-6-10-10-60-950-0</td><td>67.821</td><td>75.1</td><td>45.4</td><td><strong>34.4</strong></td><td>104.554<br>(34.317% - 21.768)</td></tr><tr><td>rand-7-9-9-30-980-0</td><td>47.285</td><td>26.8</td><td><strong>18.5</strong></td><td>46.3</td><td>50.271<br>(57.469% - 19.383)</td></tr><tr><td>rand-8-20-5-18-800-8</td><td>83.815</td><td>86.6</td><td><strong>45.8</strong></td><td>574</td><td>111.949<br>(62.960% - 8.744)</td></tr></tbody></table>
### 3.3. STR-SLICE

<figure><img src="image_60.png" /><figcaption>Figure 3.12: Pie chart of patterns (totalPatterns=771) used per length for a constraint of arity 9 (nbTuples=63138) of the instance problem crossword-m1-ogd-23-04.</figcaption></figure>

number reaches 0 at *scoreThreshold*=282.

Figures 3.15 illustrates the variation of the compression ratio according to the *scoreThreshold* for the instance crossword-lex-vg5-7. Since the number of used patterns detected is affected by the score rise, the compression ratio is also concerned by this factor. The compression ratio decreases with the score rise until there is no frequent patterns detected (at *scoreThreshold*=282), and thus, the table constraint cannot be compressed. In fact, when the *scoreThreshold* rise that means that either the patterns detected are more and more frequent or the patterns are longer which implies an important reduction when replacing their occurrences.

## 3.3 STR-slice

In the first work, we defined a pattern as a sequence of consecutive values. Although this definition allowed us to obtain an important space complexity reduction, the compressed form of the table constraint presents some drawbacks especially during the filtering process preventing us to use optimized STR techniques. For each test of tuple validity, iterating over all its values is necessary (if
### 3.3. STR-SLICE

<figure><img src="image_61.png" /><figcaption>Figure 3.13: Number of patterns used per length for 4 constraints of arity 32 of the instance problem *nonogram* — *gp* — 108.</figcaption></figure>

we are not in the case of re-using the results previously done and stored in the specified data structure). These drawbacks are due to the pattern definition: a pattern could involve different variables depending on the position in which it occurs.

Aiming to be able to benefit from optimized STR techniques, we proposed in this second work a new definition of pattern and, thus, a new compressed form of table constraints by means of data-mining techniques.

This section is organized as follows: after explaining the relaxation of pattern definition in Section 3.3.1, we present, in Section 3.3.2, a compression process for table constraints, introducing the algorithm used to obtain the new form of table constraints (called “sliced” table constraints). Next, we describe, in Section 3.3.3, an optimized algorithm to enforce GAC on “sliced” table constraints. Finally, we conclude by giving some experimental results in Section 3.3.4.

#### 3.3.1 Pattern Definition

In this subsection, we introduce the new concepts of pattern and sub-table that are useful for the compression process.
### 3.3. STR-SLICE

<figure><img src="image_62.png" /><figcaption>Figure 3.14: Number of patterns (detected and used) per score threshold for a constraint of arity 7 of the instance problem crossword-lex-vg5-7.</figcaption></figure>

**Definition 32** A pattern $\mu$ of a constraint $c$ is an instantiation $I$ of some variables of $c$. We note $scp(\mu)$ its scope, which is equal to $vars(I)$, $|\mu|$ its length, which is equal to $|scp(\mu)|$, and $nbOcc(\mu)$ its number of occurrences in $rel(c)$, which is $|\{\tau \in rel(c) \mid \mu \subseteq \tau\}|$.

**Example 28** Let $c$ be a positive table constraint on variables $x_1, x_2, x_3, x_4$ and $x_5$ with $dom(x_1) = dom(x_2) = dom(x_3) = dom(x_4) = dom(x_5) = \{a, b, c\}$. Table 3.3 represents a constraint $c$ with 7 allowed tuples.

In Table 3.3, $\mu_1=\{(x_1,a), (x_4,c), (x_5,a)\}$ and $\mu_2=\{x_1=b, x_2=a\}$ are patterns of length 3 and 2, with $scp(\mu_1)=\{x_1,x_4,x_5\}$ and $scp(\mu_2)=\{x_1,x_2\}$. Their number of occurrences are respectively 3 and 2.

We present above a new definition of pattern different from the one chosen in the first work (Section 3.2). The pattern depends no more on a consecutive sequence of values, but rather on variables assignments, which are no more expected to be consecutive.

For our new compressed form, we chose to present in another way the patterns. They are no more gathered in a patterns table, but presented with the
### 3.3. STR-SLICE

<figure><img src="image_63.png" /><figcaption>Figure 3.15: Compression ratio per score threshold for a constraint of arity 7 of the instance problem *crossword-lex-vg5-7*.</figcaption></figure>

<table><caption>Table 3.3: Table constraint *c* on $x_1, x_2, x_3, x_4, x_5$.</caption><thead><tr><th>x<sub>1</sub></th><th>x<sub>2</sub></th><th>x<sub>3</sub></th><th>x<sub>4</sub></th><th>x<sub>5</sub></th></tr></thead><tbody><tr><td>c</td><td>b</td><td>c</td><td>a</td><td>c</td></tr><tr><td>a</td><td>a</td><td>b</td><td>c</td><td>a</td></tr><tr><td>a</td><td>c</td><td>b</td><td>c</td><td>a</td></tr><tr><td>b</td><td>a</td><td>c</td><td>b</td><td>c</td></tr><tr><td>b</td><td>a</td><td>a</td><td>b</td><td>b</td></tr><tr><td>c</td><td>c</td><td>b</td><td>c</td><td>a</td></tr><tr><td>a</td><td>c</td><td>a</td><td>c</td><td>a</td></tr></tbody></table>

remaining part of the tuples ("sub-table") as a unique entity called "entry" composing the final form of the constraint. These two data structures are introduced in Definitions 33 and 34.

**Definition 33 (Sub-table)** The **sub-table** *T* associated with a pattern *μ* of a constraint *c* is obtained by removing *μ* from tuples of *c* that contain *μ* and ignoring other tuples.
### 3.3. STR-SLICE

$$T = \{\tau \setminus \mu \mid \tau \in \mathrm{rel}(c) \wedge \mu \subseteq \tau\}$$

$$\textit{The scope of } T \textit{ is } scp(T) = scp(c) - scp(\mu).$$

**Example 29** Table 3.4 represents the sub-table associated with the pattern $\mu_1=\{x_1 = a, x_4 = c, x_5 = a\}$ of c, presented in Table 3.3.

<table><caption>Table 3.4: The sub-table $T_1$ associated with the pattern $\mu_1$ of c.</caption><thead><tr><th>x<sub>2</sub></th><th>x<sub>3</sub></th></tr></thead><tbody><tr><td>a</td><td>b</td></tr><tr><td>c</td><td>b</td></tr><tr><td>c</td><td>a</td></tr></tbody></table>

**Definition 34** (entry) An entry for a constraint c is a pair $(\mu, T)$ such that $\mu$ is a pattern of c and T is the sub-table associated with $\mu$.

Since the set of tuples represented by an entry $(\mu, T)$ represents in fact the Cartesian product of $\mu$ by $T$, we shall also use the notation $\mu \otimes T$ to denote a constraint entry. Notice that after the compressing ("slicing") process of a constraint into a set of entries, the set of tuples, which are not associated with any pattern can be stored in a so called default entry denoted by $(\emptyset, T)$.

**Example 30** The pattern $\mu_1=\{(x_1, a), (x_4, c), (x_5, a)\}$ of constraint c, depicted in Figure 3.16(a), appears in tuples $\tau_2, \tau_3$ and $\tau_7$. $\mu_1$ and the resulting sub-table form an entry for c, as shown in Figure 3.16(b).

<figure><img src="image_64.png" /><figcaption>Figure 3.16: Example of a constraint entry.</figcaption></figure>
### 3.3. STR-SLICE

**Definition 35 ("Sliced" table constraint)** A "sliced" table constraint is a compressed form of table constraint composed of a set of entries.

Testing the validity of classical or compressed tuples is an important operation in filtering algorithms of (compressed) table constraints. For sliced table constraints, we extend the notion of validity to constraint entries.

**Definition 36 (Pattern)** A pattern $\mu$, is valid iff $\{\forall x \in \mu, \mu[x] \in \text{dom}(x)\}$

A table constraint is valid iff all its current tuples are valid. This validity is extended to *sub-table*, since it is considered the same data structure having a scope included in the scope of the original table constraint.

**Definition 37 (Validity of an entry)** An entry $(\mu, T)$ is valid iff at least one tuple of the Cartesian product $\mu \otimes T$ is valid. Equivalently, an entry is valid iff its pattern is valid and its sub-table contains at least one valid sub-tuple.

### 3.3.2 Compression Method

In order to build the “sliced” table constraint, we apply the *FP-Growth* algorithm (Section 2.1.2) which is a technique used in data mining. To do this, we just use the first step of the algorithm (the FP-Tree construction), and then, extract classically the frequent patterns. In the context of table constraints, a transaction is a tuple; an item is, in fact, an assignment of value to a variable and a frequent itemset is a pattern, which is a partial instantiation.

We give now an example of the construction of the *FP-Tree* in the context of table compression, using the constraint given in Table 3.3 as an example. In our example, we shall use *minSupport*=2 to identify patterns that occur at least twice.

**First step: FP-Tree building** In this step, the algorithm goes through all tuples of a table constraint:

* we calculate for each value its support;

* we order the tuples in decreasing order of values support;

* we remove the infrequent values;

* we put the different tuples one by one in an FP-Tree.

**Example 31** We collect the number of occurrences of each value. By abuse of terminology, we shall call frequency the support of a value (number of occurrences). The result on our example is given in Figure 3.17.
### 3.3. STR-SLICE

<table><caption>Figure 3.17: Frequencies.</caption><thead><tr><th>s(x<sub>i</sub>, a<sub>i</sub>)</th><th>x<sub>1</sub></th><th>x<sub>2</sub></th><th>x<sub>3</sub></th><th>x<sub>4</sub></th><th>x<sub>5</sub></th></tr></thead><tbody><tr><th>a</th><td>3</td><td>3</td><td>2</td><td>1</td><td>4</td></tr><tr><th>b</th><td>2</td><td>1</td><td>3</td><td>2</td><td>1</td></tr><tr><th>c</th><td>2</td><td>3</td><td>2</td><td>4</td><td>2</td></tr></tbody></table>

We sort each tuple in decreasing order of frequency of values. The result is given in Figure 3.18 where the frequency of a value is given between parentheses. Values, which have a frequency below the threshold minSupport are removed from the tuple (they are identified in bold face) because they cannot appear in a frequent pattern.

<table><caption>Figure 3.18: Tuples sorted according to decreasing frequencies.</caption><tr><td>τ<sub>1</sub></td><td>(2) x<sub>1</sub> = c</td><td>(2) x<sub>3</sub> = c</td><td>(2) x<sub>5</sub> = c</td><td>(1) x<sub>2</sub> = b</td><td>(1) x<sub>4</sub> = a</td></tr><tr><td>τ<sub>2</sub></td><td>(4) x<sub>4</sub> = c</td><td>(4) x<sub>5</sub> = a</td><td>(3) x<sub>1</sub> = a</td><td>(3) x<sub>2</sub> = a</td><td>(3) x<sub>3</sub> = b</td></tr><tr><td>τ<sub>3</sub></td><td>(4) x<sub>4</sub> = c</td><td>(4) x<sub>5</sub> = a</td><td>(3) x<sub>1</sub> = a</td><td>(3) x<sub>2</sub> = c</td><td>(3) x<sub>3</sub> = b</td></tr><tr><td>τ<sub>4</sub></td><td>(3) x<sub>2</sub> = a</td><td>(2) x<sub>1</sub> = b</td><td>(2) x<sub>3</sub> = c</td><td>(2) x<sub>4</sub> = b</td><td>(2) x<sub>5</sub> = c</td></tr><tr><td>τ<sub>5</sub></td><td>(3) x<sub>2</sub> = a</td><td>(2) x<sub>1</sub> = b</td><td>(2) x<sub>3</sub> = a</td><td>(2) x<sub>4</sub> = b</td><td>(1) x<sub>5</sub> = b</td></tr><tr><td>τ<sub>6</sub></td><td>(4) x<sub>4</sub> = c</td><td>(4) x<sub>5</sub> = a</td><td>(3) x<sub>2</sub> = c</td><td>(3) x<sub>3</sub> = b</td><td>(2) x<sub>1</sub> = c</td></tr><tr><td>τ<sub>7</sub></td><td>(4) x<sub>4</sub> = c</td><td>(4) x<sub>5</sub> = a</td><td>(3) x<sub>1</sub> = a</td><td>(3) x<sub>2</sub> = c</td><td>(2) x<sub>3</sub> = a</td></tr></table>

Once a tuple is sorted and possibly reduced, it is inserted in the FP-Tree. We note that we don't use the dotted links between values of different paths since we don't use the second step of the FP-Growth algorithm to extract the frequent patterns. Moreover, each edge from a parent to its child is labeled with a value rather than representing the value in nodes.

Figure 3.19 represents the FP-Tree obtained on our running example. The first tuple inserted in the tree is the beginning of $τ_1$, that is $(x_1, c), (x_3, c), (x_5, c)$. This creates the leftmost branch of the tree. Each node of this branch is given a frequency of 1. The second tuple inserted is $(x_4, c), (x_5, a), (x_1, a), (x_2, a), (x_3, b)$ which creates the third leftmost branch in the tree (each node having a frequency of 1 at this step). When $τ_3$ is inserted, the new branch $(x_4, c), (x_5, a), (x_1, a), (x_2, c), (x_3, b)$ shares its first three edges with the last branch, hence the frequency of the corresponding nodes is incremented and becomes 2. The other tuples are inserted in the same way. In the end, nodes with a frequency below the threshold minSupport are pruned. The remaining tree is depicted with thick lines and circled by a dashed line in Figure 3.19.
### 3.3. STR-SLICE

<figure><img src="image_65.png" /><figcaption>Figure 3.19: FP-tree built for the table constraint in Table 3.3.</figcaption></figure>

**Second step: Frequent patterns detection** We now have to identify patterns in the *FP-Tree* which are relevant for compression. Each node of the tree corresponds to a frequent pattern $\mu$ which, can be read on the path from the root to the node. The frequency $nbOcc(\mu)$ of this pattern is given by the node itself. We choose to identify patterns based on the obtained savings while factoring this frequent pattern. In fact, the savings for a pattern are $|\mu| \times (nbOcc(\mu) - 1)$ values (we can save each occurrence of the pattern but one). In our example, we can see that the pattern $(x_4, c), (x_5, a)$ can save six values, the pattern $(x_4, c), (x_5, a), (x_1, a)$ can also save six values but the pattern $(x_4, c), (x_5, a), (x_1, a), (x_2, c)$ can save only four values. Therefore, we further prune the tree by removing nodes that save less values than their parents. The leaves of the tree we obtain represent the frequent pattern used in the compression: $(x_4, c), (x_5, a), (x_1, a)$ and $(x_2, a), (x_1, b)$.

To complete the compression, we create an entry for each frequent pattern we have identified and fill them in a last scan of the table. For each tuple, we use the *FP-Tree* to identify if the (sorted) tuple starts with a frequent pattern, in which case we add the rest of the tuple to the corresponding sub-table. Tuples which do not start with a frequent pattern are added to the default entry.

Algorithm 27 summarizes the different steps of the compression process. In a first scan of the table constraint $c$, we calculate the frequencies of each value. In a second scan, we sort each tuple by decreasing order of value frequency
### 3.3. STR-SLICE

<figure><img src="image_66.png" /><figcaption>Figure 3.20: Sliced table constraint.</figcaption></figure>

and remove each value having a frequency less than minSupport. Once a tuple is sorted, the ordered value are inserted into the FP-Tree (using Algorithm 19 but with a tuple rather than a pattern), if a path starting with these values does not already exist. If a path already exists, the node frequency counters for these values are updated. After building the whole FP-Tree, we prune all nodes having frequencies beyond minSupport or also those having less savings than their parents which means $|\mu_i| \times (frequency - 1) < (|\mu_i| - 1) \times (frequency' - 1)$ (Algorithm 28). To compress c a last scan is required. For each tuple $\tau$ of constraint c, we look for a pattern $\mu$ sharing with it its first values (already ordered in the second scan) in FP-Tree (Algorithm 29). If there is a pattern $\mu$ found, we look in the “sliced” table constraint if there is an entry having as pattern $\mu$. If it is the case, we add the sub-tuple $(\tau \setminus \mu)$ to the sub-table of the identified entry, otherwise, we create a new entry having as pattern $\mu$ and then we put the sub-tuple $(\tau \setminus \mu)$ to the sub-table (Line 15). If there is no pattern found in the FP-Tree, we add the tuple $\tau$ to the defaultEntry (Line 18).

Figure 3.21 describes the gained space obtained thanks to the compression process. The gained space, without considering position data structure (Section 1.3.2), is obtained as follows:

$$ \Sigma_i [\text{gainedSpace}(\text{entry}(i))] = \Sigma_i [|\mu_i| \times (|\text{subTable}(i)| - 1)] \\ \text{For our "sliced" table, the gained space is } 3 \times 2 + 2 \times 1 = 6 $$
### 3.3. STR-SLICE

**Algorithm 27:** compress-STR-slice(c: Constraint, minSupport: float)
**Initialization of frequencies**
1 **foreach** i ∈ length(frequencies) **do**
2   **frequencies[i]** ← 0
3 **First scan:** compute the frequency of each value of c
4 **foreach** τ ∈ table(c) **do**
5   **foreach** v ∈ τ **do**
6   **frequencies[v]**++
7 **Second scan:** build FP-Tree
8 **foreach** τ ∈ table(c) **do**
9   **sorting** τ and removing values less frequent than minSupport
10   τ ← sortTuple(τ, frequencies, minSupport)
11   **insert** τ into FP-Tree by updating nodes frequency
12   addTuple(root(FP-Tree),τ)
13 **removing** nodes less frequent than minSupport or such that
14   |μ| × (f − 1) is smaller than for their parents
15 pruneTree(root(FP-Tree),minSupport,0)
16 **Third scan:** compress c
17 **foreach** τ ∈ table(c) **do**
18   **μ** ← searchPattern(root(FP-Tree),τ)
19   **if** μ ≠ nil **then**
20     **entry** ← getEntry entries[c],μ)
21     **if** entry = nil **then**
22       **There is no entry for this pattern**
23       **entry** ← addEntry entries[c],μ)
24     **addSubTuple**(entry,τ \ μ)
25   **else**
26   **addSubTuple**(defaultEntry,τ)

### 3.3.3 Filtering Sliced Table Constraints

In order to enforce GAC on sliced table constraints, our idea is to adapt STR, and more specifically the optimized variant STR2, on the compressed form of this kind of constraint. As a sliced table constraint is composed of several entries, each one composed of both a pattern and a sub-table, the filtering process we propose acts at two distinct levels. At a high level, the validity of each entry is checked, and at a low-level, the validity of each pattern and each sub-tuple is checked. Remember that an entry is valid iff both its pattern is valid and at least
### 3.3. STR-SLICE

<caption>**Algorithm 28:** pruneTree(node: Node, minSupport: Float, parentSavings: Integer)</caption>

1. savings ← (node.value − 1) × node.level
2. if node ≠ nil then
3.     if node.value < minSupport or savings < parentSavings then
4.         remove(node)
5. foreach child ∈ node.getChildren() do
6.     pruneTree(child, minSupport, savings)

<caption>**Algorithm 29:** searchPattern(root: Node, τ: Tuple): pattern</caption>

1. root ← node
2. µ ← µ
3. for i ∈ [0..|τ|] do
4.     node ← node node := nodeمرة τ[i]
5.     if node ≠ nil then
6.         µ ← µ + τ[i]
7.     else
8.         break
9. return µ

one tuple from its sub-table is valid (see Definition 37). In this section, we first describe the employed data structures, then we introduce our GAC algorithm, and finally we give an illustration.

## Data structures

A sliced table constraint *c* is represented by an array *entries*[*c*] of *p* entries. Managing the set of valid entries, called *current*<fnref n="1" /> entries, is performed as follows:

* entriesLimit[*c*] is the index of the last current entry in *entries*[*c*]. The elements in *entries*[*c*] at indexes ranging from 1 to entriesLimit[*c*] are the current entries of *c*.

* removing an entry (that has become invalid) at index *i* is performed by a call of the form removeEntry(*c*, *i*). Such a call swaps the entries at indexes *i* and entriesLimit[*c*], and then decrements entriesLimit[*c*]. Note that the initial order of entries is not preserved.

<footnote n="1">¹Current entries correspond to valid entries at the end of the previous invocation of the algorithm.</footnote>
### 3.3. STR-SLICE

<figure><img src="image_67.png" /><figcaption>Figure 3.21: Gained Space after compression.</figcaption></figure>

* restoring a set of entries can be performed by simply changing the value of `entriesLimit[c]`.

Each entry in `entries` can be represented as a record composed of a field `pattern` and a field `subtable`. More precisely:

* the field `pattern` stores a partial instantiation $\mu$, and can be represented in practice as a record of two arrays: one for the variables, the scope of the pattern, and the other for the values.

* the field `subtable` stores a sub-table $T$, and can be represented in practice as a record of two arrays: one for the variables, i.e., the scope of the sub-table $T$, and the other, a two-dimensional array, for the sub-tuples.

Managing the set of valid sub-tuples, called *current sub-tuples*, of $T$, is performed as follows:

* `limit[T]` is the index of the last current sub-tuple in $T$. The elements in $T$ at indexes ranging from 1 to `limit[T]` are the current sub-tuples of $T$.

* removing a sub-tuple (that has become invalid) at index $i$ is performed by a call of the form `removeSubtuple(T, i)`. Such a call swaps the sub-tuples at indexes $i$ and `limit[T]$, and then decrements `limit[T]`. Note that the initial order of sub-tuples is not preserved.
### 3.3. STR-SLICE

* restoring a set of sub-tuples can be performed by simply changing the value of `limit[T]`.

Note that the management of both current entries and current sub-tuples is in the spirit of STR. Also, as in [Lecoutre, 2011], we introduce two sets of variables, called $S^{val}$ and $S^{sup}$. The set $S^{val}$ contains uninstantiated variables (and possibly, the last assigned variable) whose domains have been reduced since the previous invocation of the filtering algorithm on $c$. To set up $S^{val}$, we need to record the domain size of each modified variable $x$ right after the execution of STR-slice on $c$: this value is recorded in `lastSize[x]`. The set $S^{sup}$ contains uninstantiated variables (from the scope of constraint $c$) whose domains contain each at least one value for which a support must be found. We also use an array `gacValues[x]` for each variable $x$. At any time, `gacValues[x]` contains all values in $dom(x)$ for which a support has already been found: hence, values for a variable $x$ without any proved support are exactly those in $dom(x) \setminus gacValues[x]$. Note that the sets $S^{val}$ and $S^{sup}$ are initially defined with respect to the full scope of $c$. However, for each sub-table we also shall use local sets $S^{lval}$ and $S^{lsup}$ of $S^{val}$ and $S^{sup}$ as explained later.

#### Algorithm

Algorithm 30 is a filtering procedure, called STR-slice, that establishes GAC on a specified sliced table constraint $c$ belonging to a CN $N$. Lines 1–10, which are exactly the same as those in Algorithm 5 of [Lecoutre, 2011], allow us to initialize the sets $S^{val}$, $S^{sup}$ and `gacValues`. Recall that $S^{val}$ must contain the last assigned variable, denoted by `lastPast(P)`, if it belongs to the scope of $c$. Lines 11–22 iterate over all current entries of $c$. To test the validity of an entry, we check first the validity of the pattern $\mu$ (Algorithm 31), and then, only when the pattern is valid, we check the validity of the sub-table $T$ by scanning it (Algorithm 32). If an entry is no more valid, it is removed at Line 22. Otherwise, considering the values that are present in the pattern, we have to update `gacValues` as well as $S^{sup}$ when a first support for a variable is found. Lines 23–30, which are exactly the same as those in Algorithm 5 of [Lecoutre, 2011], manage the reduction of domains: unsupported values are removed at line 25 and if the domain of a variable $x$ becomes empty, an exception is thrown at line 27. Also, the set of variables $X_{evt}$ reduced by STR-slice is computed and returned so that these “events” can be propagated to other constraints.

Algorithm 32 is an important function, called `scanSubtable`, of STR-slice. Its role is to iterate over all current (sub)tuples of a given sub-table, in order to collect supported values and to remove invalid tuples. Note that when this function is called, we have the guarantee that the pattern associated with the sub-table is valid (note the “and then” short-circuit operator at Line 14 of Algorithm 30). The first part of the function, lines 1–8, allow us to build the local sets
### 3.3. STR-SLICE

**Algorithm 30: STR-slice(c: constraint):set of variables**

```c
// Initialization of sets $S^{val}$ and $S^{sup}$, as in STR2
1 $S^{val} \leftarrow \emptyset$
2 $S^{sup} \leftarrow \emptyset$
3 if lastPast($P$) $\in$ scp($c$) then
4 $\lfloor$ $S^{val} \leftarrow S^{val} \cup \{\text{lastPast}(P)\}$
5 foreach variable $x \in$ scp($c$) $| x \notin$ past($P$) do
6 $\quad$ gacValues[$x$] $\leftarrow$ $\emptyset$
7 $\quad$ $S^{sup} \leftarrow S^{sup} \cup \{x\}$
8 if $|dom(x)| \neq \text{lastSize}[c][x]$ then
9 $\quad$ $\lfloor$ $S^{val} \leftarrow S^{val} \cup \{x\}$
10 $\quad$ $\text{lastSize}[c][x] \leftarrow |dom(x)|$
11 // Iteration over all entries of $c$
12 i $\leftarrow$ 1
13 while $i \le$ entriesLimit[$c$] do
14 $\quad$ $(\mu, T) \leftarrow$ entries[$c$][$i$] // $i$th current entry of $c$
15 if isValidPattern($\mu$) and then scanSubtable($T$) then
16 $\quad$ foreach variable $x \in$ scp($\mu$) $| x \in$ $S^{sup}$ do
17 $\quad$ $\quad$ if $\mu[x] \notin$ gacValues[$x$] then
18 $\quad$ $\quad$ $\lfloor$ $\text{gacValues}[x] \leftarrow \text{gacValues}[x] \cup \{\mu[x]\}$
19 $\quad$ $\quad$ if $|dom(x)| = |\text{gacValues}[x]|$ then
20 $\quad$ $\quad$ $\lfloor$ $S^{sup} \leftarrow S^{sup} \setminus \{x\}$
21 $\quad$ $\quad$ $i \leftarrow i + 1$
22 else
23 $\quad$ $\lfloor$ removeEntry($c$, $i$) // entriesLimit[$c$] decremented
24 // domains are now updated and $X_{evt}$ computed, as in STR2
25 $X_{evt} \leftarrow \emptyset$
26 foreach variable $x \in$ $S^{sup}$ do
27 $\quad$ $\lfloor$ $dom(x) \leftarrow \text{gacValues}[x]$ 
28 $\quad$ $\quad$ if $dom(x) = \emptyset$ then
29 $\quad$ $\quad$ $\lfloor$ throw INCONSISTENCY
30 $X_{evt} \leftarrow X_{evt} \cup \{x\}$
31 $\lfloor$ $\text{lastSize}[c][x] \leftarrow |dom(x)|$
32 return $X_{evt}$
```

$S^{lval}$ and $S^{lsup}$ from $S^{val}$ and $S^{sup}$. Such sets are obtained by intersecting $S^{val}$ with scp($T$) and $S^{sup}$ with scp($T$), respectively. Once the sets $S^{lval}$ and $S^{lsup}$
### 3.3. STR-SLICE

<table><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>foreach</td><td>variable x &isin; scp(&mu;)</td><td>do</td></tr><tr><td>2</td><td></td><td>if</td><td>&mu;[x] &notin; dom(x)</td><td>then</td></tr><tr><td>3</td><td></td><td>&nbsp;&nbsp;&nbsp;&nbsp;L</td><td>return false</td></tr><tr><td>4</td><td>return</td><td>true</td></tr></tbody></table>

are initialized, we benefit from optimized operations concerning validity checking and support seeking, as in STR2. The second part of the function, lines 9–21, consists in iterating over all current sub-tuples of T. This is a classical STR2-like traversal of a set of tuples. Finally, Line 22 returns true when there still exists at least one valid sub-tuple.

It is interesting to note the lazy synchronization performed between the global unique set $S^{sup}$ and the specific local sets $S^{lsup}$ (one such set per sub-table). When a variable $x$ is identified as “fully supported”, it is immediately removed from $S^{sup}$ (see Line 19 of Algorithm 30 and Line 18 of Algorithm 32). Consequently, that means that the next sub-tables (entries) will benefit from such a reduction, but the information is only transmitted at initialization (lines 6–8 of Algorithm 32). On the other hand, once initialized, the global set $S^{val}$ is never modified during the execution of STR-slice.

**Backtracking issues:** In our implementation, entries and tuples can be restored by modifying the value of the limit pointers (`entriesLimit[c]` and `limit[T]` for each sub-table $T$ of $c$), recorded at each search depth. Restoration is then achieved in $O(1+p)$ (for each constraint) where $p$ is the number of entries. However, by introducing a simple data structure, it is possible to only call the restoration procedure when necessary, limiting restoration complexity to $O(1)$ in certain cases: it suffices to register the limit pointers that need to be updated when backtracking, and this for each level. When the search algorithm backtracks, we also have to deal with the array `lastSize`. As mentioned in [Lecoutre, 2011], we can record the content of such an array at each depth of search, so that the original state of the array can be restored upon backtracking. As STR-slice is a direct extension of STR2, it enforces GAC.

### Illustration

Figures 3.22 and 3.23 illustrate the different steps for filtering a sliced table constraint, when STR-slice is called after an event. In Figure 3.22, considering that the new event is simply $x_3 \neq a$ (i.e., the removal of the value $a$ from $dom(x_3)$), STR-slice starts checking the validity of the current entries (from 1 to `entriesLimit`). So, for the first entry, the validity of the pattern $\mu=\{(x_1, a), (x_4, c), (x_5, a)\}$ is first checked. Since $\mu$ remains valid (our hypothesis
### 3.3. STR-SLICE

<caption>**Algorithm 32:** scanSubtable(T: sub-table): Boolean</caption>

```c
// Initialization of local sets S^{lval} and S^{lsup} from S^{val} and S^{sup}
1 S^{lval} ← ∅
2 foreach variable x ∈ S^{val} do
3   if x ∈ scp(T) then
4     S^{lval} ← S^{lval} ∪ {x}
5 S^{lsup} ← ∅
6 foreach variable x ∈ S^{sup} do
7   if x ∈ scp(T) then
8     S^{lsup} ← S^{lsup} ∪ {x}
9 // Iteration over all (sub)tuples of T
10 i ← 1
11 while i ≤ limit[T] do
12   τ ← T[i] // ith current sub-tuple of T
13   if isValidSubtuple(S^{lval}, τ) then
14     foreach variable x ∈ S^{lsup} do
15       if τ[x] ∉ gacValues[x] then
16         gacValues[x] ← gacValues[x] ∪ {τ[x]}
17         if |dom(x)| = |gacValues[x]| then
18           S^{lsup} ← S^{lsup} \ {x}
19           S^{sup} ← S^{sup} \ {x}
20     i ← i + 1
21   else
22     removeSubtuple(T, i) // limit[T] decremented
23 return limit[T] > 0
```

<caption>**Algorithm 33:** isValidSubtuple(S^{lval}: variables, τ: tuple): Boolean</caption>

```c
1 foreach variable x ∈ S^{lval} do
2   if τ[x] ∉ dom(x) then
3     return false
4 return true
```

is that the event was only $x_3 \neq a$), the sub-table of the first entry is scanned. Here, only the sub-tuple $\{(x_2, c), (x_3, a)\}$ is found invalid, which modifies the value of limit for the sub-table of this first entry. After the call to STR-slice, the constraint is as in Figure 3.22(b).
### 3.3. STR-SLICE

<figure><img src="image_68.png" /><figcaption>Figure 3.22: STR-slice called on a slice table constraint after the event $x_3 \neq a$.</figcaption></figure>

<figure><img src="image_69.png" /><figcaption>Figure 3.23: From Figure 3.22(b), STR-slice called after the event $x_3 \neq b$.</figcaption></figure>

In Figure 3.23, considering now that the new event is $x_3 \neq b$, we start again with the first current entry. Figuring out that the pattern is still valid, we check the validity of the associated sub-tuples. Since the sub-tuple $\{x_2 = a, x_3 = b\}$ is no more valid, it is swapped with $\{x_2 = c, x_3 = b\}$. This latter sub-tuple is then also found invalid, which sets the value of `limit` to 0. This is illustrated in
### 3.3. STR-SLICE

<table><caption>Table 3.5: Mean CPU time (in seconds) to solve instances from different series with MAC. Mean compression ratio and CPU time are given for STR-slice between parentheses.</caption><thead><tr><th>Instance</th><th>#ins</th><th>STR1</th><th>STR2</th><th>STR3</th><th>STR-slice</th></tr></thead><tbody><tr><td>a7-v24-d5-ps05</td><td>11</td><td>298.05</td><td>147.73</td><td>189.14</td><td><strong>115.30</strong> (66% - 5.74)</td></tr><tr><td>bdd</td><td>70</td><td>44.53</td><td><strong>13.44</strong></td><td>99.21</td><td>20.35 (86% - 0.59)</td></tr><tr><td>crossword-ogd</td><td>43</td><td>90.05</td><td>39.35</td><td><strong>25.69</strong></td><td>29.59 (75.51% - 0.36)</td></tr><tr><td>crossword-uk</td><td>43</td><td>95.20</td><td>45.88</td><td><strong>44.33</strong></td><td>47.21 (88.69% - 0.18)</td></tr><tr><td>renault</td><td>46</td><td>19.66</td><td>14.39</td><td><strong>13.37</strong></td><td>17.20 (47.15% - 0.67)</td></tr></tbody></table>

Figure 3.23(a). As the sub-table of the first entry is empty, the entry is removed by swapping its position with that of last current entry. After the call to STR-slice, the constraint is as in Figure 3.23(b) (note that a second swap of constraint entries has been performed).

### 3.3.4 Experimental results

In order to show the practical interest of our approach to represent and filter sliced table constraints, we have conducted an experimentation in the same condition as the first approach (see Section 3.2.4). Since STR1, STR2 and STR3 belong to the state-of-the-art GAC algorithms for table constraints, we compare the respective behaviors of STR variants and STR-slice on the different series of instances used in Section 3.2.4

Table 3.5 shows mean results (CPU time in seconds) per series. For each series, the number of tested instances is given by #ins; it corresponds to the number of instances solved by all three variants within 1,200 seconds. Note that the mean compression ratios and CPU times (in seconds) are also given for STR-slice between parentheses. We define the compression ratio as the size of the sliced tables over the size of the initial tables, where the size of a (sliced) table is the number of values over all patterns and (sub-)tables. The used minSupport is equal to 10% of the number of tuples in the table. The results in Table 3.5 show that STR-slice is competitive with both STR2 and STR3. Surprisingly, although the compression ratio obtained for the instances of the series renault is rather encouraging, the CPU time obtained for STR-slice is disappointing. We suspect that the presence of many constraints with small tables in the renault instances is penalizing for STR-slice because, in that case, the overhead of managing constraint entries is not counterbalanced by the small absolute spatial reduction. Table 3.6 presents the results obtained on some instances. A general observation
### 3.3. STR-SLICE

<table><caption>Table 3.6: CPU time (in seconds) on some selected instances solved by MAC. Compression ratio and CPU time are given for STR-slice between parentheses.</caption><thead><tr><th>Instance</th><th>MDD</th><th>STR1</th><th>STR2</th><th>STR3</th><th>STR-slice</th></tr></thead><tbody><tr><td>a7-v24-d5-ps0.5-psh0.7-9</td><td><b>17.819</b></td><td>879</td><td>334</td><td>367</td><td>200<br>(68.75% - 5.406)</td></tr><tr><td>a7-v24-d5-ps0.5-psh0.9-2</td><td><b>5.536</b></td><td>256</td><td>145</td><td>143</td><td>93<br>(62.5% - 5.957)</td></tr><tr><td>a7-v24-d5-ps0.5-psh0.9-6</td><td><b>11.397</b></td><td>353</td><td>195</td><td>324</td><td>174<br>(62.5% - 5.82)</td></tr><tr><td>bdd-21-2713-15-79-9</td><td>77.171</td><td>80.2</td><td><b>23.3</b></td><td>60.0</td><td>35.4<br>(88.230% - 0.283)</td></tr><tr><td>bdd-21-2713-15-79-11</td><td>55.752</td><td>78.5</td><td><b>23.5</b></td><td>48.5</td><td>31.7<br>(88.05% - 0.28)</td></tr><tr><td>bdd-21-133-18-78-11</td><td>47.157</td><td>38.4</td><td><b>11.0</b></td><td>250</td><td>19.0<br>(86.12% - 0.866)</td></tr><tr><td>crossword-m1-ogd-23-04</td><td>104.485</td><td>82.7</td><td><b>78.2</b></td><td>103</td><td>80.1<br>(73.90% - 1.039)</td></tr><tr><td>crossword-m1c-lex-vg5-7-</td><td>86.475</td><td>43.5</td><td><b>31.4</b></td><td>36.6</td><td>34.5<br>(96.17% - 0.097)</td></tr><tr><td>crossword-m1c-ogd-vg10-13</td><td>TO</td><td>TO</td><td>897</td><td>765</td><td><b>750</b><br>(74.84% - 0.801)</td></tr><tr><td>nonogram-gp-108</td><td>55.732</td><td>290</td><td><b>78.7</b></td><td>118</td><td>83.6<br>(74.93% - 2.475)</td></tr><tr><td>nonogram-gp-116</td><td><b>16.658</b></td><td>102</td><td>21.7</td><td>21.9</td><td>22.8<br>(79.99% - 1.455)</td></tr><tr><td>nonogram-gp-137</td><td><b>8.359</b></td><td>166</td><td>45.4</td><td>56.8</td><td>29.4<br>(82.96% - 3.5)</td></tr><tr><td>rand-6-10-10-60-950-0</td><td>67.821</td><td>75.1</td><td>45.4</td><td><b>34.4</b></td><td>42.5<br>(77.77% - 4.950)</td></tr><tr><td>rand-7-9-9-30-980-0</td><td>47.285</td><td>26.8</td><td><b>18.5</b></td><td>46.3</td><td>22.9<br>(75% - 7.489)</td></tr><tr><td>rand-8-20-5-18-800-8</td><td>83.815</td><td>86.6</td><td><b>45.8</b></td><td>574</td><td>64.2<br>(72.36% - 4.787)</td></tr></tbody></table>
### 3.3. STR-SLICE

from this experimentation is that STR-slice is a competitor to STR2 and STR3, but a not a competitor that takes a real advantage compared to MDD.

## Comparison with related approaches

In this section we compare both contributions with the approaches presented in Section 2.1. Table 3.7 compares, in a first time, our two contributions with ShortSTR2 algorithm (see Section 2.1.2). This table presents both resolution time (CPU time) and compression ratio as defined before (compressed table / original table). It is important to note that the resolution time for ShortSTR2 are given considering that the algorithm run on Minion solver [Gent et al., 2006]. We gathered the common benchmarks. Obviously from the given results, Short-STR2 outperforms our contribution only on bddSmall problem but the other compression ratios are too small (100% means that the algorithm does not compress the table). For the running time, we cannot make any comparison since two different solvers are used to solve these problems.

<table><caption>Table 3.7: STR<sup>c</sup> and STR-slice compared to ShortSTR2.</caption><thead><tr><th>Instance</th><th colspan="2">STR<sup>c</sup></th><th colspan="2">STR-slice</th><th colspan="2">ShortSTR2</th></tr></thead><tbody><tr><td>rand-8-20</td><td>111.949</td><td>62.960%</td><td>64.2</td><td>72.36%</td><td>3,207</td><td>99%</td></tr><tr><td>bddSmall</td><td>64.314</td><td>83.076%</td><td>28.7</td><td>87.46%</td><td>521.10</td><td>52.63%</td></tr><tr><td>crosswordVg</td><td>49.393</td><td>20.134%</td><td>34.5</td><td>96.17%</td><td>396.25</td><td>100%</td></tr></tbody></table>

Table 3.8 makes also a comparison considering the common benchmarks between the approaches: STR<sup>c</sup>, STR-slice and STR2-C (Section 2.1.2). All these problems run on AbsCon solver. STR2-C outperforms our contribution especially on the random problems (MDD0.7 and MDD0.9) considering both compression ratio and resolution time.

<table><caption>Table 3.8: STR<sup>c</sup> and STR-slice compared to STR2-C.</caption><thead><tr><th>Instance</th><th colspan="2">STR<sup>c</sup></th><th colspan="2">STR-slice</th><th colspan="2">STR2-C</th></tr></thead><tbody><tr><td>rand-8-20</td><td>111.949</td><td>62.960%</td><td>64.2</td><td>72.36%</td><td>26.0</td><td>60.2%</td></tr><tr><td>MDD 0.7</td><td>780.318</td><td>43.775%</td><td>200</td><td>68.75%</td><td>171.3</td><td>5%</td></tr><tr><td>MDD 0.9</td><td>352.281</td><td>43.776%</td><td>133.5</td><td>62.5%</td><td>28.5</td><td>1.5%</td></tr></tbody></table>

Due to the lack of experiments for data-mining based approaches we could not make any comparison.
### 3.4 Conclusions and discussion

Through the first work (STR<sup>c</sup>), we combine both techniques of simple tabular reduction and compression. Identifying recurring patterns in tuples of different tables, reduces memory space and also the CPU time by avoiding redundant validity tests. From our tests, the STR<sup>c</sup> algorithm we propose seems to be competitive with STR1 (in the search step) but supplanted by STR2 and sometimes STR3.

For the second approach, we combined a new compression technique using the concept of sliced table constraints and an optimized adaptation of the tabular reduction (as in STR2) for the filtering process. Our experimentation shows that STR-slice is a competitor to the state-of-the-art STR2 and STR3 algorithms.

For the first compression technique just one scan of the table is required to build the trie of frequent patterns which is not the case for the second compression technique requiring two scans to build the trie. Even if we use the same data structure (trie) during the compression process for both approaches, but each trie have a different representation. In the first one we gather all paths starting with the same value. However, in the second one we gather all paths sharing the same literal.

Both of the two compression methods enable us to obtain high ratios of total space reduction. Nevertheless, the second compression technique supplants the drawback of the first one. In fact, the issue of compressing extensional constraints has two faces: the first one is to achieve a high reduction ratio of the required memory space which is the easiest step since there are several proposed compression approaches aiming to that especially in the data mining field. However, the most difficult step is how to represent the compressed constraint in a suitable way avoiding slowing down the filtering process, but also, if it is possible, to speed it up taking advantages from the several dynamic compression techniques like STR.

Since our first compression technique defines a pattern as a sequence of values independently from their positions which implies the independence from the variables, we were not able to use the STR2 and STR3 techniques which are based on variables domains changes. That is why the first approach could not compete with the state-of-the-art STR2 and STR3 algorithms. This is not the case of the second approach (“sliced” table constraints) that is based on an optimized adaptation of the tabular reduction for the filtering process. The experimental results show that STR-slice algorithm is competitive with STR2 and STR3 even if it is sometimes sanctioned due to the compression time. Compared to MDD, the two approaches competes with MDD only in the case where STR variants supplant it.
# Chapter 4

## Using Singleton Arc Consistency in Parallel to Improve Search

### Contents

<table><tr><td>4.1</td><td>Architecture</td><td>151</td></tr><tr><td>4.2</td><td>Master's side</td><td>153</td></tr><tr><td>4.2.1</td><td>The Assignments Stack</td><td>153</td></tr><tr><td>4.2.2</td><td>The Messages Queue</td><td>154</td></tr><tr><td>4.3</td><td>Workers' side</td><td>157</td></tr><tr><td>4.3.1</td><td>The Assignments Stack</td><td>157</td></tr><tr><td>4.3.2</td><td>The Messages Queue</td><td>159</td></tr><tr><td>4.3.3</td><td>The Literals Queue</td><td>160</td></tr><tr><td>4.4</td><td>Enhancing the search process</td><td>162</td></tr><tr><td>4.5</td><td>Experimental results</td><td>164</td></tr></table>
### Introduction

In Section 2.2, we introduced the main categories of the state-of-the-art of parallel approaches that have been proposed in order to solve CSP instances within a parallel architecture. Some approaches distribute the search tree over workers while others use a portfolio of workers which compete in order to solve an instance of a problem.

In this chapter, we explore another way of using a parallel architecture in which a main solver is helped by side workers that partially establish consistencies, which are otherwise two heavy to be maintained by the main solver.

This chapter is organized as follows:

* In Section 4.1, we describe our approach and the used parallel architecture;

* In Section 4.2, we introduce the data structures and algorithms used from the side of the master;

* In Section 4.3, we explore the workers side and how they interact with each other and with the master;

* In Section 4.4, we explain how our architecture is supposed to enhance the search process;

* Finally, we conclude with experimental results in Section 4.5.

### 4.1 Architecture

Our approach is based on a master/workers architecture where the master is a sequential CSP solver and the different workers help their master during the search process. This main solver transmits its current instantiation to its side workers, which will try to infer relevant information by exploiting different levels of consistencies. As soon as new facts are discovered, they are transmitted to the main solver that takes them into account as soon as possible. Our goal is to have a synchronization between the main solver and the side workers as lightweight as possible. In our current work, both the main solver and the side workers (threads running on different cores) run on the same host.

Different consistencies were introduced in Chapter 1 that could be ranked with respect to their strength. Singleton Arc Consistency (SAC) [Debruyne and Bessiere, 1997] is a strong consistency that is very expensive to enforce during search [Lecoutre and Prosser, 2006]. Performing each SAC test in a sequential solver is too heavy. But in a parallel solver available cores can perform these SAC tests for free (at least from a wall-clock point of view). The literals that are discovered SAC-inconsistent are transmitted to the master in order to avoid them in its future assignments.
## 4.1. ARCHITECTURE

<figure><img src="image_70.png" /><figcaption>Figure 4.1: Overview of the architecture.</figcaption></figure>

Figure 4.1 describes the architecture of our system. In fact, each master and worker has its own copy of the problem. The master solves the problem whereas the workers enforce SAC on some literals of the problem. An *Assignments Stack* is associated to each master and worker. The master stores all positive and negative decisions made in its own *Assignments Stack* while the workers only copy them to their stack, each time there are new decisions. This stack describes the state of the problem of each entity. All workers get literals to test for consistency
## 4.2. MASTER’S SIDE

from a *Literals Queue* which is a shared data structure between all of them. If enforcing SAC on these literals produces new facts, new messages are put into the *Messages Queue* which is a shared data structure between the master and the workers. The master in his turn extracts messages from the *Messages Queue* in order to exploit them in its solving process by avoiding failures.

We detail our approach from both sides: the master’s side in Section 4.2 and the workers one in Section 4.3.

# 4.2 Master’s side

In our approach, the master, runs a classical CSP solver using only two additional data structures: the *Messages Queue* which is shared with the workers and a *Set of Inferences* which is its own data structure. The *Assignments Stack* is accessible by the workers in order to get the problem state. All these used data structures are detailed in this Section from the master’s side.

## 4.2.1 The Assignments Stack

In our context, a search tree is composed of different levels which represents the number of variables composing the problem. In the next algorithms, we consider that each level corresponds to an assignment of a variable. The *Assignments Stack* stores all decisions made by the solver. They might be positive (assignment) or negative (refutation) decisions. Each positive decision defines a level to which corresponds a time-stamp indication at which time this assignment was taken. This time-stamp is given by a global counter (on 64 bits to avoid any overflow) which is initialized to 0 and incremented each time a decision is taken. This information is used to identify the modifications of the *Assignments Stack* and is further described from the workers side. In fact, a time-stamp is only associated with positive decisions (assignments) which is a feature of AbsCon solver [Lecoutre and Tabary, 2007]. Positive decisions are stored in the stack in a consecutive order. When a backtrack occurs, the value causing the backtrack is removed from the domain of its variable and this refutation is added to the previous level.

**Example 32** *Figure 4.2 gives an illustration of the Assignments Stack management when different decisions are made. Positive decisions are stored in the stack in a consecutive order. When a backtrack occurs, e.g. $x_2 \neq a$ in Figure 4.2(c), the value causing the backtrack is removed from the domain of its variable and this refutation is added to the previous level. The time-stamp of the last positive decision before backtrack does not change.*
## 4.2. MASTER'S SIDE

<figure><img src="image_71.png" /><figcaption>Figure 4.2: Master’s side: managing the *Assignments Stack*.</figcaption></figure>

### 4.2.2 The Messages Queue

Before a decision is taken, the master checks if some information has been inferred by the other workers. This is done by checking the content of the *Messages Queue*, which is read by the master and written by the workers. When a message is extracted from this queue, the master first checks if the inference is still relevant in the current state of the solver (the message could be outdated because the master backtracked in between). If the message is not relevant, it is ignored. Otherwise, the inference is taken into account.

In fact, a message contains two main information:

* **literal**: the pair (variable,value) to avoid in future assignments;

* **(level, timeStamp)**: the pair level and its time-stamp in which the property
## 4.2. MASTER'S SIDE

"the literal is SAC-inconsistent" is still relevant.

Algorithm 34 describes how the master judges the validity of the messages sent by workers to use them in the inference process. According to the master, a message is still relevant *iff* the level of the test is **higher** (in the search tree) than the master solver level *and* the time-stamps are **coherent**.

<table><caption>**Algorithm 34:** `isValidMessage(msg: Message): Boolean`</caption><tr><td>1</td><td><b>if</b> msg.level &le; currentLevel <b>and</b><br/>msg.timeStamp = timeStamp[msg.level] <b>then</b></td></tr><tr><td>2</td><td><b>return</b> true</td></tr><tr><td>3</td><td><b>return</b> false</td></tr></table>

<figure><img src="image_72.png" /><figcaption>Figure 4.3: A master's search tree at level 3.</figcaption></figure>

Once the master figures out that the message is still relevant, it stores it in its own data structure, called `setOfInferences`. In fact, `setOfInferences` is a table where `setOfInferences[i]` defines the messages extracted and used at level *i*. Thanks to this data-structure, the master can re-use these inferences in higher
## 4.2. MASTER'S SIDE

<figure><img src="image_73.png" /><figcaption>Figure 4.4: The master backtracking to level 2.</figcaption></figure>

levels, when a backtrack occurs. Figure 4.3 describes the use of `setOfInferences`. At level 3, the master receives a new message $m_1=\{level=2, timeStamp=2, literal=(x_1, a)\}$. This message is relevant with respect to the master current state (level ≤ master current level and `timeStamp` = `timeStamp[2]`). The master can, thus, benefit from this message by deleting this value as long as it has not backtracked. Value `a` is then removed from `dom(x_1)` and the message is stored in `setOfInferences`. It happens that a backtrack occurs to the level 2 which implies restoration of the previous state of the problem at level 2: the inference application of the message $m_1$ is undone when backtracking. Since $m_1$ remains relevant after backtracking, the master re-applies it.

Algorithm 35 describes how the master manages the messages received from the different workers and the inferences already stored in `setOfInferences`. In fact, the master checks `setOfInferences` only when a backtrack occurs (Lines 1 - 7). The parameter `hasBacktracked` indicates if the master has backtracked or not since the last decision made. If it is the case, the master re-applies all the inferences stored starting from its current level after backtracking. If the master
4.3. WORKERS' SIDE

**Algorithm 35: applyMessages hasBacktracked Boolean)**
1 **if** hasBacktracked **then**
2 &nbsp;&nbsp;**foreach** i ∈ [currentLevel+1, levelBeforeBacktrack] **do**
3 &nbsp;&nbsp;&nbsp;&nbsp;**foreach** msg : setOfInferences[i] **do**
4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** isValidMessage(msg) **then**
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;remove msg.literal.val from dom(lmsg.literal.var)
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;add msg to setOfInferences(currentLevel)
7 &nbsp;&nbsp;&nbsp;&nbsp;clear setOfInferences[i]
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**//** removing the inferences stored at level i
8 **foreach** msg : msgQueue **do**
9 &nbsp;&nbsp;**if** isValidMessage(msg) **then**
10 &nbsp;&nbsp;&nbsp;&nbsp;remove msg.literal.val from dom(msg.literal.var)
11 &nbsp;&nbsp;&nbsp;&nbsp;add msg to setOfInferences(currentLevel)
12 &nbsp;&nbsp;remove msg

hasn't backtracked, it checks the new messages in Messages Queue. It, first,
verifies if the message is relevant. If it is the case, the literal is removed and the
inference is added to setOfInferences at the current level of search (Lines 5 and
6). If the message is no more relevant, it is removed from the Messages Queue
(Line 12).

4.3 Workers’ side

The **workers** use three main data structures:

4.3.1 The Assignments Stack

The workers obtain initially a copy $\mathcal{P}'$ of the problem instance $\mathcal{P}$ that is handled
by the master (variables, domains, constraints). In order to reach the same search
state as the master, the workers can either copy the new state of the problem or
get only the decision made so far and re-apply them. Since copying the new state
of the problem enables the workers to get only the new domains state and not the
constraints state (involving the handled supports for each constraint), we choose
in our approach to make an incremental copy. In fact, in a loop, they copy
incrementally the *Assignments Stack* of the master (i.e. the list of decisions
taken by the master), reproduce the filtering made by the master after these
decisions in order to reach the same state as the master and then run their own
(partial) consistency. The incremental copy of the *Assignments Stack* consists
in, first, identifying the part of the *Assignments Stack* which is identical in the
4.3. WORKERS' SIDE

master and in the worker's copy and then copying every decision taken by the master after this common part. It is performed in the following way. The worker first obtains the current stack pointer of the master and then identifies the last decision which has the same time-stamp in the master and in the worker. Then, the worker copies each decision of the master after this last common decision. Since the master may have backtracked in between, the worker then checks that the last decision that it copied still has the same time-stamp as in the master. If this is not the case, the master backtracked during the copy and the worker restarts its copy of the *Assignments Stack*. In practice, this does not happen too often (less than 1% of the total copies). Therefore, our approach guarantees that inconsistent copies are never used because when such a copy is obtained, the worker simply makes another one.

Figures 4.5 and 4.6 describe two cases of the copying process. In Figure 4.5, the master continued its solving process and, thus, there are new decisions to be copied in the worker's *Assignments Stack*. The last common positive decision between the master and the worker is $x_1 = a$. All decisions made after this one are added to the worker's stack.

<figure><img src="image_74.png" /><figcaption>Figure 4.5: Copying process (case 1: the same branch).</figcaption></figure>

In the case of Figure 4.6 the master has backtracked and started new other decisions. The worker has to remove all decisions until the common one. In fact, a backtrack on the variable $x_2$ has occurred and, thus, a negative decision is added to the first positive decision $x_1 = a$ (the last positive decision). The time-stamp of the decision $x_1 = a$ does not change when adding the refutation ($x_2 \neq c$). However, the worker has to update its stack in order to cope with these new facts. First of all, the worker removes the old decisions that are no more relevant. Then, its checks if there are new negative decisions of the last common
4.3. WORKERS' SIDE

positive decision ($x_1 = a$ in our case). This is done by comparing the number of
negative decisions of the last common positive decision. Finally, the worker adds
incrementally the decisions of the new levels (including refutations).

<figure><img src="image_75.png" /><figcaption>Figure 4.6: Copying process (case 2: backtracking).</figcaption></figure>

4.3.2 The Messages Queue

Once a worker has a stable copy of the master's state, it picks a new literal (x, a) from a global queue of literals (described in Section 4.3.3) and checks if (x, a) is SAC-consistent, i.e., if no domain wipe-out (global inconsistency) is detected when taking the decision x = a and running constraint propagation (we assume that GAC is achieved). If it is not, the worker places in the *Messages Queue* the data x ≠ a together with its current decision level and a time-stamp where this information could be inferred (as detailed in Section 4.2.2). The master will extract this information when it is ready to use it. After testing SAC on a literal (x, a), it is put back to the literals queue, while updating its priority (as described in Section 4.3.3), in order to test its consistency later.

Algorithm 36 describes the SAC enforcing on the set of literals of the queue. We just focus, in this section, on the message producing process. When a literal (variable,value) is SAC-inconsistent (the SAC test returns false), it means that removing this literal enables the master to avoid some useless search sub-tree and, thus, speeds up the solving process. The worker transmits this information to its master (Line 14). A message is then composed indicating the literal to avoid, on which level the SAC test is still relevant and the time-stamps to identify the last positive decision related to this test.
4.3. WORKERS' SIDE

<caption>**Algorithm 36:** `enforceConsistencyOnLiterals`($P_i$: Constraint Network of slave $i$, `LiteralsQueue`: Queue of literals)</caption>

1 &nbsp;&nbsp;&nbsp;&nbsp;valueFound &larr; false
2 &nbsp;&nbsp;&nbsp;&nbsp;**while** &not;&nbsp;valueFound **do**
3 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;literal &larr; getLiteral(literalsQueue)
4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** &not;&nbsp;assigned(literal.var) **and** |dom(literal.var)| &gt; 1 **then**
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;valueFound &larr; true
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;literal.countdown --
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;insert literal to literalsQueue

// while the problem is not solved, there is always a value to test
9 &nbsp;&nbsp;&nbsp;&nbsp;assign literal.val to literal.var
10 &nbsp;&nbsp;&nbsp;&nbsp;consistent &larr; GAC(P, literal.var)
11 &nbsp;&nbsp;&nbsp;&nbsp;backtrack()
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// going back to the previous level in order to test more pairs
13 &nbsp;&nbsp;&nbsp;&nbsp;**if** &not;&nbsp;consistent **then**
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;literal priority++
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;putMessage(currentLevel, timeStamp(level), literal)
16 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// Putting the inferred result in the queue of messages
17 &nbsp;&nbsp;&nbsp;&nbsp;literal.countdown --
18 &nbsp;&nbsp;&nbsp;&nbsp;insert literal to literalsQueue

4.3.3 The Literals Queue

In order to perform the SAC tests, the literals of the problem are put together
in a *Literals Queue*. The different workers cooperate to examine each possible
literal as often as possible. Since some literals are more likely to become SAC-
inconsistent, we use priorities in order to test these literals more often than the
other ones. Therefore, each literal in the *Literals Queue* is assigned a priority,
which is incremented when the literal is identified as SAC-inconsistent (Algo-
rithm 36 Line 13).

To manage this priority, we use the approach of the Completely Fair Schedul-
ing (CFS) algorithm [Li et al., 2009] used in Linux. The CFS scheduler ensures
executing the process that has used the least amount of time at the first place
and, thus, the processes are ordered according to the execution time spent. The
CFS uses a red-black tree data structure that is a balanced binary search tree
whose key is based on the value of the running time. According to red-black
tree property, tasks that have been given less processing time are on the left
4.3. WORKERS’ SIDE

side, whereas tasks that have been given more processing time are on the right
side. In Figure 4.7, node $N_7$ has the smallest value of running time and $N_{10}$ has
the largest value. CFS scheduler accords the highest priority to the node that
has the smallest running time value, and thus, left tasks are runned the first.
After picking a process, the CFS scheduler removes it from the tree, executes it
and updates its global execution time counter and then returns it back to the
tree taking into account its new execution time counter. One advantage of this
algorithm is that each value is tested as many times as its priority.

<figure><img src="image_76.png" /><figcaption>Figure 4.7: A red-black tree.</figcaption></figure>

In our approach a literal has two main properties:

* *countdown* counter: it indicates the number of times a literal could be tested. Each time we test a literal, we decrease its *countdown* counter (Line 15 in the Algorithm 36) to ensure a balanced test between all the literals of the queue. When all the literals are tested, the *countdown* is automatically reset for all the literals. Each time we reset the *Literals Queue*, the value *countdown* of each literal takes the value of its *priority*;

* *priority* counter: it indicates how interesting a literal is. If a SAC test proves the inconsistency of a literal, its *priority* counter is increased (Line 13 in the Algorithm 36) because such a literal is important to be tested in other branches of the search tree and may infer important information to be exploited by the master. The *priority* counter is initialized to 1 when the workers start their jobs: the literals have the same importance at the root of the search tree.

Since the *Literals Queue* is managed according to the CFS algorithm, in order
to perform the SAC tests we first get a literal and remove it from the queue.
Then, we check if the variable is already assigned or is a singleton variable. If it
## 4.4 ENHANCING THE SEARCH PROCESS

is the case, it is useless to enforce SAC on this literal and we put back the literal in the end of the queue (by updating its priority). Otherwise, we perform the test.

## 4.4 Enhancing the search process

Algorithm 37 describes the search algorithm used by the master. In fact, we use the classic MAC search algorithm. Added to that, we include extracting messages step (Line 4): a call to Algorithm 35 is made in order to benefit from the facts discovered by workers. In this way, the SAC-inconsistent values are removed from their respective domains which enables to avoid them (Line 6).

<table><caption>**Algorithm 37:** solveProblem(*P*: Constraint network)</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>finished ← false</td></tr><tr><td>2</td><td>hasBacktracked ← false</td></tr><tr><td>3</td><td>while ¬finished do</td></tr><tr><td>4</td><td>applyMessages(<i>hasBacktracked</i>)</td></tr><tr><td>5</td><td>// select new pair (<i>variable</i>,<i>value</i>) to assign</td></tr><tr><td>6</td><td><i>var</i> ← getNextVariable(<i>variableOrderingHeuristic</i>)</td></tr><tr><td>7</td><td><i>val</i> ← getNextValue(<i>valueOrderingHeuristic</i>, <i>var</i>)</td></tr><tr><td>8</td><td>assign <i>var</i> to <i>val</i></td></tr><tr><td>9</td><td><i>levelBeforeBacktrack</i> ← |<i>past</i>(<i>P</i>)|</td></tr><tr><td>10</td><td><i>consistent</i> ← checkConsistencyAfterAssignment(<i>P</i>)</td></tr><tr><td>11</td><td><b>if</b> <i>consistent and</i> |<i>past</i>(<i>P</i>)| = <i>n</i> <b>then</b></td></tr><tr><td>12</td><td>display <i>solution</i></td></tr><tr><td>13</td><td><b>else</b></td></tr><tr><td>14</td><td>while ¬<i>consistent</i> do</td></tr><tr><td>15</td><td>backtrack()</td></tr><tr><td>16</td><td><i>hasBacktracked</i> ← true</td></tr><tr><td>17</td><td>remove <i>val</i> from <i>dom</i>(<i>var</i>)</td></tr><tr><td>18</td><td><i>consistent</i> ← checkConsistencyAfterRefutation(<i>P</i>)</td></tr></tbody></table>

Using the introduced data structures, Figure 4.8 illustrates our architecture. On this example, the master has taken three decisions so far. The first decision *x* = *a* has time-stamp 1. Then, the master tried *y* = *c* at time-stamp 2, but immediately obtained an inconsistency. Therefore, it removes this decision and adds the negative decision *y* ≠ *c* to the previous positive decision. The latest decision is *y* = *a* at time-stamp 3. *Worker*<sub>1</sub> has copied the master's stack at
4.4. ENHANCING THE SEARCH PROCESS

<figure><img src="image_77.png" /><figcaption>Figure 4.8: Illustration of the architecture.</figcaption></figure>
## 4.5. EXPERIMENTAL RESULTS

this point, while *Worker*₂ has copied the stack at an earlier point where the decision *y* = *c* was taken. Each worker picks a literal from a global list of literals that should be tested. *Worker*₂ picks the literal (*w*, *c*) and detects that is SAC-inconsistent. A message *m*₁ indicating that *w* ≠ *c* can be inferred at decision level 2 (with time-stamp 2) is posted. *Worker*₁ tests (*z*, *a*) and proves that it is inconsistent with the previous assignments. Therefore, it posts a message *m*₂ indicating that *z* ≠ *a* can be inferred at decision level 2 (with time-stamp 3).

The master finds out, when extracting messages, that *m*₁ is outdated since it has backtracked since *Worker*₂ has copied the *Assignments Stack*. The message *m*₁ is then removed. The message *m*₂ is relevant with respect to the problem state of the master. This latter can benefit from this information until it changes its decision at level 2.

## 4.5 Experimental results

In order to test the practical interest of the approach we propose, we have conducted a preliminary experimentation (with our solver AbsCon) using a cluster of bi-quad cores Xeon processors at 2.66 GHz node with 16GiB of RAM under Linux. We have used the search algorithm MAC (which maintains the property of generalized arc consistency during search), equipped with *dom/ddeg* [Bessiere and Régin, 1996] and *dom/wdeg* [Boussemart et al., 2004] as variable ordering heuristic and *lexico* as value ordering heuristic, to solve instances of different problems<fnref n="1" />.

We have compared the wall-clock time (wck) in second(s), CPU time (cpu) in second(s) and the number of nodes (#nodes) for both classical sequential approaches and the parallel ones. For the sequential approaches, we have used MAC, SAC+MAC where SAC is enforced only at preprocessing, and MSAC that enforces SAC during the search (at each node). For the parallel approach, we have used 1, 3 and 7 workers (and of course, one master). The number of total messages (#tMsgs) and useful ones (#uMsgs) sent from the workers to the master is displayed. The speed-up ratio of resolution time compared to MAC is also calculated as follows:

$$ \frac{\text{MAC wck time}}{\text{parallel wck time}} \qquad (4.1) $$

A time-out of 1,800 seconds was set per instance; when the instance cannot be solved within this limit, TO is indicated in the table. In our tests, we suppose that CPU resources are available (for free). Under this assumption, we just focused on *wck time* rather than *CPU time*

Table 4.1 describes the results obtained when using the heuristic *dom/wdeg* on some selected instances. Obviously, our approach does not overweight the

<footnote n="1">¹available at http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html</footnote>
## 4.5. EXPERIMENTAL RESULTS

classical MAC solver, but it gives better resolution times (in wall-clock) than the other sequential approaches (SAC+MAC, MSAC).

<table><caption>Table 4.1: Results for the sequential and parallel approaches for solving a few selected instances with dom/wdeg.</caption><thead><tr><th>Instance</th><th></th><th>#nodes</th><th>wck time</th><th>cpu time</th><th>#tMsgs</th><th>#uMsgs</th><th>Speedup</th></tr></thead><tbody><tr><td rowspan="6">cc-10-10-2</td><td>MAC</td><td>3,411</td><td><strong>1.188</strong></td><td>1.375</td><td></td><td></td><td>ratio</td></tr><tr><td>SAC+MAC</td><td>3,411</td><td>1.211</td><td>1.414</td><td></td><td></td><td></td></tr><tr><td>MSAC</td><td><strong>367</strong></td><td>2.997</td><td>3.199</td><td></td><td></td><td></td></tr><tr><td>Par(7)</td><td>3138</td><td>4.913</td><td>18.559</td><td>4,123</td><td>332</td><td>0.28</td></tr><tr><td>Par(3)</td><td>3129</td><td>2.510</td><td>10.226</td><td>2,854</td><td>92</td><td>0.50</td></tr><tr><td>Par(1)</td><td>3730</td><td>1.448</td><td>4.18</td><td>920</td><td>24</td><td>0.82</td></tr><tr><td rowspan="6">cw-ogd-vg12-15</td><td>MAC</td><td>5,309</td><td><strong>81.047</strong></td><td>80.943</td><td></td><td></td><td></td></tr><tr><td>SAC+MAC</td><td>3,723</td><td>446.735</td><td>445.572</td><td></td><td></td><td></td></tr><tr><td>MSAC</td><td></td><td style="background-color: #808080;"></td><td style="background-color: #808080;"></td><td></td><td></td><td></td></tr><tr><td>Par(7)</td><td>5,824</td><td>346.884</td><td>2255.207</td><td>11,956</td><td>2,092</td><td>0.23</td></tr><tr><td>Par(3)</td><td>5,072</td><td>162.165</td><td>746.163</td><td>6,264</td><td>850</td><td>0.50</td></tr><tr><td>Par(1)</td><td><strong>5,008</strong></td><td>134.122</td><td>247.401</td><td>1,878</td><td>90</td><td>0.60</td></tr><tr><td rowspan="6">langford-3-13</td><td>MAC</td><td>891,850</td><td><strong>30.449</strong></td><td>30.353</td><td></td><td></td><td></td></tr><tr><td>SAC+MAC</td><td>891,850</td><td>31.181</td><td>31.339</td><td></td><td></td><td></td></tr><tr><td>MSAC</td><td></td><td style="background-color: #808080;"></td><td style="background-color: #808080;"></td><td></td><td></td><td></td></tr><tr><td>Par(7)</td><td><strong>864,631</strong></td><td>57.564</td><td>231.143</td><td>1,102,392</td><td>36,544</td><td>0.53</td></tr><tr><td>Par(3)</td><td>884,835</td><td>34.483</td><td>140.035</td><td>84,7136</td><td>16,079</td><td>0.88</td></tr><tr><td>Par(1)</td><td>880,091</td><td>32.523</td><td>68.443</td><td>356,678</td><td>5,071</td><td>0.94</td></tr><tr><td rowspan="6">queen-12-12-14</td><td>MAC</td><td>660,504</td><td><strong>17.753</strong></td><td>17.825</td><td></td><td></td><td></td></tr><tr><td>SAC+MAC</td><td>660,504</td><td>18.334</td><td>18.25</td><td></td><td></td><td></td></tr><tr><td>MSAC</td><td><strong>18,651</strong></td><td>200.428</td><td>199.81</td><td></td><td></td><td></td></tr><tr><td>Par(7)</td><td>664,789</td><td>41.884</td><td>123.137</td><td>574,521</td><td>41,555</td><td>0.42</td></tr><tr><td>Par(3)</td><td>693,670</td><td>23.371</td><td>77.039</td><td>420,752</td><td>16,996</td><td>0.76</td></tr><tr><td>Par(1)</td><td>742,988</td><td>18.748</td><td>39.429</td><td>224,975</td><td>6,723</td><td>0.70</td></tr><tr><td rowspan="6">qK-12-5-mul</td><td>MAC</td><td>5,573</td><td>0.993</td><td>0.944</td><td></td><td></td><td></td></tr><tr><td>SAC+MAC</td><td><strong>0</strong></td><td>0.426</td><td>0.633</td><td></td><td></td><td></td></tr><tr><td>MSAC</td><td><strong>0</strong></td><td><strong>0.418</strong></td><td>0.639</td><td></td><td></td><td></td></tr><tr><td>Par(7)</td><td>10,594</td><td>3.821</td><td>12.026</td><td>31,455</td><td>2,917</td><td>0.72</td></tr><tr><td>Par(3)</td><td>6,299</td><td>1.410</td><td>5.309</td><td>30,601</td><td>2,886</td><td>1.11</td></tr><tr><td>Par(1)</td><td>7,938</td><td>3.856</td><td>2.959</td><td>5,818</td><td>5,015</td><td>0.44</td></tr></tbody></table>

Table 4.2 describes the average wall-clock time for several series of instances. Times are mentioned for a classical MAC solver, MSAC, SAC+MAC and also our parallel approach using 7 workers. The wck-time of instances that reach time-out is penalized by 1,800 * 3 seconds. On the 8 series of instances, our approach has the best average wall-clock time on only 2 series. The classical MAC solver is the best solver when using dom/wdeg heuristic compared to our
## 4.5. EXPERIMENTAL RESULTS

parallel approach.

<table><caption>Table 4.2: The average wall clock time for series of instances with dom/wdeg.</caption><thead><tr><th>Series</th><th>#inst</th><th>MAC</th><th>MSAC</th><th>SAC+MAC</th><th>Par(7)</th></tr></thead><tbody><tr><td>langford</td><td>17</td><td><strong>90.55</strong></td><td>905.32</td><td>391.14</td><td>408.16</td></tr><tr><td>queen</td><td>7</td><td>785.85</td><td>4143</td><td>2382</td><td><strong>235.42</strong></td></tr><tr><td>quennsKnight</td><td>22</td><td>1473</td><td><strong>162.39</strong></td><td>165.97</td><td>1264</td></tr><tr><td>rand-8-20-5-18-800</td><td>10</td><td><strong>45.91</strong></td><td>517.68</td><td>1124</td><td>93.20</td></tr><tr><td>fapp25-2230</td><td>12</td><td>46.95</td><td>620.83</td><td>48.80</td><td><strong>41.93</strong></td></tr><tr><td>ewddr2-10-by-5</td><td>10</td><td><strong>1.545</strong></td><td>6.589</td><td>2.336</td><td>3.026</td></tr><tr><td>cc</td><td>13</td><td><strong>2.772</strong></td><td>19.62</td><td>2.837</td><td>13.46</td></tr><tr><td>BlackHole-4-4-e</td><td>10</td><td><strong>0.458</strong></td><td>7.858</td><td>0.485</td><td>1.110</td></tr></tbody></table>

Disappointed by these results, we used dom/ddeg to compare our parallel approach with the sequential ones. This variable ordering heuristic guarantees that the different approaches have the same search path, which could by the reason behind the failure of our approach using dom/wdeg. Results are given in Table 4.3.

Compared with a classical solver using MAC, the interest of using a parallel approach is visible on these five instances:

* For some instances (cw-ogd-vg12-15, langford-3-13 and qk-12-5-mul), the number of visited nodes is highly decreased;

* For some instances (cc-10-10-2 and qk-12-5-mul), the wall clock time is decreased.

One interest of our approach is that SAC tests are interleaved with search, which means that we do not have to wait for the completion of the preprocessing to start the actual search, and still, we benefit from the discovery of inconsistent literals. In a sense, we use a kind of *anytime* version of SAC.

We investigate the efficiency of used messages on the speed-up obtained when using our parallel approach compared to the classical MAC solver. For the Crossword instance (cw-ogd-vg12-15), the inferences made by the workers are too limited for being useful compared with a MAC solver. Even though, using a parallel approach remains interesting compared to SAC+MAC or MSAC in term of wall clock time. On this instance, it appears that, for SAC+MAC, the most of CPU time (404 seconds) is spent at preprocessing. This explains why MSAC is
## 4.5. EXPERIMENTAL RESULTS

<table><caption>Table 4.3: Results for the sequential and parallel approaches for solving a few selected instances with dom/ddeg.</caption><thead><tr><th>Instance</th><th>#nodes</th><th>wck time</th><th>cpu time</th><th>#tMsgs</th><th>#uMsgs</th><th>Speedup ratio</th></tr></thead><tbody><tr><td rowspan="5">cc-10-10-2</td><td>MAC</td><td>542,776</td><td>47.90</td><td>47.479</td><td></td><td></td><td></td></tr><tr><td>SAC+MAC</td><td>542,776</td><td>48.23</td><td>47.946</td><td></td><td></td><td></td></tr><tr><td>MSAC</td><td><strong>4960</strong></td><td>49.10</td><td>48.73</td><td></td><td></td><td></td></tr><tr><td>Par(7)</td><td>73,684</td><td>114.889</td><td>456.136</td><td>46,111</td><td>23,979</td><td>2.3</td></tr><tr><td>Par(3)</td><td>139,351</td><td><strong>19.49</strong></td><td>154.4</td><td>160.77</td><td>22,240</td><td>2.46</td></tr><tr><td rowspan="5">cw-ogd-vg12-15</td><td>MAC</td><td>4,224</td><td><strong>70.71</strong></td><td>70.528</td><td></td><td></td><td></td></tr><tr><td>SAC+MAC</td><td>4,648</td><td>545.48</td><td>543.951</td><td></td><td></td><td></td></tr><tr><td>MSAC</td><td></td><td><strong>TO</strong></td><td></td><td></td><td></td><td></td></tr><tr><td>Par(7)</td><td><strong>4116</strong></td><td>231.988</td><td>1590.632</td><td>6,469</td><td>412</td><td>0.292</td></tr><tr><td>Par(3)</td><td>4241</td><td>125.783</td><td>616.308</td><td>3,361</td><td>158</td><td>0.536</td></tr><tr><td rowspan="5">langford-3-13</td><td>MAC</td><td>764,944</td><td>29.14</td><td>29.148</td><td></td><td></td><td></td></tr><tr><td>SAC+MAC</td><td>764,944</td><td><strong>28.53</strong></td><td>28.689</td><td></td><td></td><td></td></tr><tr><td>MSAC</td><td></td><td><strong>TO</strong></td><td></td><td></td><td></td><td></td></tr><tr><td>Par(7)</td><td><strong>750,105</strong></td><td>47.01</td><td>195.52</td><td>10,617,44</td><td>33,987</td><td>0.620</td></tr><tr><td>Par(3)</td><td>759,166</td><td>30.46</td><td>116.039</td><td>822,626</td><td>15,073</td><td>0.957</td></tr><tr><td rowspan="5">queen-12-12-14</td><td>MAC</td><td>2,211,140</td><td><strong>64.12</strong></td><td>64.123</td><td></td><td></td><td></td></tr><tr><td>SAC+MAC</td><td>2,211,140</td><td>65.650</td><td>65.427</td><td></td><td></td><td></td></tr><tr><td>MSAC</td><td><strong>61,179</strong></td><td>170.87</td><td>468.701</td><td></td><td></td><td></td></tr><tr><td>Par(7)</td><td>2,000,032</td><td>97.09</td><td>512.836</td><td>2,297,683</td><td>164,826</td><td>0.660</td></tr><tr><td>Par(3)</td><td>2,083,863</td><td>68.49</td><td>265.991</td><td>1,739,529</td><td>110,223</td><td>0.936</td></tr><tr><td rowspan="5">qK-12-5-mul</td><td>MAC</td><td>2,017,288</td><td>44.88</td><td>44.937</td><td></td><td></td><td></td></tr><tr><td>SAC+MAC</td><td></td><td><strong>0</strong></td><td>0.438</td><td>0.629</td><td></td><td></td></tr><tr><td>MSAC</td><td><strong>0</strong></td><td><strong>0.401</strong></td><td>0.629</td><td></td><td></td><td></td></tr><tr><td>Par(7)</td><td>1,647,766</td><td>87.391</td><td>533.816</td><td>10,505,678</td><td>1,778,671</td><td>0.513</td></tr><tr><td>Par(3)</td><td>1,838,425</td><td>70.161</td><td>272.171</td><td>5,535,294</td><td>857,197</td><td>0.640</td></tr><tr><td></td><td>Par(1)</td><td>1,928,055</td><td>59.009</td><td>115.684</td><td>1,880,410</td><td>365,341</td><td>0.760</td></tr></tbody></table>

not able to solve the problem in 1,800 seconds. For the Chessboard Coloration instance (cc-10-10-2), the parallel approach achieves the best wall clock time with an average of messages number around 20,000. For the Langford and Queen instances, the number of messages is greater than the Chessboard Coloration instance. However, this does not imply in anyway that the parallel approach is quicker. To conclude, analyzing these results shows clearly that the speed-up obtained is not correlated with to the number of used messages when using our parallel approach compared to the classical MAC solver. Instances can use an
## 4.5. EXPERIMENTAL RESULTS

important number of messages but not reduce their search tree and, contrary to that, other instances could benefit from a few number of messages to reduce significantly their search tree.

<table><caption>Table 4.4: The average wall clock time for series of instances with dom/ddeg.</caption><thead><tr><th>Series</th><th>#inst</th><th>MAC</th><th>MSAC</th><th>SAC+MAC</th><th>Par(7)</th></tr></thead><tbody><tr><td>langford</td><td>17</td><td>77.828</td><td>830,090</td><td><strong>76.995</strong></td><td>397.311</td></tr><tr><td>queen</td><td>7</td><td>845.799</td><td>4,659.207</td><td>24,443.690</td><td><strong>319.756</strong></td></tr><tr><td>queensKnight</td><td>22</td><td>3,446.051</td><td><strong>160.044</strong></td><td>166.904</td><td>1,475.197</td></tr><tr><td>rand-8-20-5-18-800</td><td>10</td><td><strong>20.221</strong></td><td>204.801</td><td>22.192</td><td>34.837</td></tr><tr><td>fapp25-2230</td><td>12</td><td>46.246</td><td>619.829</td><td>49.241</td><td><strong>43.191</strong></td></tr><tr><td>ewddr2-10-by-5</td><td>10</td><td><strong>1.518</strong></td><td>6.888</td><td>2.362</td><td>3.046</td></tr><tr><td>cc</td><td>10</td><td>53.004</td><td>67.663</td><td>54.017</td><td><strong>13.422</strong></td></tr><tr><td>BlackHole-4-4-e</td><td>10</td><td><strong>0.493</strong></td><td>11.354</td><td>0.498</td><td>1.156</td></tr></tbody></table>

Table 4.4 describes the average wall-clock time for several series of instances. Times are mentioned for a classical MAC solver, MSAC, SAC+MAC and also our parallel approach using 7 workers. The wck-time of instances that reach time-out is penalized by 1,800 * 3 seconds. Our parallel approach has the best solving wall-clock time on 3 series out of 8 which outweigh the results obtained with MSAC and SAC+MAC. However, we have been disappointed in not reducing significantly the solving time compared to a MAC solver. In fact, using such a strong consistency is supposed to infer important information that can be used by a classical solver to reduce its search tree.

In order to understand the reasons behind the fruitless results (compared to MAC) of our approach, we decide to make more experiments. On the one hand, we used an oracle of inferences: we wanted to know what we would get if the SAC tests were costless (*costlessMSAC*). To do that, we stored the inferences made when maintaining classical SAC during search (MSAC). We then use the previous stored inferences (oracle of inferences) while maintaining arc consistency (MAC). We get, thus, the best case times of maintaining SAC during search. On the other hand, we compared *costlessMSAC* with a classical MAC solver and estimated the speed-up ratio as follows:

$$ \frac{\text{MAC wck time}}{\text{costlessMSAC wck time}} \qquad (4.2) $$

Figure 4.9 describes the distribution of 876 instances of several problems according to the speed-up ratio. In fact, only 3% of the instances of the conducted
## 4.5. EXPERIMENTAL RESULTS

experimentation have a speed-up ratio greater than 10. Whereas, the other 94% of the instances have a speed-up ratio less than 2. In this case, it is difficult to overweight the costs of maintaining SAC in parallel. This leads us to assume that maintaining SAC during search is not as effective as supposed in reducing the search tree.

<figure><img src="image_78.png" /><figcaption>Figure 4.9: Pie chart of instances according to the speed-up ratio.</figcaption></figure>

Table 4.5 describes the results of some selected instances of the previous experimentation: comparing MAC to costlessMSAC. These instances are presented in an increasing order of their speed-up. Obviously, the difficulty of instance resolution does not affect the obtained speed-up ratio. For example, the *langford-3-14* instance is more difficult than *val10-43*, whereas the speedup ratio for *langford-3-14* is significantly less than *val10-43*.

Figure 4.10(a) describes the number of effective SAC tests per level that contribute to the reduction of the search tree and, thus, helping the solver during its solving process. These results are more detailed in Table 4.6. In fact, we chose instances composed of the same number of variables (100 variables) and all variables have the same domain size of 46. However, these instances have different speed-up. Obviously, the *primes-15-60-2-7* instance which has the greatest speed-up ratio, has also the greatest number of effective SAC tests during the 32 first levels. This number reaches 2740 tests for the level 32. For the other instances, the greatest number of effective SAC tests are mostly during pre-processing whereas the remaining SAC tests are distributed during the search in few amounts. Obviously, some instances for which maintaining *costlessSAC* is efficient use a large number of SAC tests in order to reduce the search space.
## 4.5. EXPERIMENTAL RESULTS

<figure><img src="image_79.png" /><figcaption>Figure 4.10: Comparison between costlessMSAC and MAC for some selected instances of the *primes* problem using dom/ddeg.</figcaption></figure>
## 4.5. EXPERIMENTAL RESULTS

<table><caption>Table 4.5: The wall clock time (in seconds) for some selected instances with costlessMSAC and MAC (dom/ddeg).</caption><thead><tr><th>Instance</th><th>costlessMSAC</th><th>MAC</th><th>speed-up ratio</th></tr></thead><tbody><tr><td>2-fullins-5-4</td><td>11.44</td><td>13.683</td><td>1.196</td></tr><tr><td>langford-3-14</td><td>93.257</td><td>229.071</td><td>2.456</td></tr><tr><td>crossword-m1c-lex-vg6-7</td><td>16.527</td><td>51.253</td><td>3.101</td></tr><tr><td>bdd-21-133-18-78-11</td><td>2.427</td><td>12.224</td><td>5.037</td></tr><tr><td>rand-8-20-5-18-800-13</td><td>3.857</td><td>51.407</td><td>13.328</td></tr><tr><td>cc-10-10-2</td><td>3.088</td><td>75.784</td><td>24.541</td></tr><tr><td>half-n25-d5-e56-r7-1</td><td>4.703</td><td>198.238</td><td>42.151</td></tr><tr><td>primes-10-20-2-5</td><td>1.202</td><td>51.973</td><td>43.239</td></tr><tr><td>val10-43</td><td>0.772</td><td>43.983</td><td>56.973</td></tr></tbody></table>

Figure 4.11(a) describes two instances with different speed-up ratio (wck-time and speed-up are detailed in 4.11(b)). These results show, clearly, that the previous assumption is not always true. In fact, *haystacks-06* instance benefits from the greatest number of SAC tests during search reaching almost 45000 tests in its 13th level but does not reach an important speed-up compared to MAC. However, *val10-43* instance reaches a speed-up of almost 57 compared to MAC benefiting from a few amount of SAC tests at pre-processing and its first level.

Furthermore, using a high number of SAC tests at the first level of the search tree does not guarantee a high speed-up which the case for *primes-15-20-2-3* and *primes-15-20-3-1* instances (Figure 4.10(a)) compared to *val10-43* instance.

<table><caption>Table 4.6: Comparison between costlessMSAC and MAC for some selected instances of the *primes* problem dom/ddeg: the wall clock time (in seconds) and the speed-up ratio.</caption><thead><tr><th>Instance</th><th>costlessMSAC</th><th>MAC</th><th>Speed-up ratio</th></tr></thead><tbody><tr><td>primes-15-60-2-7</td><td>1.194</td><td>37.384</td><td>31.310</td></tr><tr><td>primes-15-20-3-5</td><td>0.875</td><td>15.833</td><td>18.095</td></tr><tr><td>primes-15-20-2-3</td><td>0.756</td><td>1.254</td><td>1.659</td></tr><tr><td>primes-15-20-3-1</td><td>0.596</td><td>0.903</td><td>1.515</td></tr></tbody></table>
## 4.5. EXPERIMENTAL RESULTS

<figure><img src="image_80.png" /></figure>

<table><caption>(b) The wall-clock time and the speed-up ratio.</caption><thead><tr><td>Instance</td><td>costlessMSAC</td><td>MAC</td><td>speed-up ratio</td></tr></thead><tbody><tr><td>haystacks-06</td><td>0.88</td><td>1.43</td><td>1,625</td></tr><tr><td>val10-43</td><td>0.772</td><td>43.983</td><td>56.973</td></tr></tbody></table>

Figure 4.11: Comparison between costlessMSAC and MAC for two instances of different speed-up ratio.

We have been disappointed by the inability of our approach, and in particular the singleton arc consistency, to reduce significantly the search tree for most of the experimented instances. This is why we tried to maintain a stronger consistency: weak-k-SAC. We conducted an experimentation over more than 360 different instances. Unfortunately, weak-k-SAC failed to prune an important search space during search, and thus, maintaining it during search does not seem to be effective in the resolution of the different instances. Table 4.7 describes the results obtained for some selected instances when establishing weak-k-SAC (presented in a decreasing order of speed-up ratio)
## 4.5. EXPERIMENTAL RESULTS

<table><caption>Table 4.7: The wall clock time (in seconds) for some selected instances with costlessMWeak-1-SAC and MAC (dom/ddeg) establishing weak-1-SAC.</caption><thead><tr><th>Instance</th><th>(#nbVar, #nbVal)</th><th>#costlessMWeak-1-SAC</th><th>MAC</th><th>speed-up ratio</th></tr></thead><tbody><tr><td>val7-12</td><td>(20, 960)</td><td>0.133</td><td>294.59</td><td>2215</td></tr><tr><td>val16-27</td><td>(53, 4,558)</td><td>0.318</td><td>422.25</td><td>1328</td></tr><tr><td>val45-50</td><td>(128, 16,384)</td><td>0.412</td><td>57.63</td><td>139.88</td></tr><tr><td>val46-50</td><td>(128, 16,384)</td><td>0.473</td><td>46.65</td><td>98.63</td></tr><tr><td>val47-50</td><td>(128, 16,384)</td><td>1.504</td><td>46.82</td><td>31.13</td></tr><tr><td>val7-27</td><td>(20, 1,720)</td><td>0.127</td><td>2.831</td><td>22.29</td></tr><tr><td>val24-41</td><td>(75, 9,600)</td><td>0.331</td><td>5.676</td><td>17.15</td></tr><tr><td>val44-50</td><td>(128, 16,384)</td><td>4.783</td><td>55.24</td><td>11.55</td></tr><tr><td>E-12</td><td>(270, 81,000)</td><td>25.80</td><td>181.17</td><td>7.02</td></tr><tr><td>val18-39</td><td>(64, 7,744)</td><td>1.919</td><td>9.819</td><td>5.12</td></tr><tr><td>val12-29</td><td>(48, 4,800)</td><td>0.319</td><td>0.959</td><td>3</td></tr><tr><td>val35-43</td><td>(120, 15,360)</td><td>0.614</td><td>1.319</td><td>2.15</td></tr><tr><td>lei450-15c-05</td><td>(450, 2,250)</td><td>1.444</td><td>1.769</td><td>1.22</td></tr><tr><td>ash958GPIA-3</td><td>(1,916, 5,748)</td><td>1.684</td><td>1.565</td><td>0.929</td></tr><tr><td>F-10</td><td>(270, 81,000)</td><td>13.144</td><td>2.654</td><td>0.201</td></tr></tbody></table>

## Conclusion

In this chapter, we introduced a new approach using a parallel architecture in order to enhance the classical solving process. Several workers establish a partial consistency (SAC/ weak-k-SAC) and send the discovered facts to the master in order to avoid useless search space. Contrary to our expectations, our approach seems to be less effective than MAC (the most used search algorithm). This could be due to the fact that the discovered SAC-inconsistent values are, in fact, easily removed by the master by propagation. This implies that the sent information is not as strong as expected to speed-up the master search. The choice of the variable ordering heuristic could be also the reason behind the failure of our approach.
# Chapter 5

# Conclusions and Future Work

The work presented can be divided into two main parts:

**Compressing Table Constraints** In the first part, we deal with the most used kind of constraints which are table constraints. Since table constraints offer expressiveness to non-expert users, its use is widespread in the industrial world. Over time, the represented data keeps growing which implies the use of compact data-structures to store them, in a first place, and optimized filtering algorithms to manage them during the solving process, in a second place. In the last decades, several techniques proposed compact ways to represent table constraints while using the minimal storage space, and mostly, not penalizing their use during the search. We present some techniques of the state-of-the-art in the first section of Chapter 2. In our turn, we propose two different methods of compressing table constraints. Both of them are based on frequent patterns search in order to avoid redundancy. However, the manner of defining pattern, the patterns-detecting process and the new compact representation differs significantly. In fact, in the first method *STR*<sup>c</sup>, we use the “trie” data structure in order to find patterns which are defined as a sequence of values. After detecting the most frequent patterns, we build a patterns table in which the most frequent patterns are stored. The new form of the table constraint replaces all occurrences of the patterns by a reference to them in the patterns table. In this way, we could benefit from avoiding these redundancies at two levels. At the space complexity level, the use of references enables us to reduce the space required to represent table constraints avoiding repeating the same sequences of values. At the time complexity level, using references to patterns enables us to avoid redundant validity checks. Rather than testing the validity of the same sequence several times in a pass of the table constraints, the test is done only one time and simply re-used for every occurrence. In order to manage the new compressed form of table constraint, we use an adapted variant of STR taking into consideration the use of patterns. The experimental results shows that our ap-
proach achieves a high compression, but compared to STR variants it competes
only with *STR1*. The choice of the manner of defining patterns are the reasons
behind the non-competitiveness of our results. In fact, since in our approach
*STR*<sup>c</sup> we consider that a pattern is a sequence of values, we are not able to use a
filtering algorithm based on the optimized variants of STR (*STR2* and *STR3*).
We take into account this drawback in our second approach *STR-slice*, where
we defined patterns in another way (as pairs of a *variable* and a *value*). The
frequent patterns detection is done, this time, using a data-mining algorithm.
The new form of table constraint is, in fact, composed of “slices” of sub-tables.
The original constraint table is fragmented based on the frequent patterns. Each
“slice” is, then composed of a frequent pattern and the remaining part of the ta-
ble where the pattern, originally, appears. The experimental results shows, this
time, more competitive results where *STR-slice* supplants *STR2* and, sometimes
*STR3* even if it is penalized by the compression process.

Generally speaking, each of the proposed approaches has its specificity and
the experimental results depends mostly on the constraints representation. The
main issue that all the proposed approaches of the-state-of-the-art have to find
an answer is how to find a compromise between achieving a high compression
ratio and filtering as effective as possible the new compact data structure.

**Future Work** First of all, we think that the tuning of the parameters used for guiding compression should be automatized (possibly, employing some machine learning techniques). *STR*<sup>c</sup> and *STR-slice* could then benefit from a better compression which depends on the nature of class of problem instance. Second, we believe that, in the rising context of big data, new constraint problems should emerge rapidly where constraints could be of (very) large arity and involve very large tables. *STR-slice* could advantageously handle such “huge” constraints, especially if we consider that slicing could be conducted recursively on the sub-tables which is another perspective of this thesis work. Finally, we think that the concept of sliced table constraints is interesting on its own for modeling, as certain forms of conditionality can be represented in a simple and natural way, directly with sliced table constraints.

**Using Singleton Arc Consistency in parallel to improve search** The second part is dedicated to another way to optimize CSP solving which is the use of a parallel architecture. The advancements of the parallel computing field has encouraged the CSP community, among others, to benefit from the computers power in order to solver larger problems. Several approaches are proposed in which the problem is distributed over workers or a copy of the problem is used for each of them. Some methods of the state-of-the-art of parallel computing and also parallel CSP solving are introduced in the second section of Chapter 2. All these methods tried to speed-up the solving time. We propose a method in
Chapter 4 where we use a parallel architecture in order to enhance the solving process by establishing parallel consistencies. In fact, different workers sent to their master the result of establishing partial consistencies as new discovered facts. The master, in its turns tries to benefit from them by removing the values leading to a failure. Contrary to our expectation, the work made by the workers does not imply a significant improvement of the solving process. In fact, an in-depth analysis shows that even in a sequential resolution enforcing such strong consistencies for free cannot imply an important reduction in the search space which makes the results obtained through our approach understandable.

**Future Work** A natural perspective of our work is to incorporate other forms of consistencies that could impact larger the neighborhood, and thus, reduce significantly the search space. We may consider “wise” messages that include many forms of consistencies which can together form a form of explanation that avoid a master to use a given path or given sequence of assignments. Moreover, we could investigate the impact of heuristics on the effectiveness of the received messages. Choosing a variable of the neighborhood may imply more deductions.
Bibliography

[Agrawal et al., 1993] Agrawal, R., Imieli'nski, T., and Swami, A. (1993). Min-
ing association rules between sets of items in large databases. In *Proceedings of SIGMOD'93*, pages 207-216.

[Agrawal and Srikant, 1994] Agrawal, R. and Srikant, R. (1994). Fast algorithms for mining association rules in large databases. In *Proceedings of ICVLDB'94*, pages 487-499.

[Amadini et al., 2015] Amadini, R., Gabbrielli, M., and Mauro, J. (2015). Sunny-cp: a sequential cp portfolio solver. In *Proceedings of SAC'15*, pages 1861-1867.

[Amdahl, 1967] Amdahl, G. (1967). Validity of the single processor approach to achieving large scale computing capabilities. In *Proceedings of ACM'67*, pages 483-485.

[Appel and Haken, 1977] Appel, K. and Haken, W. (1977). Every planar map is four colorable. Part I: Discharging. *Illinois Journal of Mathematics*, 21(3):429–490.

[Bartak and Erben, 2004] Bartak, R. and Erben, R. (2004). A new algorithm for singleton arc consistency. In *Proceedings of FLAIRS'04*, pages 257–262.

[Benson et al., 1992] Benson, J., Brent, W., and Freuder, E. (1992). Interchangeability preprocessing can improve forward checking search. In *Proceedings of ECAI'92*, pages 28–30.

[Bessiere, 1994] Bessiere, C. (1994). Arc consistency and arc consistency again. *Artificial Intelligence*, 65:179–190.

[Bessiere, 2006] Bessiere, C. (2006). Constraint propagation. In *Handbook of Constraint Programming*, chapter 3, pages 29–83. Elsevier.

[Bessiere and Debruyne, 2004] Bessiere, C. and Debruyne, R. (2004). Optimal and suboptimal singleton arc consistency algorithms. In *Proceedings of CP'04*, pages 17–27.
BIBLIOGRAPHY

[Bessiere and Debruyne, 2005] Bessiere, C. and Debruyne, R. (2005). Optimal and suboptimal singleton arc consistency algorithms. In *Proceedings of IJCAI'05*, pages 54–59.

[Bessiere et al., 1999] Bessiere, C., Freuder, E., and Régin, J. (1999). Using constraint metaknowledge to reduce arc consistency computation. *Artificial Intelligence*, 107:125–148.

[Bessiere and Régin, 1996] Bessiere, C. and Régin, J. (1996). MAC and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems. In *Proceedings of CP'96*, pages 61–75.

[Bessiere and Régin, 2001] Bessiere, C. and Régin, J. (2001). Refining the basic constraint propagation algorithm. In *Proceedings of IJCAI'01*, pages 309–315.

[Bessiere and van Hentenryck, 2003] Bessiere, C. and van Hentenryck, P. (2003). To be or not to be ... a global constraint. In *Proceedings of CP'03*, pages 789–794.

[Bordeaux et al., 2009] Bordeaux, L., Hamadi, Y., and Samulowitz, H. (2009). Experiments with massively parallel constraint solving. In *Proceedings of IJCAI'09*, pages 443–448.

[Bornemann, 2003] Bornemann, F. (2003). Primes is in p, une avancée accessible à “l’homme ordinaire”. *Gazette des Mathématiciens*, (98):14–30.

[Boussemart et al., 2004] Boussemart, F., Hemery, F., Lecoutre, C., and Sais, L. (2004). Boosting systematic search by weighting constraints. In *Proceedings of ECAI'04*, pages 146–150.

[Bryant, 1986] Bryant, R. (1986). Graph-based algorithms for boolean function manipulation. *Computers, IEEE Transactions on*, 100(8):677–691.

[Cheng and Yap, 2006] Cheng, K. and Yap, R. (2006). Maintaining generalized arc consistency on ad-hoc n-ary Boolean constraints. In *Proceedings of ECAI'06*, pages 78–82.

[Cheng and Yap, 2010] Cheng, K. and Yap, R. (2010). An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints. *Constraints*, 15(2):265–304.

[Chu et al., 2009] Chu, G., Schulte, C., and Stuckey, P. (2009). Confidence-based work stealing in parallel constraint programming. In *Proceedings of CP'09*, pages 226–241.

[Chu et al., 2008] Chu, G., Stuckey, P., and Harwood, A. (2008). PMiniSAT: A Parallelization of MiniSAT 2.0. Technical report.
[Colton and Miguel, 2001] Colton, S. and Miguel, I. (2001). Constraint generation via automated theory formation. In *Proceedings of CP'01*, pages 575-579. Springer.

[Dasygenis and Stergiou, 2014] Dasygenis, M. and Stergiou, K. (2014). Building portfolios for parallel constraint solving by varying the local consistency applied. In *Proceedings of ICTAI'14*, pages 717-724.

[de la Banda et al., 2006] de la Banda, M. G., Marriott, K., Rafeh, R., and Wallace, M. (2006). The modelling language Zinc. In *Proceedings of CP'06*, pages 700-705.

[Dean and Ghemawat, 2008] Dean, J. and Ghemawat, S. (2008). Mapreduce: simplified data processing on large clusters. *Communications of the ACM*, 51(1):107-113.

[Debruyne and Bessiere, 1997] Debruyne, R. and Bessiere, C. (1997). Some practical filtering techniques for the constraint satisfaction problem. In *Proceedings of IJCAI'97*, pages 412-417.

[Dijkstra, 2001] Dijkstra, E. (2001). Solution of a problem in concurrent programming control. In *Pioneers and Their Contributions to Software Engineering*, pages 289-294. Springer.

[Domshlak et al., 2005] Domshlak, R. B. C., Fernández, C., Gomes, C., Krishnamachari, B., Selman, B., and Valls, M. (2005). Sensor networks and distributed csp: communication, computation and complexity. *Artificial Intelligence*, 161(1):117-147.

[Dunstan, 1991] Dunstan, N. (1991). Semaphores for fair scheduling monitor conditions. *ACM SIGOPS Operating Systems Review*, 25(3):27-31.

[Fahle et al., 2001] Fahle, T., Schamberger, S., and Sellman, M. (2001). Symmetry breaking. In *Proceedings of CP'01*, pages 93-107.

[Focacci and Milano, 2001] Focacci, F. and Milano, M. (2001). Global cut framework for removing symmetries. In *Proceedings of CP'01*, pages 77-92.

[Fredkin, 1960] Fredkin, E. (1960). Trie memory. *Communications of the ACM*, 3(9):490-499.

[Freuder, 1978] Freuder, E. (1978). Synthesizing constraint expressions. *Communication of the ACM*, 21(11):958-965.

[Frisch et al., 2007] Frisch, A., Grum, M., Jefferson, C., Hernandez, B. M., and Miguel, I. (2007). The design of ESSENCE: A constraint language for specifying combinatorial problems. In *Proceedings of IJCAI'07*, pages 80-87.
[Frisch et al., 2002] Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., and Walsh, T. (2002). Global constraints for lexicographic orderings. In *Proceedings of CP’02*, pages 93–108.

[Gaschnig, 1979] Gaschnig, J. (1979). Performance measurement and analysis of search algorithms. Technical Report CMU-CS-79-124, Carnegie Mellon.

[Gent et al., 2006] Gent, I., Jefferson, C., and Miguel, I. (2006). Minion: A fast, scalable constraint solver. In *Proceedings of ECAI’06*, pages 98–102.

[Gent et al., 2011] Gent, I., Jefferson, C., Miguel, I., Moore, N., Nightingale, P., Prosser, P., and Unsworth, C. (2011). A preliminary review of literature on parallel constraint solving. In *Proceedings of PMCS’11*.

[Gent et al., 2007] Gent, I., Jefferson, C., Miguel, I., and Nightingale, P. (2007). Data structures for generalised arc consistency for extensional constraints. In *Proceedings of AAAI’07*, pages 191–197.

[Gharbi et al., 2013] Gharbi, N., Hemery, F., Lecoutre, C., and Roussel, O. (2013). Optimizing STR algorithms with tuple compression. In *Proceedings of JFPC’13*, pages 143–146.

[Gharbi et al., 2014] Gharbi, N., Hemery, F., Lecoutre, C., and Roussel, O. (2014). Sliced table constraints: Combining compression and tabular reduction. In *Proceedings of CPAIOR’14*, pages 120–135.

[Ginsberg, 1993] Ginsberg, M. (1993). Dynamic backtracking. *Journal of Artificial Intelligence Research*, 1:25–46.

[Gomes and Selman, 2001] Gomes, C. and Selman, B. (2001). Algorithm portfolios. *Artificial Intelligence*, 126(1-2):43–62.

[Granas and Dugundji, 2003] Granas, A. and Dugundji, J. (2003). *Fixed Point Theory*. Springer, 1 edition.

[Gustafson, 1988] Gustafson, J. (1988). Reevaluating amdahl’s law. *Communications of the ACM*, 31(5):532–533.

[Hamadi, 1999] Hamadi, Y. (1999). Optimal distributed arc-consistency. In *Proceedings of CP’99*, pages 219–233.

[Han et al., 2000] Han, J., Pei, J., and Yin, Y. (2000). Mining frequent patterns without candidate generation. In *Proceedings of SIGMOD’00*, pages 1–12.

[Han et al., 2004] Han, J., Pei, J., Yin, Y., and Mao, R. (2004). Mining frequent patterns without candidate generation: A frequent-pattern tree approach. *Data Mining and Knowledge Discovery*, 8(1):53–87.
BIBLIOGRAPHY

[Haralick and Elliott, 1980] Haralick, R. and Elliott, G. (1980). Increasing tree search efficiency for constraint satisfaction problems. *Artificial Intelligence*, 14:263–313.

[Henz et al., 1993] Henz, M., Smolka, G., and Würtz, J. (1993). Oz-a programming language for multi-agent systems. In *Proceedings of IJCAI'93*, pages 404–409.

[Herken, 1995] Herken, R. (1995). *The universal Turing machine: a half-century survey*. Springer-Verlag New York, Inc.

[Herlihy and Wing, 1987] Herlihy, M. P. and Wing, J. M. (1987). Axioms for concurrent objects. In *Proceedings of SIGACT-SIGPLAN'87*, pages 13–26.

[Hoare, 1974] Hoare, C. A. R. (1974). Monitors: An operating system structuring concept. *Communications of the ACM*, 17(10):549–557.

[Hubbe and Freuder, 1992] Hubbe, P. and Freuder, E. (1992). An efficient cross product representation of the constraint satisfaction problem search space. In *Proceedings of AAAI'92*, pages 421–427.

[Jabbour et al., 2013a] Jabbour, S., Sais, L., and Salhi, Y. (2013a). A mining-based compression approach for constraint satisfaction problems. Technical Report arXiv:1305.3321, CoRR.

[Jabbour et al., 2013b] Jabbour, S., Sais, L., Salhi, Y., and Uno, T. (2013b). Mining-based compression approach of propositional formulae. In *Proceedings of CIKM'13*, pages 289–298.

[Katsirelos and Bacchus, 2005] Katsirelos, G. and Bacchus, F. (2005). Generalized nogoods in CSPs. In *Proceedings of AAAI'05*, pages 390–396.

[Katsirelos and Walsh, 2007] Katsirelos, G. and Walsh, T. (2007). A compression algorithm for large parity extensional constraints. In *Proceedings of CP'07*, pages 379–393.

[Kotthoff and Moore, 2010] Kotthoff, L. and Moore, N. (2010). Distributed solving through model splitting.

[Lecoutre, 2011] Lecoutre, C. (2011). STR2: Optimized simple tabular reduction for table constraints. *Constraints*, 16(4):341–371.

[Lecoutre and Cardon, 2005] Lecoutre, C. and Cardon, S. (2005). A greedy approach to establish singleton arc consistency. In *Proceedings of IJCAI'05*, pages 199–204.
[Lecoutre and Hemery, 2007] Lecoutre, C. and Hemery, F. (2007). A study of residual supports in arc consistency. In *Proceedings of IJCAI'07*, pages 125–130.

[Lecoutre et al., 2012] Lecoutre, C., Likitvivatanavong, C., and Yap, R. (2012). A path-optimal GAC algorithm for table constraints. In *Proceedings of ECAI'12*, pages 510–515.

[Lecoutre and Prosser, 2006] Lecoutre, C. and Prosser, P. (2006). Maintaining singleton arc consistency. In *Proceedings of CPAI'06*, pages 47–61.

[Lecoutre et al., 2007] Lecoutre, C., Sais, L., Tabary, S., and Vidal, V. (2007). Transposition Tables for Constraint Satisfaction. In *Proceedings of AAAI'07*, pages 243–248.

[Lecoutre and Szymanek, 2006] Lecoutre, C. and Szymanek, R. (2006). Generalized arc consistency for positive table constraints. In *Proceedings of CP'06*, pages 284–298.

[Lecoutre and Tabary, 2007] Lecoutre, C. and Tabary, S. (2007). Abscon 109: a generic CSP solver. In *Proceedings of the 2006 CSP solver competition*, pages 55–63.

[Li et al., 2009] Li, T., Baumberger, D., and Hahn, S. (2009). Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robin. In *Proceedings of SIGPLAN'09*, pages 65–74. ACM.

[Mackworth, 1977] Mackworth, A. (1977). Consistency in networks of relations. *Artificial Intelligence*, 8(1):99-118.

[Maheswaran et al., 2004] Maheswaran, R., Tambe, M., Bowring, E., Pearce, J., and Varakantham, P. (2004). Taking dcop to the real world: Efficient complete solutions for distributed multi-event scheduling. In *Proceedings of AAMAS'04*, pages 310–317.

[Mairy et al., 2015] Mairy, J., Deville, Y., and Lecoutre, C. (2015). The smart table constraint. In *Proceedings of CPAIOR'15*, pages 271–287.

[Michel and Hentenryck, 2012] Michel, L. and Hentenryck, P. V. (2012). Activity-based search for black-box constraint programming solvers. In *Proceedings of CPAIOR'12*, pages 228–243.

[Mohr and Henderson, 1986] Mohr, R. and Henderson, T. (1986). Arc and path consistency revisited. *Artificial Intelligence*, 28:225–233.

[Mohr and Masini, 1988] Mohr, R. and Masini, G. (1988). Good old discrete relaxation. In *Proceedings of ECAI'88*, pages 651–656.
[Montanari, 1974] Montanari, U. (1974). Network of constraints : Fundamental properties and applications to picture processing. *Information Science*, 7:95-132.

[Nguyen and Deville, 1998] Nguyen, T. and Deville, Y. (1998). A distributed arc-consistency algorithm. *Science of Computer Programming*, 30(1-2):227-250.

[Nightingale et al., 2011] Nightingale, P., Gent, I., Jefferson, C., and Miguel, I. (2011). Exploiting short supports for generalised arc consistency for arbitrary constraints. In *Proceedings of IJCAI'11*, pages 623-628.

[Nightingale et al., 2013] Nightingale, P., Gent, I., Jefferson, C., and Miguel, I. (2013). Short and long supports for constraint propagation. *Journal of Artificial Intelligence Research*, 46:1-45.

[Nyström et al., 2003] Nyström, D., Tešanović, A., and Hansson, C. N. J. (2003). The COMET database management system. Technical report, Mälardalen Real-Time Research Centre, Mälardalen University.

[O'Mahony et al., 2008] O'Mahony, E., Hebrard, E., Holland, A., Nugent, C., and O'Sullivan, B. (2008). Using case-based reasoning in an algorithm portfolio for constraint solving. In *Proceedings of ICAIG'08*, pages 53-62.

[Perez and Régin, 2014] Perez, G. and Régin, J. (2014). Improving gac-4 for table and mdd constraints. In *Proceedings of CP'14*, pages 606-621.

[Pesant, 2001] Pesant, G. (2001). A filtering algorithm for the stretch constraint. In *Proceedings of CP'01*, pages 183-195.

[Pesant, 2004] Pesant, G. (2004). A regular language membership constraint for finite sequences of variables. In *Proceedings of CP'04*, pages 482-495.

[Pesant et al., 2012] Pesant, G., Quimper, C.-G., and Zanarini, A. (2012). Counting-based search: Branching heuristics for constraint satisfaction problems. *Journal of Artificial Intelligence Research*, 43:173-210.

[Pramod and Vyas, 2010] Pramod, S. and Vyas, O. (2010). Article: Survey on frequent itemset mining algorithms. *International Journal of Computer Applications*, 1(15):86-91.

[Prosser, 1993] Prosser, P. (1993). Hybrid algorithms for the constraint satisfaction problems. *Computational Intelligence*, 9(3):268-299.

[Prosser et al., 1992] Prosser, P., Conway, C., and Muller, C. (1992). A constraint maintenance system for the distributed resource allocation problem. *Intelligent Systems Engineering*, 1(1):76-83.
[Rao and Kumar, 1988] Rao, V. and Kumar, V. (1988). Superlinear speedup in parallel state-space search. In *Foundations of Software Technology and Theoretical Computer Science*, pages 161–174. Springer.

[Refalo, 2004] Refalo, P. (2004). Impact-based search strategies for constraint programming. In *Proceedings of CP’04*, pages 557–571.

[Régin, 1994] Régin, J. (1994). A filtering algorithm for constraints of difference in CSPs. In *Proceedings of AAAI’94*, pages 362–367.

[Régin, 2011a] Régin, J. (2011a). Global constraints: a survey. In *Hybrid Optimization*, chapter 2, pages 63–134. Springer.

[Régin, 2011b] Régin, J. (2011b). Improving the expressiveness of table constraints. In *Proceedings of ModRef’11*.

[Régin et al., 2013] Régin, J., Rezgui, M., and Malapert, A. (2013). Embarrassingly parallel search. In *Proceedings of CP’13*, pages 596–610.

[Régin et al., 2014] Régin, J., Rezgui, M., and Malapert, A. (2014). Improvement of the embarrassingly parallel search for data centers. In *Principles and Practice of Constraint Programming*, pages 622–635. Springer.

[Rochart et al., 2006] Rochart, G., Cambazard, H., Laburthe, F., Jussien, N., and Benoist, T. (2006). Choco: a java library for constraint satisfaction problems (csp), constraint programming (cp) and explanation-based constraint solving (e-cp).

[Roussel and Lecoutre, 2009] Roussel, O. and Lecoutre, C. (2009). XML representation of constraint networks: Format XCSP 2.1. Technical Report arXiv:0902.2362, CoRR.

[Sabin and Freuder, 1994] Sabin, D. and Freuder, E. (1994). Contradicting conventional wisdom in constraint satisfaction. In *Proceedings of CP’94*, pages 10–20.

[Schubert et al., 2008] Schubert, T., Lewis, M., and Becker, B. (2008). Pamiraxt: Parallel sat solving with threads and message passing. *Journal on Satisfiability, Boolean Modeling and Computation*, 6:203–222.

[Schulte, 2000] Schulte, C. (2000). Parallel search made simple. In *University of Singapore*, pages 41–57.

[Schulte et al., 2006] Schulte, C., Tack, G., and Lagerkvist, M. (2006). Gecode: A generic constraint development environment.
[Simonis and O'Sullivan, 2008] Simonis, H. and O'Sullivan, B. (2008). Search strategies for rectangle packing. In *Proceedings of CP'08*, pages 52-66. Springer.

[Sleep, 1981] Sleep, F. B. M. (1981). Executing functional programs on a virtual tree of processors. In *Proceedings of FPCA'81*, pages 187-194.

[Stergiou, 2008] Stergiou, K. (2008). Heuristics for dynamically adapting propagation. In *Proceedings of ECAI'08*, pages 485-489.

[Stuckey et al., 2010] Stuckey, P., Becket, R., and Fischer, J. (2010). Philosophy of the minizinc challenge. *Constraints*, 15(3):307-316.

[Tiedemann et al., 2007] Tiedemann, P., Andersen, H. R., and Pagh, R. (2007). Generic global constraints based on mdds.

[Tseitin, 1983] Tseitin, G. (1983). On the complexity of derivation in propositional calculus. In *Automation of reasoning*, pages 466-483. Springer.

[Ullmann, 1977] Ullmann, J. (1977). A binary n-gram technique for automatic correction of substitution, deletion, insertion and reversal errors in words. *Computer Journal*, 20(2):141-147.

[Ullmann, 2007] Ullmann, J. (2007). Partition search for non-binary constraint satisfaction. *Information Science*, 177:3639-3678.

[van Dongen, 2006] van Dongen, M. (2006). Beyond singleton arc consistency. In *Proceedings of ECAI'06*, pages 163-167.

[van Hentenryck, 1999] van Hentenryck, P. (1999). *The OPL Optimization Programming Language*. The MIT Press.

[Wallace, 2005] Wallace, R. (2005). Heuristic policy analysis and efficiency assessment in constraint satisfaction search. In *Proceedings of CPAI'05*, pages 79-91.

[Witten and Frank, 2005] Witten, I. and Frank, E. (2005). *Data Mining: Practical Machine Learning Tools and Techniques*. Morgan Kaufmann Publishers Inc., second edition.

[Wu et al., 2008] Wu, X., Kumar, V., Quinlan, J. R., Ghosh, J., Yang, Q., Montoda, H., McLachlan, G., Ng, A., Liu, B., Yu, P., Zhou, Z.-H., Steinbach, M., Hand, D., and Steinberg, D. (2008). Top 10 algorithms in data mining. *Knowledge and Information Systems*, 14(1):1-37.

[Xia and Yap, 2013] Xia, W. and Yap, R. (2013). Optimizing STR algorithms with tuple compression. In *Proceedings of CP'13*, pages 724-732.
BIBLIOGRAPHY

[Xie and Davenport, 2010] Xie, F. and Davenport, A. (2010). Massively parallel constraint programming for supercomputers: Challenges and initial results. In *Proceedings of CPAIOR'10*, pages 334–338. Springer.

[Yokoo et al., 1998] Yokoo, M., Durfee, E., Ishida, T., and Kuwabara, K. (1998). The distributed constraint satisfaction problem: Formalization and algorithms. *Knowledge and Data Engineering, IEEE Transactions on*, 10(5):673–685.

[Yokoo et al., 1992] Yokoo, M., Ishida, T., Durfee, E., and Kuwabara, K. (1992). Distributed constraint satisfaction for formalizing distributed problem solving. In *Proceedings of ICDCS'92*, pages 614–621. IEEE.

[Zhang and Yap, 2001] Zhang, Y. and Yap, R. (2001). Making AC3 an optimal algorithm. In *Proceedings of IJCAI'01*, pages 316–321.