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

HAL
open science

# On Compressing and Parallelizing Constraint Satisfaction Problems

Nebras Gharbi

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

## To cite this version:

Nebras Gharbi. On Compressing and Parallelizing Constraint Satisfaction Problems. Artificial Intelligence [cs.AI]. Université d'Artois, 2015. English. NNT: 2015ARTO0406. tel-04276605

HAL Id: tel-04276605

https://hal.science/tel-04276605

Submitted on 9 Nov 2023

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
# On Compressing and Parallelizing Constraint Satisfaction Problems

By
Nebras GHARBI

A THESIS
submitted to
UNIVERSITY OF ARTOIS

in fulfilment of the requirements for the degree of

Doctor of Philosophy

of Artois University

Department of Computer Science

## Thesis committee:

<table><tr><td>Jean-Charles RÉGIN (University of Nice-Sophia Antipolis)</td><td>Referee</td></tr><tr><td>Xavier LORCA (École des Mines de Nantes)</td><td>Referee</td></tr><tr><td>Bertrand LE CUN (University of Paris-Ouest-Nanterre-La défense)</td><td>Examiner</td></tr><tr><td>Gilles DEQUEN (University of Picardie Jules Verne)</td><td>Examiner</td></tr><tr><td>Gilles AUDEMARD (University of Artois)</td><td>Examiner</td></tr><tr><td>Christophe LECOUTRE (University of Artois)</td><td>Supervisor</td></tr><tr><td>Fred HEMERY (University of Artois)</td><td>Co-Supervisor</td></tr><tr><td>Olivier ROUSSEL (University of Artois)</td><td>Co-Supervisor</td></tr></table>

CENTRE DE RECHERCHE EN INFORMATIQUE DE LENS (CRIL CNRS UMR 8188)

Université d'Artois, rue Jean Souvraz, S.P. 18 F-62307, Lens Cedex
France
# Contents

<table><tr><td>I</td><td>Background</td><td>39</td></tr><tr><td>1</td><td>Constraint Satisfaction Problem</td><td>40</td></tr><tr><td>1.1</td><td>Introduction to CSP</td><td>41</td></tr><tr><td>1.1.1</td><td>Definitions</td><td>41</td></tr><tr><td>1.1.2</td><td>Complexity</td><td>45</td></tr><tr><td>1.1.3</td><td>Example of a CSP: Map coloring</td><td>46</td></tr><tr><td>1.1.4</td><td>Solvers</td><td>48</td></tr><tr><td>1.2</td><td>Consistency</td><td>48</td></tr><tr><td>1.2.1</td><td>Definitions</td><td>48</td></tr><tr><td>1.3</td><td>Generalized Arc Consistency (GAC)</td><td>50</td></tr><tr><td>1.3.1</td><td>Arc Consistency</td><td>51</td></tr><tr><td>1.3.2</td><td>GAC for Table Constraints</td><td>55</td></tr><tr><td>1.4</td><td>Singleton Arc Consistency(SAC)</td><td>61</td></tr><tr><td>1.4.1</td><td>Definitions</td><td>62</td></tr><tr><td>1.4.2</td><td>SAC1</td><td>63</td></tr><tr><td>1.4.3</td><td>Weak k-SAC</td><td>64</td></tr><tr><td>1.5</td><td>Search</td><td>64</td></tr><tr><td>1.5.1</td><td>Look-back approaches</td><td>65</td></tr><tr><td>1.5.2</td><td>Look-ahead approaches</td><td>66</td></tr><tr><td>1.5.3</td><td>Maintaining Arc Consistency (MAC)</td><td>68</td></tr><tr><td>1.6</td><td>Heuristics</td><td>69</td></tr><tr><td>1.6.1</td><td>Static Variable Ordering (SVO)</td><td>69</td></tr><tr><td>1.6.2</td><td>Dynamic Variable Ordering (DVO)</td><td>69</td></tr><tr><td>1.6.3</td><td>Adaptive Variable Ordering (AVO)</td><td>69</td></tr><tr><td>2</td><td>Compression and Parallel computing</td><td>71</td></tr><tr><td>2.1</td><td>Compression techniques</td><td>72</td></tr><tr><td>2.1.1</td><td>Compact representation of table constraints</td><td>72</td></tr><tr><td>2.1.2</td><td>Compression-based approaches</td><td>78</td></tr><tr><td>2.2</td><td>Parallel computing</td><td>91</td></tr><tr><td>2.2.1</td><td>Definitions</td><td>92</td></tr><tr><td>2.2.2</td><td>Parallel performance measurements</td><td>93</td></tr></table>
CONTENTS

<table><tr><td>2.2.3 Parallel programming models</td><td>96</td></tr><tr><td>2.2.4 CSP solving using parallel programming models</td><td>100</td></tr></table>

## II Contributions 108

### 3 Compressing Table Constraints 109

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

### 4 Using Singleton Arc Consistency in Parallel to Improve Search 150

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

### 5 Conclusions and Future Work 174

### Bibliography 177
List of Figures

<table>
  <tbody>
    <tr>
      <td>1</td>
      <td>Compression des tuples.</td>
      <td>15</td>
    </tr>
    <tr>
      <td>2</td>
      <td>Le trie des motifs construits à partir de la contrainte décrite dans la table 3.1.</td>
      <td>17</td>
    </tr>
    <tr>
      <td>3</td>
      <td>La vue physique de la table compressée.</td>
      <td>18</td>
    </tr>
    <tr>
      <td>4</td>
      <td>Evolution de la structure stamps.</td>
      <td>18</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Un exemple de fragment de contrainte.</td>
      <td>20</td>
    </tr>
    <tr>
      <td>6</td>
      <td>Les deux première étapes de compression.</td>
      <td>22</td>
    </tr>
    <tr>
      <td>7</td>
      <td>FP-tree et la table compressée.</td>
      <td>23</td>
    </tr>
    <tr>
      <td>8</td>
      <td>Vue d'ensemble de l'architecture.</td>
      <td>29</td>
    </tr>
    <tr>
      <td>1.1</td>
      <td>The compatibility graph of constraint c<sub>xy</sub> such that dom(x) = dom(y) = {a, b, c}.</td>
      <td>43</td>
    </tr>
    <tr>
      <td>1.2</td>
      <td>Complete instantiation of the Tunisian map coloring (Solution).</td>
      <td>47</td>
    </tr>
    <tr>
      <td>1.3</td>
      <td>Illustration of domain filtering.</td>
      <td>50</td>
    </tr>
    <tr>
      <td>1.4</td>
      <td>An arc-inconsistent network P.</td>
      <td>51</td>
    </tr>
    <tr>
      <td>1.5</td>
      <td>Enforcing AC on c<sub>yz</sub>.</td>
      <td>52</td>
    </tr>
    <tr>
      <td>1.6</td>
      <td>Enforcing AC on constraints originally arc-consistent.</td>
      <td>52</td>
    </tr>
    <tr>
      <td>1.7</td>
      <td>Initialization of STR data structures for a positive table constraint c<sub>xyz</sub>; dom(x) = dom(y) = dom(z) = {a, b, c}.</td>
      <td>57</td>
    </tr>
    <tr>
      <td>1.8</td>
      <td>Enforcing GAC-STR on c<sub>xyz</sub> after the removal of (z, a) at level 1.</td>
      <td>58</td>
    </tr>
    <tr>
      <td>1.9</td>
      <td>Enforcing GAC-STR on c<sub>xyz</sub> after the removal of (x, a) at level 2; (y, c) is not supported.</td>
      <td>59</td>
    </tr>
    <tr>
      <td>1.10</td>
      <td>Enforcing Singleton Arc-Consistency on P.</td>
      <td>62</td>
    </tr>
    <tr>
      <td>1.11</td>
      <td>Possible standard backtracks on P.</td>
      <td>66</td>
    </tr>
    <tr>
      <td>1.12</td>
      <td>Forward Checking on P.</td>
      <td>67</td>
    </tr>
    <tr>
      <td>2.1</td>
      <td>A trie of English words.</td>
      <td>73</td>
    </tr>
    <tr>
      <td>2.2</td>
      <td>A trie representation of a table constraint.</td>
      <td>74</td>
    </tr>
    <tr>
      <td>2.3</td>
      <td>MDD built from the table constraint in Figure 2.2(a).</td>
      <td>76</td>
    </tr>
    <tr>
      <td>2.4</td>
      <td>DFA representation of the table constraint in Figure 2.4(a).</td>
      <td>78</td>
    </tr>
    <tr>
      <td>2.5</td>
      <td>SHORTGAC data structures.</td>
      <td>81</td>
    </tr>
    <tr>
      <td>2.6</td>
      <td>c-tuple representation.</td>
      <td>82</td>
    </tr>
    <tr>
      <td>2.7</td>
      <td>Smart table representation.</td>
      <td>83</td>
    </tr>
    <tr>
      <td>2.8</td>
      <td>Transaction database evolution.</td>
      <td>86</td>
    </tr>
  </tbody>
</table>
LIST OF FIGURES

<table>
  <tbody>
    <tr>
      <td>2.9</td>
      <td>FP-tree construction by adding the different transactions.</td>
      <td>88</td>
    </tr>
    <tr>
      <td>2.10</td>
      <td>Prefix path sub-trees.</td>
      <td>89</td>
    </tr>
    <tr>
      <td>2.11</td>
      <td>Conditional FP-Tree.</td>
      <td>90</td>
    </tr>
    <tr>
      <td>2.12</td>
      <td>Reducing table constraint: c<sub>0</sub> and c'.</td>
      <td>92</td>
    </tr>
    <tr>
      <td>2.13</td>
      <td>Possible speedup curves.</td>
      <td>93</td>
    </tr>
    <tr>
      <td>2.14</td>
      <td>Illustrating Amdahl's Law (total work).</td>
      <td>95</td>
    </tr>
    <tr>
      <td>2.15</td>
      <td>Illustrating Gustafson's Law (total work).</td>
      <td>95</td>
    </tr>
    <tr>
      <td>2.16</td>
      <td>Symmetric Shared Memory multiprocessor architecture.</td>
      <td>97</td>
    </tr>
    <tr>
      <td>2.17</td>
      <td>Non-uniform memory access model.</td>
      <td>97</td>
    </tr>
    <tr>
      <td>2.18</td>
      <td>Message passing model.</td>
      <td>98</td>
    </tr>
    <tr>
      <td>2.19</td>
      <td>Divide and conquer model.</td>
      <td>98</td>
    </tr>
    <tr>
      <td>2.20</td>
      <td>MapReduce model.</td>
      <td>99</td>
    </tr>
    <tr>
      <td>2.21</td>
      <td>Messages communicated between workers and manager.</td>
      <td>102</td>
    </tr>
    <tr>
      <td>2.22</td>
      <td>Work stealing architecture.</td>
      <td>103</td>
    </tr>
    <tr>
      <td>2.23</td>
      <td>Search-space splitting architecture.</td>
      <td>105</td>
    </tr>
    <tr>
      <td>3.1</td>
      <td>Patterns detection according to positions in the table constraint</td>
      <td>111</td>
    </tr>
    <tr>
      <td>3.2</td>
      <td>Patterns detection according to the scope in the table constraint</td>
      <td>112</td>
    </tr>
    <tr>
      <td>3.3</td>
      <td>The patterns trie built from &tau;<sub>1</sub> of the constraint given in Table 3.1.</td>
      <td>115</td>
    </tr>
    <tr>
      <td>3.4</td>
      <td>Compressing tuples.</td>
      <td>117</td>
    </tr>
    <tr>
      <td>3.5</td>
      <td>The trie of patterns built from the constraint given in Table 3.1: nbOcc are given in nodes.</td>
      <td>119</td>
    </tr>
    <tr>
      <td>3.6</td>
      <td>The trie of patterns built from the constraint given in Table 3.1: score are given in nodes.</td>
      <td>120</td>
    </tr>
    <tr>
      <td>3.7</td>
      <td>Compressed table (logical view).</td>
      <td>121</td>
    </tr>
    <tr>
      <td>3.8</td>
      <td>Compressed table (physical view).</td>
      <td>122</td>
    </tr>
    <tr>
      <td>3.9</td>
      <td>Compressed table (Gained space).</td>
      <td>122</td>
    </tr>
    <tr>
      <td>3.10</td>
      <td>Evolution of the stamps structure.</td>
      <td>123</td>
    </tr>
    <tr>
      <td>3.11</td>
      <td>Example of the stamps data structure evolution at currentTime = 1 (event x<sub>3</sub> &ne; c).</td>
      <td>126</td>
    </tr>
    <tr>
      <td>3.12</td>
      <td>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.</td>
      <td>129</td>
    </tr>
    <tr>
      <td>3.13</td>
      <td>Number of patterns used per length for 4 constraints of arity 32 of the instance problem nonogram &minus; gp &minus; 108.</td>
      <td>130</td>
    </tr>
    <tr>
      <td>3.14</td>
      <td>Number of patterns (detected and used) per score threshold for a constraint of arity 7 of the instance problem crossword-lex-vg5-7.</td>
      <td>131</td>
    </tr>
    <tr>
      <td>3.15</td>
      <td>Compression ratio per score threshold for a constraint of arity 7 of the instance problem crossword-lex-vg5-7.</td>
      <td>132</td>
    </tr>
    <tr>
      <td>3.16</td>
      <td>Example of a constraint entry.</td>
      <td>133</td>
    </tr>
    <tr>
      <td>3.17</td>
      <td>Frequencies.</td>
      <td>135</td>
    </tr>
  </tbody>
</table>
LIST OF FIGURES

<table>
  <tbody>
    <tr>
      <td>3.18</td>
      <td>Tuples sorted according to decreasing frequencies.</td>
      <td>135</td>
    </tr>
    <tr>
      <td>3.19</td>
      <td>FP-tree built for the table constraint in Table 3.3.</td>
      <td>136</td>
    </tr>
    <tr>
      <td>3.20</td>
      <td>Sliced table constraint.</td>
      <td>137</td>
    </tr>
    <tr>
      <td>3.21</td>
      <td>Gained Space after compression.</td>
      <td>140</td>
    </tr>
    <tr>
      <td>3.22</td>
      <td>STR-slice called on a slice table constraint after the event x<sub>3</sub> ≠ a.</td>
      <td>145</td>
    </tr>
    <tr>
      <td>3.23</td>
      <td>From Figure 3.22(b), STR-slice called after the event x<sub>3</sub> ≠ b.</td>
      <td>145</td>
    </tr>
    <tr>
      <td>4.1</td>
      <td>Overview of the architecture.</td>
      <td>152</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>Master's side: managing the Assignments Stack.</td>
      <td>154</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>A master's search tree at level 3.</td>
      <td>155</td>
    </tr>
    <tr>
      <td>4.4</td>
      <td>The master backtracking to level 2.</td>
      <td>156</td>
    </tr>
    <tr>
      <td>4.5</td>
      <td>Copying process (case 1: the same branch).</td>
      <td>158</td>
    </tr>
    <tr>
      <td>4.6</td>
      <td>Copying process (case 2: backtracking).</td>
      <td>159</td>
    </tr>
    <tr>
      <td>4.7</td>
      <td>A red-black tree.</td>
      <td>161</td>
    </tr>
    <tr>
      <td>4.8</td>
      <td>Illustration of the architecture.</td>
      <td>163</td>
    </tr>
    <tr>
      <td>4.9</td>
      <td>Pie chart of instances according to the speed-up ratio.</td>
      <td>169</td>
    </tr>
    <tr>
      <td>4.10</td>
      <td>Comparison between costlessMSAC and MAC for some selected instances of the primes problem using dom/ddeg.</td>
      <td>170</td>
    </tr>
    <tr>
      <td>4.11</td>
      <td>Comparison between costlessMSAC and MAC for two instances of different speed-up ratio.</td>
      <td>172</td>
    </tr>
  </tbody>
</table>
List of Tables

<table>
  <tbody>
    <tr>
      <td>1</td>
      <td>Une contrainte table c portant sur x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub>, x<sub>4</sub>, x<sub>5</sub>.</td>
      <td>12</td>
    </tr>
    <tr>
      <td>2</td>
      <td>La contrainte table C<sub>x<sub>1</sub>,x<sub>2</sub>,x<sub>3</sub>,x<sub>4</sub>,x<sub>5</sub></sub>.</td>
      <td>17</td>
    </tr>
    <tr>
      <td>3</td>
      <td>Le temps CPU (en secondes) pour quelques instances résolues avec MAC. Les ratios et le temps CPU de compression pour STR<sup>c</sup> sont donnés entre parenthèses.</td>
      <td>19</td>
    </tr>
    <tr>
      <td>4</td>
      <td>Le temps CPU sur quelques instances.</td>
      <td>28</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Le temps wall claock moyen pour des séries d'instances en utilisant l'heuristique dom/wdeg.</td>
      <td>34</td>
    </tr>
    <tr>
      <td>6</td>
      <td>Le temps wall claock moyen pour des séries d'instances en utilisant l'heuristique dom/ddeg.</td>
      <td>34</td>
    </tr>
    <tr>
      <td>1.1</td>
      <td>The worst-case complexity of several AC algorithms on binary constraint networks.</td>
      <td>53</td>
    </tr>
    <tr>
      <td>1.2</td>
      <td>The worst-case complexity of the SAC algorithms on binary constraint networks.</td>
      <td>63</td>
    </tr>
    <tr>
      <td>2.1</td>
      <td>Transaction database of different market baskets.</td>
      <td>85</td>
    </tr>
    <tr>
      <td>2.2</td>
      <td>The frequent itemsets (minSupport=5).</td>
      <td>89</td>
    </tr>
    <tr>
      <td>3.1</td>
      <td>Table constraint C<sub>x<sub>1</sub>,x<sub>2</sub>,x<sub>3</sub>,x<sub>4</sub>,x<sub>5</sub></sub>.</td>
      <td>114</td>
    </tr>
    <tr>
      <td>3.2</td>
      <td>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.</td>
      <td>128</td>
    </tr>
    <tr>
      <td>3.3</td>
      <td>Table constraint c on x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub>, x<sub>4</sub>, x<sub>5</sub>.</td>
      <td>132</td>
    </tr>
    <tr>
      <td>3.4</td>
      <td>The sub-table T<sub>1</sub> associated with the pattern &mu;<sub>1</sub> of c.</td>
      <td>133</td>
    </tr>
    <tr>
      <td>3.5</td>
      <td>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.</td>
      <td>146</td>
    </tr>
    <tr>
      <td>3.6</td>
      <td>CPU time (in seconds) on some selected instances solved by MAC. Compression ratio and CPU time are given for STR-slice between parentheses.</td>
      <td>147</td>
    </tr>
    <tr>
      <td>3.7</td>
      <td>STR<sup>c</sup> and STR-slice compared to ShortSTR2.</td>
      <td>148</td>
    </tr>
    <tr>
      <td>3.8</td>
      <td>STR<sup>c</sup> and STR-slice compared to STR2-C.</td>
      <td>148</td>
    </tr>
  </tbody>
</table>
LIST OF TABLES

<table><tr><td>4.1</td><td>Results for the sequential and parallel approaches for solving a few selected instances with dom/wdeg.</td><td>165</td></tr><tr><td>4.2</td><td>The average wall clock time for series of instances with dom/wdeg.</td><td>166</td></tr><tr><td>4.3</td><td>Results for the sequential and parallel approaches for solving a few selected instances with dom/ddeg.</td><td>167</td></tr><tr><td>4.4</td><td>The average wall clock time for series of instances with dom/ddeg.</td><td>168</td></tr><tr><td>4.5</td><td>The wall clock time (in seconds) for some selected instances with costlessMSAC and MAC (dom/ddeg).</td><td>171</td></tr><tr><td>4.6</td><td>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.</td><td>171</td></tr><tr><td>4.7</td><td>The wall clock time (in seconds) for some selected instances with costlessMWeak-1-SAC and MAC (dom/ddeg) establishing weak-1-SAC.</td><td>173</td></tr></table>
List of Algorithms

<table>
  <tbody>
    <tr>
      <td>1</td>
      <td>compress-STR<sup>c</sup>(c: Constraint, FP-Queue: Queue)</td>
      <td>16</td>
    </tr>
    <tr>
      <td>2</td>
      <td>compress-STR-slice(c: Constraint, minSupport: float)</td>
      <td>24</td>
    </tr>
    <tr>
      <td>3</td>
      <td>STR-slice(c: constraint):set of variables</td>
      <td>27</td>
    </tr>
    <tr>
      <td>4</td>
      <td>enforceConsistencyOnLiterals(P<sub>i</sub>: Constraint Network of slave i, LiteralsQueue: Queue of literals)</td>
      <td>30</td>
    </tr>
    <tr>
      <td>5</td>
      <td>ValidMessage(msg: Message): Boolean</td>
      <td>31</td>
    </tr>
    <tr>
      <td>6</td>
      <td>applyMessages.hasBacktracked: Boolean)</td>
      <td>32</td>
    </tr>
    <tr>
      <td>7</td>
      <td>solveProblem(P: Constraint network)</td>
      <td>33</td>
    </tr>
    <tr>
      <td>8</td>
      <td>doAC (P = (X, D, C): Constraint network): Boolean</td>
      <td>54</td>
    </tr>
    <tr>
      <td>9</td>
      <td>revise-3(c: constraint, x:variable): Boolean</td>
      <td>54</td>
    </tr>
    <tr>
      <td>10</td>
      <td>revise-2001(c: constraint, x:variable): Boolean</td>
      <td>55</td>
    </tr>
    <tr>
      <td>11</td>
      <td>enforceGAC-STR2(P:constraint network, c: constraint):set of variables</td>
      <td>60</td>
    </tr>
    <tr>
      <td>12</td>
      <td>ValidSTuple(c: constraint, S<sup>val</sup>:variables, τ: tuple): Boolean</td>
      <td>61</td>
    </tr>
    <tr>
      <td>13</td>
      <td>SAC(P: constraint network):Boolean</td>
      <td>63</td>
    </tr>
    <tr>
      <td>14</td>
      <td>WSAC(P: constraint network, k: integer):Boolean</td>
      <td>65</td>
    </tr>
    <tr>
      <td>15</td>
      <td>MAC(P: constraint network)</td>
      <td>68</td>
    </tr>
    <tr>
      <td>16</td>
      <td>SeekValidSupportTrie(x: variable, a: value): Tuple</td>
      <td>74</td>
    </tr>
    <tr>
      <td>17</td>
      <td>extendSupport(node: Node, τ: Tuple): Tuple</td>
      <td>75</td>
    </tr>
    <tr>
      <td>18</td>
      <td>mddc(G: MDD root, st: state): (boolean, state)</td>
      <td>76</td>
    </tr>
    <tr>
      <td>19</td>
      <td>addPattern(root:Node,μ:Pattern)</td>
      <td>113</td>
    </tr>
    <tr>
      <td>20</td>
      <td>getPattern(node:Node):pattern</td>
      <td>113</td>
    </tr>
    <tr>
      <td>21</td>
      <td>getLengthPath(node:Node):Integer</td>
      <td>113</td>
    </tr>
    <tr>
      <td>22</td>
      <td>buildPatterns(c: Constraint): Queue</td>
      <td>116</td>
    </tr>
    <tr>
      <td>23</td>
      <td>extractBestFrequentPatterns(node: Node, FP-Queue: Queue)</td>
      <td>117</td>
    </tr>
    <tr>
      <td>24</td>
      <td>compress-STR<sup>c</sup>(c: Constraint, FP-Queue: Queue)</td>
      <td>118</td>
    </tr>
    <tr>
      <td>25</td>
      <td>STR<sup>c</sup>(P:constraint network, c: constraint):set of variables</td>
      <td>124</td>
    </tr>
    <tr>
      <td>26</td>
      <td>ValidTuple<sup>comp</sup>(c: Constraint, τ: Tuple): Boolean</td>
      <td>125</td>
    </tr>
    <tr>
      <td>27</td>
      <td>compress-STR-slice(c: Constraint, minSupport: float)</td>
      <td>138</td>
    </tr>
    <tr>
      <td>28</td>
      <td>pruneTree(node: Node,minSupport: Float, parentSavings: Integer)</td>
      <td>139</td>
    </tr>
  </tbody>
</table>
LIST OF ALGORITHMS

<table><tr><td>29</td><td>searchPattern(root: Node, τ: Tuple): pattern</td><td>139</td></tr><tr><td>30</td><td>STR-slice(c: constraint):set of variables</td><td>142</td></tr><tr><td>31</td><td>ValidPattern(μ: pattern): Boolean</td><td>143</td></tr><tr><td>32</td><td>scanSubtable(T: sub-table): Boolean</td><td>144</td></tr><tr><td>33</td><td>ValidSubtuple(S<sup>lval</sup>: variables, τ: tuple): Boolean</td><td>144</td></tr><tr><td>34</td><td>ValidMessage(msg: Message): Boolean</td><td>155</td></tr><tr><td>35</td><td>applyMessages.hasBacktracked: Boolean)</td><td>157</td></tr><tr><td>36</td><td>enforceConsistencyOnLiterals(P<sub>i</sub>: Constraint Network of slave i, LiteralsQueue: Queue of literals)</td><td>160</td></tr><tr><td>37</td><td>solveProblem(P: Constraint network)</td><td>162</td></tr></table>
# Résumé Détaillé de la Thèse

## Introduction

La programmation par contraintes (CP) est un cadre puissant utilisé pour modéliser et résoudre des problèmes combinatoires, employant des techniques d'intelligence artificielle, de la recherche opérationnelle, de théorie des graphes, ..., etc. L'idée de base de la programmation par contraintes est que l'utilisateur exprime ses contraintes et qu'un solveur de contraintes cherche une ou plusieurs solutions.

Les problèmes de satisfaction de contraintes (CSP) [Montanari, 1974], sont au coeur de la programmation par contraintes. Ce sont des problèmes de décision où nous recherchons des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Ces problèmes de décision revoient *vrai*, si le problème admet une solution, *faux*, sinon. Les problèmes de satisfaction de contraintes sont le sujet de recherche intense tant en recherche opérationnelle qu'en intelligence artificielle. Beaucoup de CSPs exigent la combinaison d'heuristiques et de méthode d'inférences combinatoires pour les résoudre dans un temps raisonnable.

La résolution des CSPs peut rapidement devenir difficile quand le problème représente un volume important de données. Les solveurs sont composés de deux mécanismes importants : la “recherche” et “l’inférence”. En effet, le mécanisme “d’inférence” se réfère à l’élaboration des déductions, tandis que, le mécanisme de “recherche” consiste à l’élaboration d’une solution en étendant itérativement une solution partielle. Pour former une solution, ou prouver qu’aucune solution n’existe, un solveur alterne entre la recherche et l’inférence. Il prend une nouvelle décision pour étendre une solution partielle et fait ensuite autant de déductions que possible. La déduction pourrait, par exemple, enlever toutes les valeurs qui ne peuvent plus apparaître dans une solution. Quand il n’y a plus de déduction qui pourrait être déduite de la dernière décision, le solveur prend une nouvelle décision. En fait, la décision est faite sur la base d’une heuristique donnée, c’est-à-dire, le solveur attribue une valeur à une variable choisie par l’heuristique qui supposent que ce choix puisse accélérer la recherche ou mener à une solution. Ce n’est pas le
cas toujours, c'est pourquoi le solveur pourrait effectuer un retour en arrière
jusqu'aux décisions précédentes, concluant que la dernière décision mène à
un échec et, ainsi, aucune solution ne pourrait être trouvée à partir de cet endroit.

Avec l'amélioration des ordinateurs, la résolution de plus grands problèmes
devient plus facile. Bien qu'il y ait plus de capacités offertes par la nouvelle
génération de machines, les problèmes industriels deviennent de plus en plus
grand ce qui implique un espace énorme pour les stocker et aussi plus de temps
pour les résoudre. Durant ces dernières décennies, plusieurs travaux ont été
proposés pour traiter ces problèmes.

D'une part, plusieurs approches ont été proposée pour réduire l'espace mémoire
requis pour représenter les contraintes et, particulièrement les contraintes table
qui sont des contraintes exprimés en extension. De différentes approches
utilisent des structures de données compactes pour représenter des contraintes
table comme des Tries [Gent et al., 2007], des Diagrammes de Décision multi-
valués (MDDs) [Cheng and Yap, 2010] et des Automates Finis Déterministes
(DFA) [Pesant, 2004]. D'autres ont proposé des nouvelles représentations
compactes comme les tuples compressés [Hubbe and Freuder, 1992], des
short supports [Nightingale et al., 2011, Nightingale et al., 2013], les smart
tuples [Mairy et al., 2015] et des approches basées sur la fouille de données
[Jabbour et al., 2013a, Jabbour et al., 2013b].

D'autre part, plusieurs travaux ont proposé des approches différentes
pour l'accélération du temps de résolution à travers l'utilisation des archi-
tectures parallèles. Nous distinguons des techniques différentes comme le
work sharing [Schulte, 2000, Régin et al., 2013, Régin et al., 2014], le work
stealing [Sleep, 1981, Kotthoff and Moore, 2010, Kotthoff and Moore, 2010,
Chu et al., 2009], la Recherche Multi-agent [Rao and Kumar, 1988,
Bordeaux et al., 2009] et l'utilisation des Portfolios [Gomes and Selman, 2001,
O'Mahony et al., 2008, Amadini et al., 2015, Dasygenis and Stergiou, 2014].

Dans cette thèse, nous nous intéressons aux problèmes de satisfaction de
contraintes et en particulier les différentes techniques utilisées dans la réduction
de l'espace mémoire requis pour la représentation des contraintes et aussi le
temps de résolution. Dans le premier chapitre, nous introduisons les notions
de bases de l'état de l'art utilisés dans ce manuscrit. nous détaillons aussi les
différentes techniques utilisées dans la recherche et l'inférence. Le deuxième
chapitre se compose principalement de deux parties. Dans la première partie,
nous décrivons les différentes méthodes de l'état de l'art utilisées dans la com-
pression des contrainte table. Tandis que la deuxième partie, décrit l'état de l'art
de la programmation parallèle ainsi que les différents travaux utilisant une archi-
tecture parallèle dans la résolution des CSPs. Dans le **troisième chapitre**, nous présentons deux contributions autour la compression des contraintes table. Pour chacune des contributions, nous décrivons la méthode de compression ainsi que l’algorithme de filtrage. Dans le **quatrième chapitre**, nous présentons une contribution qui consiste à résoudre une instance CSP en établissant des cohérences en parallèle. En effet, nous explorons une nouvelle manière d’utilisation d’une architecture parallèle dans laquelle un solveur principale est aidé par différent esclaves qui établissent des cohérences fortes qui sont couteuse pour être maintenue durant la recherche. Finalement, nous concluons et nous présentons les perspectives de nos travaux dans le **dernier chapitre**.

## Préliminaires

Un réseau de contraintes (discret) (CN) $N$ est un ensemble fini de $n$ variables reliées par un ensemble fini de $e$ contraintes. Chaque variable $x$ a un domaine qui représente l’ensemble fini de valeurs qui peuvent être assignées à $x$. Le domaine initial d’une variable $x$ est noté $dom^{init}(x)$ tandis que le domaine courant de $x$ est noté $dom(x)$. Nous avons toujours $dom(x) \subseteq dom^{init}(x)$. Chaque contrainte $c$ porte sur un ensemble ordonné de variables, appelé portée (scope) de $c$ et noté $scp(c)$, et est sémantiquement défini par une relation, notée $rel(c)$, qui contient l’ensemble des tuples autorisés pour les variables impliquées dans $c$. Une contrainte table (positive) $c$ est une contrainte telle que $rel(c)$ est définie explicitement en énumérant les tuples qui sont autorisés par $c$ (voir exemple ci-dessous). L’arité d’une contrainte $c$ est la taille de $scp(c)$. L’arité maximale du réseau sera notée $r$.

**Exemple 1** Soit $c$ une contrainte table positive portant sur les variables $x_1, x_2, x_3, x_4, x_5$ telles que $dom(x_1) = dom(x_2) = dom(x_3) = dom(x_4) = dom(x_5) = \{a, b, c\}$. La table 1 liste les 7 tuples autorisés par la contrainte $c$.

<table><caption>Table 1: Une contrainte table $c$ portant sur $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><th>&tau;<sub>1</sub></th><td>(c, b, c, a, c)</td><td></td><td></td><td></td><td></td></tr><tr><th>&tau;<sub>2</sub></th><td>(a, a, b, c, a)</td><td></td><td></td><td></td><td></td></tr><tr><th>&tau;<sub>3</sub></th><td>(a, c, b, c, a)</td><td></td><td></td><td></td><td></td></tr><tr><th>&tau;<sub>4</sub></th><td>(b, a, c, b, c)</td><td></td><td></td><td></td><td></td></tr><tr><th>&tau;<sub>5</sub></th><td>(b, a, a, b, b)</td><td></td><td></td><td></td><td></td></tr><tr><th>&tau;<sub>6</sub></th><td>(c, c, b, c, a)</td><td></td><td></td><td></td><td></td></tr><tr><th>&tau;<sub>7</sub></th><td>(a, c, a, c, a)</td><td></td><td></td><td></td><td></td></tr></tbody></table>
Soit $X = \{x_1, \dots, x_r\}$ un ensemble ordonné de variables. Une instanciation $I$ de $X$ est un ensemble $\{(x_1, a_1), \dots, (x_r, a_r)\}$ qui est également noté $\{x_1 = a_1, \dots, x_r = a_r\}$ tel que $\forall i \in 1..r, a_i \in \text{dom}^{\text{init}}(x_i)$. $X$ est notée $\text{vars}(I)$ et chaque $a_i$ est notée $I[x_i]$. Un littéral est une paire $(x, a_i)$ où $x \in \mathcal{X}$ et $a_i \in \text{dom}(x)$. Une instanciation $I$ est valide ssi $\forall (x, a) \in I, a \in \text{dom}(x)$. Un $r$-tuple $\tau$ sur $X$ est une suite de valeurs $(a_1, \dots, a_r)$ telle que $\forall i \in 1..r, a_i \in \text{dom}^{\text{init}}(x_i)$; la valeur $a_i$ sera notée $\tau[x_i]$. Un tuple défini sur un ensemble $X$ peut être vu comme une instanciation de $X$ et inversement. De ce fait, un $r$-tuple $\tau$ sur $\text{scp}(c)$ est valide ssi l'instanciation sous-jacente est valide. Un $r$-tuple $\tau$ sur $\text{scp}(c)$ est un support sur la contrainte $r$-aire $c$ ssi $\tau$ est un tuple valide qui est autorisé par $c$. Si $\tau$ est un support sur une contrainte $c$ impliquant une variable $x$ et tel que $\tau[x] = a$, on dit que $\tau$ est un support pour $(x, a)$ sur $c$. GAC est une cohérence de domaine définie comme suit :

**Définition 1** Une contrainte $c$ satisfait la cohérence d'arc généralisée (GAC) ssi $\forall x \in \text{scp}(c), \forall a \in \text{dom}(x)$, il existe au moins un support pour $(x, a)$ sur $c$. Un CN $N$ est GAC ssi chaque contrainte de $N$ est GAC.

L'application de GAC implique la suppression de toutes les valeurs qui n'ont pas de support sur une contrainte. De nombreux algorithmes ont été mis au point pour établir GAC selon la nature des contraintes. STR [Ullmann, 2007] est l'un de ces algorithmes pour les contraintes table : il supprime les tuples invalides lors de la recherche de supports en utilisant une structure de données qui sépare les tuples valides des tuples invalides. Cette méthode de recherche des supports améliore le temps de recherche en évitant les tests redondants sur des tuples invalides qui ont déjà été détectés comme invalides lors des précédents applications de GAC. STR2 [Lecoutre, 2011], une optimisation de STR, évite certaines opérations de base concernant la validité de tuples et l'identification des supports, par l'introduction de deux ensembles importants appelés $S^{\text{sup}}$ et $S^{\text{val}}$ (décrits ultérieurement). Dans le meilleur des cas, STR2 est $r$ fois plus rapide que STR.

# La compression des contraintes tables

## STR$^c$

La première approche, appelée (STR$^c$), consiste à combiner l'algorithme STR avec un algorithme de compression basé sur les "tries", qui diffère des approches décrites dans [Katsirelos and Walsh, 2007] et [Xia and Yap, 2013] où une représentation sur la base des produits cartésiens est utilisée pour la compression. L'idée de base est d'identifier les motifs récurrents, appelés sous tuples, dans le tuples de chaque contrainte et remplacer leurs occurrences par des références vers une table de motifs. Le processus de filtrage est une adaptation
de l'algorithme STR qui prend en considération les motifs apparaissant dans des positions différentes.

**Méthode de compression** Un motif $\mu$ d'une contrainte table $c$ est une séquence de valeurs consécutives (sous-tuples) dans un tuple $\tau$ d'une table. On note $|\mu|$ la longueur d'un motif $\mu$, et $nbOcc(\mu)$ le nombre d'occurrences du motif repérées dans l'ensemble des tuples d'une contrainte donnée.

Afin de réduire la complexité spatiale de la représentation des tuples de chaque contrainte, nous allons repérer les motifs les plus fréquents et remplacer chaque occurrence de motif par un symbole unique. De ce fait, la taille utilisée pour représenter la table sera d'autant plus faible que la longueur des motifs sera grande et que leur nombre d'occurrences sera important.

Il est important de noter que nous considérons que les motifs extraits dans le cadre de notre approche sont indépendants de leur position initiale dans le tuple. En conséquence, un motif ne correspond pas obligatoirement à l'affectation des mêmes valeurs aux mêmes variables mais plutôt la même suite d'affectation à une séquence de variables consécutives. Ce choix a été fait dans l'espoir d'obtenir des motifs les plus fréquents possibles, et donc une meilleure compression.

Pour identifier les motifs pertinents, nous allons dans un premier temps créer une forêt d'arbres de préfixes à partir des différents tuples d'une contrainte table donnée. Un arbre enregistre toutes les séquences existantes de valeurs de longueur donnée et leur nombre d'occurrences. Pour garantir un certain niveau d'efficacité de compression, la longueur minimale des séquences est fixée dans notre approche à 3, et la longueur maximale à l'arité de la contrainte moins 1.

Dans un second temps, il nous faut identifier les motifs les plus efficaces pour le processus de compression. Pour cela nous allons introduire la notion de **score** d'un motif $\mu$ comme suit :

$$ score(\mu) = -\mu - \times nbOcc(\mu) $$

Un seuil de sélection est fixé, seuls les motifs dont le score est supérieur au seuil de sélection sont retenus dans l'algorithme de compression et stockés dans la table des motifs. Pour des raisons d'efficacité, le nombre total de motifs retenus est borné par un second paramètre afin de contrôler le temps de compression.

Le processus de compression utilise donc les motifs dont le score est supérieur au seuil de sélection. Un parcours de la table est effectué pour détecter la présence des motifs retenus et établir une référence vers la table de motifs. Si dans un tuple, plusieurs motifs se recouvrent, l'algorithme de compression choisit en priorité le motif ayant le meilleur score. Après compression, la table contient des tuples de longueurs différentes composés de valeurs et de références vers la table des motifs.
La figure 3.4 illustre la structure de données compressée. En fait, une fois qu'un motif est trouvé, il est remplacé par une référence vers une table de motifs où les motifs fréquents sont stockés. La référence est codée par un entier négatif (-patternid). En fait, le tuple ne contient pas les valeurs composant le motif, mais plutôt une référence vers le motif.

<figure><img src="image_4.png" /><figcaption>Figure 1: Compression des tuples.</figcaption></figure>

L'algorithme 24 décrit la méthode de compression. D'abord, pour chaque tuple de la contrainte table nous cherchons le meilleur motif contenu dans *FP-Queue*. En cherchant le meilleur motif, nous respectons un ordre décroissant des scores. Si un motif est trouvé, nous l'ajoutons à la table de motifs et remplaçons ensuite son occurrence dans le tuple par une référence vers celui-ci dans la table des motifs. Ce processus continue jusqu'à il n'y a plus de motif possible qui pourrait être remplacé dans le tuple. Nous notons qu'en cherchant le meilleur motif contenu dans un tuple, nous prenons en considération les remplacements fait auparavant. En conséquence, les motifs ne se chevauchent pas puisque nous choisissons de remplacer toujours l'occurrence du meilleur. Une fois que nous avons itéré sur toutes les valeurs d'un tuple nous vérifions si nous avons déjà remplacé au moins un motif. Si c'est le cas, le tuple $\tau_i$ de la contrainte est remplacé par sa version compressée $\tau_i^c$. La table 3.1 présente une contrainte table positive d'arité 5, impliquant les variables $x_1, x_2, x_3, x_4$ et $x_5$. nous notons que plusieurs motifs sont répétés sur l'ensemble des tuples tels que *cbc*, *aab* et *abb* comme des motifs de taille 3 et *aabb*, *acbc* et *cbca* comme des motifs de taille 4. En itérant sur l'ensemble des tuples de notre contrainte, on peut construire le trie décrit dans la figure 3.5, où le nombre des occurrences est donné au niveau de chaque noeud. Chaque noeud représente un chemin $\mu$ (allant de la racine à une feuille) associé avec le compteur $nbOcc(\mu)$.

Le mécanisme de compression engendre une réduction importante de l'espace mémoire occupé par la contrainte table. La vue physique décrite dans la figure 3.8 illustre mieux ce phénomène. Les tuples compressés font référence à leur motifs correspondant stockés dans la tables des motifs. La contrainte table est donc composée de tuples de différentes longueurs puisqu'ils contiennent des motifs de différentes tailles.
<caption>**Algorithm 1:** compress-STR<sup>c</sup>(c: Constraint, FP-Queue: Queue)</caption>

1 **foreach** $\tau_i \in table(c)$ **do**
2 &nbsp;&nbsp;&nbsp;**repeat**
3 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**//** searching for the best frequent pattern contained in $\tau_i$
3 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bestPattern ← <;
4 &nbsp;&nbsp;&nbsp;**foreach** $\mu_i \in FP-Queue$ **do**
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** contains($\mu_i, \tau_i$) **then**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bestPattern ← $\mu_i$
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bestPatterniltion ← index($\mu_i, \tau_i$)
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**break**
9 &nbsp;&nbsp;&nbsp;**if** bestPattern $\neq$ nil **then**
10 &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<sup>c</sup>
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;position ← 0
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;length<sup>c</sup> ← 0
12 &nbsp;&nbsp;&nbsp;**while** position < $\tau_i$.length **do**
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** position = bestPattern. position **then**
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\tau_i^c$[length<sup>c</sup>] ← -bestPattern.id **//** a reference
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;towards the pattern
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;position ← position + bestPattern.length
16 &nbsp;&nbsp;&nbsp;**else**
17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\tau_i^c$[length<sup>c</sup>] ← $\tau_i$[position]
18 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;position ← position + 1
19 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;length<sup>c</sup> ← length<sup>c</sup> + 1
20 **until** bestPattern = nil
21 **if** length<sup>c</sup> < $\tau_i$.length **then**
22 &nbsp;&nbsp;&nbsp;**tau** ← $\tau_i^c$

**Algorithme de filtrage** Lors du filtrage d'une contrainte table, il est nécessaire de vérifier la validité des tuples, ce qui implique de vérifier la validité des motifs. Quand un motif apparaît plusieurs fois dans la table à partir de la même position, nous souhaitons n'effectuer le test de validité du motif qu'une seule fois, ce qui permet de traduire la compression spatiale en une réduction du temps de filtrage.

Pour ce faire, nous utilisons un compteur *time* qui est incrémenté à chaque filtrage de la contrainte table et un tableau *stamps*[$\mu_i$, *j*] associé à la contrainte.
<table><caption>Table 2: La contrainte table $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><th>τ<sub>1</sub></th><td>(c, b, c, a, c)</td><td></td><td></td><td></td><td></td></tr><tr><th>τ<sub>2</sub></th><td>(a, a, b, b, a)</td><td></td><td></td><td></td><td></td></tr><tr><th>τ<sub>3</sub></th><td>(a, c, b, c, a)</td><td></td><td></td><td></td><td></td></tr><tr><th>τ<sub>4</sub></th><td>(b, a, c, b, c)</td><td></td><td></td><td></td><td></td></tr><tr><th>τ<sub>5</sub></th><td>(b, a, a, b, b)</td><td></td><td></td><td></td><td></td></tr><tr><th>τ<sub>6</sub></th><td>(a, c, b, c, b)</td><td></td><td></td><td></td><td></td></tr><tr><th>τ<sub>7</sub></th><td>(a, c, a, c, a)</td><td></td><td></td><td></td><td></td></tr></tbody></table>

<figure><img src="image_5.png" /><figcaption>Figure 2: Le trie des motifs construits à partir de la contrainte décrite dans la table 3.1.</figcaption></figure>

Pour un motif $\mu_i$ qui s'applique à partir d'une position $j$, stamps[$\mu_i$, $j$] donne le résultat du dernier test de validité de $(\mu_i, j)$ (champ stamps[$\mu_i$, $j$].valid) ainsi que la valeur stamps[$\mu_i$, $j$].time du compteur time lors de ce test. Chaque fois que la validité de $(\mu_i, j)$ doit être testée, nous vérifions d'abord si stamps[$\mu_i$, $j$].time est égal à la valeur courante de time. Si c'est le cas, la validité a déjà été testée dans l'opération de filtrage courante et donc stamps[$\mu_i$, $j$].valid fournit directement la réponse, ce qui évite des calculs inutiles. Sinon, il faut effectivement tester la validité de $(\mu_i, j)$ et sauvegarder le résultat dans stamps[$\mu_i$, $j$].

La figure 3.10 illustre l'évolution de la structure stamps. D'abord, tous les éléments sont initialisés à `currentTime=0` et les champs `valid` reste vide (voir figure 3.10(a)). Durant le premier filtrage de la table, le compteur global est mis à 1. Par exemple, pour déterminer si le tuple $\tau_3$ est valid, il faut s'assurer que $\mu_1$ à la position $j = 2$ est valide. Comme la valeur `time` du champ `stamps[$\mu_1$,2]` n'est pas égal à la valeur courante du `currentTime`, nous constatons que le test
<figure><img src="image_6.png" /><figcaption>Figure 3: La vue physique de la table compressée.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 4: Évolution de la structure stamps.</figcaption></figure>

n'est pas encore fait dans le filtrage courant. Par conséquent, nous vérifions si c, b et c sont encore présents dans les domaines respectifs des variables $x_2, x_3$ et $x_4$. Nous supposons que c'est le cas et donc les champs *time* et *valid* de *stamps*[$\mu_1, 2$] prennent les valeurs 1 et true. Plus tard, quand nous testons la validité du tuple $\tau_6$, nous nous apercevons immédiatement que la validité du motif $\mu_1$ a été déjà vérifié dans le filtrage courant et ça suffit donc d'utiliser le résultat enregistré dans le champs *valid* de *stamps*[$\mu_1, 2$]. Supposons que $\mu_1$ est invalide à la position 1 et 3, valide à la position 2 et que $\mu_2$ est valide à la position 1 et 2, nous obtenons à la fin du filtrage le résultat illustré dans la figure 3.10(b).

**Résultats expérimentaux** Pour montrer le potentiel de notre approche (STR^c), nous avons comparé le comportement des algorithmes MDD, STR1, STR2, STR3 et STR^c lorsqu'ils sont intégrés à l'algorithme de recherche MAC (qui maintient la propriété de cohérence d'arc généralisée lors d'une recherche arborescente). Nous avons effectué quelques tests sur des instances de différents problèmes distincts : Les mdds introduites dans [Cheng and Yap, 2010], les nonogrammes [Pesant et al., 2012], les Bdds, les mots croisés et les problèmes
<table><caption>Table 3: Le temps CPU (en secondes) pour quelques instances résolues avec MAC. Les ratios et le temps CPU de compression pour STR<sup>c</sup> sont donnés entre parenthèses.</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 (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 (43.776% - 11.511)</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 (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 (82,643% - 1.164)</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 (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 (20.134% - 0.5)</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 (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 (95.7% - 7.948)</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 (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 (57.469% - 19.383)</td></tr></tbody></table>

aléatoires. Les résultats figurent en table 3.2 ; l'heuristique dom/ddeg est utilisée pour garantir le même parcours d'arbre (dom/wdeg est plus versatile).

L'algorithme STR<sup>c</sup> permet une économie spatiale d'au moins 50% par rapport à STR1 et STR2, et jusqu'à un facteur 4 par rapport à STR3. Nous décrivons le temps CPU ainsi que le ratio de compression et le temps de compression. Lorsqu'on considère le temps de recherche, il apparaît que STR<sup>c</sup> rivalise avec STR1, mais reste toutefois supplanté par STR2.

## STR-slice: Les contraintes table fragmentées

Dans la première approche, nous avons défini un motif comme un séquence de valeurs consécutives. Bien que cette définition nous ait permis d'obtenir une réduction importante de la complexité spatiale, la forme compressée de la contrainte table présente quelques inconvénients particulièrement pendant le processus de filtrage nous empêchant d'utiliser les variantes optimisées de STR. Pour chaque test de validité d'un tuple, il est nécessaire de réitérer sur toutes ses valeurs (si nous ne sommes pas dans le cas de réutiliser les résultats précédemment faits et enregistrés). Ces inconvénients sont dus à la définition du motif : un motif pourrait impliquer des variables différentes selon sa position dans le tuple.

Pour pouvoir profiter de variantes STR optimisées, nous avons proposé dans cette seconde approche une nouvelle définition du motif et, ainsi, une nouvelle forme compressée des contraintes table à l'intermédiaire des technique de fouilles
de données.

Un **motif** $\mu$ d'une contrainte $c$ est une instanciation $I$ d'un sous ensemble de variables de $c$. On note $scp(\mu)$ sa portée, qui est $vars(I)$, $|\mu|$ sa longueur, qui est égale à $|scp(\mu)|$, et $nbOcc(\mu)$ son nombre d'occurrences dans $rel(c)$, qui est $|\{\tau \in rel(c) | \mu \subseteq \tau\}|$.

Une **sous-table** $T$ associée à un motif $\mu$ d'une contrainte $c$ est la table obtenue en ne conservant que les tuples de $c$ qui contiennent $\mu$ et en effaçant $\mu$ dans chacun de ces tuples.

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

La portée de $T$ est $scp(T) = scp(c) - scp(\mu)$

Un **fragment** d'une contrainte $c$ est un couple $(\mu, T)$ tel que $\mu$ est un motif de la contrainte $c$ et $T$ est la sous-table associée au motif $\mu$.

Comme l'ensemble des tuples représentés par un fragment $(\mu, T)$ représente en fait le produit cartésien de $\mu$ par $T$, nous allons également utiliser la notation $\mu \otimes T$ pour désigner un fragment d'une contrainte. Après le processus de fragmentation d'une contrainte, l'ensemble des tuples qui ne sont associés à aucun motif sont regroupés dans un *fragment par défaut* noté $(\emptyset, T)$

Le motif $\mu=(x_1 = a, x_4 = c, x_5 = a)$ de la contrainte $c$, détecté en figure 3.16(a), apparaît dans les tuples $\tau_2, \tau_3$ et $\tau_7$. Donc le fragment résultant est composé du motif $\mu$ et sa sous-table correspondante extraite de $c$, comme décrit en figure 3.16(b).

<figure><img src="image_8.png" /><figcaption>Figure 5: Un exemple de fragment de contrainte.</figcaption></figure>

Le test de validité sur les tuples (classiques ou bien compressés) est une opération très importante dans les algorithmes de filtrage pour les contraintes table. Pour les contraintes table fragmentée, nous étendons la notion de validité à un fragment d'une contrainte.

Un fragment $(\mu, T)$ est *valide ssi* il existe au moins un tuple du produit cartésien $\mu \otimes T$ qui soit valide. De ce fait, un fragment est *valide ssi* son motif est valide et sa *sous-table* correspondante contient au moins un *sous-tuple* valide.
**Méthode de compression** Plusieurs algorithmes de fouille de données, tels que Apriori [Agrawal and Srikant, 1994] et FP-Growth [Han et al., 2000], peuvent être utilisés pour identifier les motifs les plus fréquents. Dans le cadre de notre approche, nous n'avons pas besoin d'identifier chaque motif fréquent possible mais seulement ceux qui sont utiles pour la compression, et en particulier au plus un motif par tuple. La construction d'un *FP-Tree* (*Frequent-Pattern Tree*) qui est la première étape dans l'algorithme *FP-Growth* est particulièrement bien adaptée à cet objectif car elle identifie chaque motif long et fréquent. Cette construction ne nécessite que trois parcours de la table de la contrainte.

Nous expliquons brièvement la construction d'un *FP-Tree* dans notre contexte de compression de table, en utilisant la contrainte donnée par la table 3.16(a). L'algorithme prend comme paramètre *minSupport* qui est le nombre minimal d'occurrences d'un motif pour qu'il soit considéré comme fréquent. Dans notre exemple, nous allons utiliser *minSupport= 2* pour identifier les motifs qui apparaîssent au moins deux fois.

Dans une première étape, nous collectons le nombre d'occurrences de chaque valeur. Par abus de langage, nous appellerons *fréquence* le nombre d'occurrences d'une valeur. Cette étape nécessite un parcours de la table. Le résultat sur notre exemple est donné par la figure 6(a). Ensuite, lors d'un deuxième parcours, nous trions l'ensemble des tuples par ordre décroissant de fréquence des valeurs. Le résultat est donné par la figure 6(b) où la fréquence d'une valeur est donnée entre parenthèses. Les valeurs qui ont une fréquence en dessous du seuil *minSupport* sont retirées du tuple (elles sont identifiés en caractères gras) parce qu'ils ne peuvent pas apparaître dans un motif fréquent. Une fois le tuple trié et éventuellement réduit, il est inséré dans le FP-Tree qui est essentiellement un arbre de préfixe où chaque branche représente la partie fréquente d'un tuple et chaque nœud contient le nombre de branches qui partagent ce nœud. Chaque arête liant un parent à son enfant est étiquetée avec une valeur. Le nœud racine n'est pas étiqueté. La figure 7(a) représente le FP-Tree obtenu sur notre exemple. Le premier tuple inséré dans l'arbre est le début de $\tau_1$ qui est $(x_1 = c, x_3 = c, x_5 = c)$. Cela crée la branche la plus à gauche de l'arbre. Chaque nœud de cette branche a initialement une fréquence de 1. Le deuxième tuple inséré est $(x_4 = c, x_5 = a, x_1 = a, x_2 = a, x_3 = b)$ qui crée la troisième branche à gauche dans l'arborescence (chaque nœud ayant une fréquence de 1 à cette étape). Lorsque $\tau_3$ est insérée, la nouvelle branche $(x_4 = c, x_5 = a, x_1 = a, x_2 = c, x_3 = b)$ partage ses trois premières arêtes avec la dernière branche. De ce fait, les fréquences des nœuds correspondants sont incrémentées à 2. Les autres tuples sont insérés de la même façon. Finalement, les nœuds ayant une fréquence en dessous du seuil *minSupport* sont supprimés. L'arbre restant est représenté avec des lignes épaisses et entouré par une ligne en pointillés sur la figure 7(a). Il faut maintenant identifier les motifs du FP-tree qui sont utiles pour la compression. Chaque nœud de l'arbre correspond à un motif fréquent $\mu$ qui peut être lu sur
<table><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><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>

(a) Les fréquences.

<table><tbody><tr><th>τ<sub>1</sub></th><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><th>τ<sub>2</sub></th><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><th>τ<sub>3</sub></th><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><th>τ<sub>4</sub></th><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><th>τ<sub>5</sub></th><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><th>τ<sub>6</sub></th><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><th>τ<sub>7</sub></th><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></tbody></table>

(b) Les tuples triées selon un ordre décroissant de fréquence.

<caption>Figure 6: Les deux première étapes de compression.</caption>

le chemin menant de la racine au nœud lui-même. La fréquence $f$ de ce motif est donnée par le nœud lui-même. Les gains qui peuvent être obtenus par la factorisation de ce motif fréquent est $|\mu| \times (f - 1)$ valeurs (on peut supprimer toutes les occurrences du motif, sauf une). Dans notre exemple, pour la première branche en gras, nous pouvons voir qu’en utilisant le motif $(x_4 = c, x_5 = a)$, nous gagnons six valeurs, avec le motif $(x_4 = c, x_5 = a, x_1 = a)$ nous gagnons également 6 valeurs tandis qu’on ne gagne que 4 valeurs avec la branche complète $(x_4 = c, x_5 = a, x_1 = a, x_2 = c)$. Par conséquent, nous réduisons l’arbre en supprimant les nœuds qui offrent un gain moindre que leur père. Les feuilles de l’arbre obtenu représentent les motifs fréquents utilisé dans notre compression : $(x_4 = c, x_5 = a, x_1 = a)$ et $(x_2 = a, x_1 = b)$. Pour terminer, nous créons un fragment pour chaque motif fréquent que nous avons identifié. Ces fragments seront remplis lors d’un dernier parcours de la contrainte. Pour chaque tuple, nous utilisons le FP-tree pour identifier si le tuple (trié) commence par un motif fréquent. Dans ce cas, nous ajoutons le reste du tuple à la sous-table correspondante. Les tuples qui ne commencent pas par un motif fréquent sont ajoutés au fragment par défaut.

L’algorithme 27 résume les différentes étapes du processus de compression.

**Algorithme de filtrage** Afin d’appliquer GAC sur les contraintes table fragmentées, notre idée est d’adapter la technique (STR), et plus précisément la variante STR2 optimisée. Comme une contrainte table fragmentée est composée de plusieurs fragments, chacune composée d’un motif et d’une sous-table, le processus de filtrage que nous proposons agit à deux niveaux distincts. Au niveau
<figure><img src="image_9.png" /><figcaption>(a) L'arbre des péfixes fréquents (FP-tree).</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(b) Table compressée.</figcaption></figure>

<caption>Figure 7: FP-tree et la table compressée.</caption>

haut, la validité de chaque fragment est déterminée, et au niveau bas, la validité de chaque couple (motif, sous-tuple) est vérifiée. Rappelons qu’un fragment est valide ssi à la fois son motif est valide et au moins un sous-tuple de la sous-table est valide (voir la définition).

Une contrainte table fragmentée $c$ est représentée par un tableau `entries[c]`
<caption>**Algorithm 2:** compress-STR-slice(c: Constraint, minSupport: float)</caption>

```c
// 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     // Second scan: build FP-Tree
7     foreach τ ∈ table(c) do
8       // sorting τ and removing values less frequent than minSupport
        τ ← sortTuple (τ, frequencies, minSupport)
        // insert τ into FP-Tree by updating nodes frequency
        addTuple(root(FP-Tree),τ)
9       // removing nodes less frequent than minSupport or such that
        |μ| × (f − 1) is smaller than for their parents
10 pruneTree(root(FP-Tree),minSupport,0)
11 // Third scan: compress c
12 foreach τ ∈ table(c) do
13   μ ← searchPattern(root(FP-Tree),τ)
14   if μ ≠ nil then
15     entry ← getEntry entries[c],μ)
16     if entry = nil then
17       // There is no entry for this pattern
18     entry ← addEntry entries[c],μ)
19   addSubTuple entry,τ \ μ)
20 else
21   addSubTuple defaultEntry,τ)
```

de *p* fragments. La gestion des fragments valides, appelés fragments *courants* <fnref n="1" />, est effectuée comme suit :

* entriesLimit[c] est l'indice du dernier fragment courant dans entries[c]. Les éléments de entries[c] aux indices allant de 1 à entriesLimit[c] sont les fragments courants de c.

<footnote n="1">¹Les fragments courants correspondent aux fragments valides obtenus comme résultat du dernier appel de l’algorithme.</footnote>
* la suppression d'un fragment (qui est devenu invalide) à l'indice *i* est faite par l'appel à la fonction removeEntry(*c*, *i*). Cet appel effectue une permutation entre les fragments d'indice *i* et *entriesLimit[*c*], puis décrèmenté *entriesLimit[*c*]. Notez que l'ordre initial de fragments n'est pas conservé.

* La restauration d'un ensemble de fragments se fait simplement en changeant la valeur de *entriesLimit[*c*].

Chaque fragment de *entries* peut être représenté comme un enregistrement composé d'un champ *pattern* et un champ *subtable*. Plus précisément :

* le champ *pattern* enregistre une instanciation partielle $\mu$, et peut être représenté en pratique comme une structure composée de deux tableaux : un pour les variables, la portée du motif, et l'autre pour les valeurs.

* la structure *subtable* stocke une sous-table *T* et peut être représentée en pratique comme une structure composée de deux tableaux : un pour les variables, à savoir la portée de la sous-table *T*, et d'autre part, un tableau à deux dimensions, pour les sous-tuples.

Dans notre présentation, nous allons traiter directement $\mu$ et *T* sans tenir compte de tous les détails d'implantation. Par exemple, *T* sera considéré comme un tableau à deux dimensions. La gestion de l'ensemble des sous-tuples valides, appelés sous-tuples *courants* de *T*, est réalisée comme suit :

* $limit[T]$ est l'indice du dernier sous-tuple courant dans *T*. Les éléments de *T* aux indices allant de 1 à $limit[T]$ sont les sous-tuples courants de *T*.

* la suppression d'un sous-tuple (qui est devenu invalidé) à l'indice *i* est effectuée par un appel à la fonction removeSubtuple(*T*, *i*). Cet appel effectue une permutation entre les sous-tuples à indices *i* et $limit[T]$, puis décrèmenté $limit[T]$. Notez que l'ordre initial de sous-tuples n'est pas conservé.

* la restauration d'un ensemble de sous-tuples se fait simplement en changeant la valeur de $limit[T]$.

Notez que la gestion des fragments courants et sous-tuples courants utilise les mêmes principes que ceux de STR. En outre, comme dans [Lecoutre, 2011], nous utilisons deux ensembles de variables, appelés $S^{val}$ et $S^{sup}$. L'ensemble $S^{val}$ contient des variables non affectées (et éventuellement, la dernière variable asignée) dont les domaines ont été réduits depuis le dernier appel de l'algorithme de filtrage sur *c*. Pour configurer $S^{val}$, nous avons besoin d'enregistrer la taille du domaine de chaque variable *x* juste après l'exécution de STR-slice sur *c* : cette valeur est enregistrée dans $lastSize[*x*]. L'ensemble $S^{sup}$ contient des variables
non affectées de la contrainte *c* dont les domaines contiennent chacun au moins
une valeur pour laquelle un support doit être trouvé. Ces deux ensembles perme-
ttent de restreindre les itérations sur les variables à celles qui sont uniquement
pertinentes. Nous utilisons également un tableau *gacValues*[*x*] pour chaque
variable *x*. A tout moment, *gacValues*[*x*] contient toutes les valeurs de dom(*x*)
pour lesquelles un support a déjà été trouvé : par conséquent, les valeurs d'une
variable *x* pour lesquelles on n'a pas trouvé de support sont exactement ceux de
dom(*x*) \ *gacValues*[*x*]. Notez que les ensembles *S*<sup>val</sup> and *S*<sup>sup</sup> sont initialement
définis par rapport à la portée de *c*. Cependant, pour chaque sous-table, nous
aussi allons utiliser des ensembles locaux *S*<sup>lval</sup> et *S*<sup>lsup</sup> de *S*<sup>val</sup> et *S*<sup>sup</sup> comme
expliqué plus loin.

L'algorithme 30 est une procédure de filtrage, appelé STR-slice, qui établit
GAC sur une contrainte table fragmentée *c* appartenant à un CN *N*.

**Résultats expérimentaux** Dans la table 3.6, nous comparons les comportements respectifs de STR1, STR2, STR3, MDD et STR-slice sur différentes instances <fnref n="2" /> impliquant des contraintes table positives d'arité supérieure à 2. Nous utilisons MAC avec *dom/ddeg* comme choix d'ordonnancement des variables et *lexico* comme heuristique de choix de valeur, pour résoudre tous ces problèmes. Une observation générale de cette expérimentation préliminaire est que STR-slice concurrence STR2 et STR3, sans toutefois l'emporter clairement.

L'utilisation de la La cohérence d'arc singleton
en parallèle pour l'amélioration de la recherche

Notre approche est basée sur une architecture de maître/esclaves où le maître est un solveur CSP séquentiel et les différents esclaves aident leur maître durant le processus de la recherche. Ce solveur principal transmet son instantiation courante à ses esclaves qui essayeront de déduire des informations pertinentes en exploitant des niveaux différents de cohérence. Dès que de nouveaux faits sont découverts, ils sont transmis au solveur principal qui les prend en compte dès que possible. Notre but est de minimiser la synchronisation entre le solveur principal et les esclaves. Dans notre approche, le solveur principal et les différents esclaves utilisent des cœurs différents du même hôte.

La cohérence d'arc singleton (SAC) [Debruyne and Bessiere, 1997] est une cohérence forte trop lourde à établir pendant la recherche [Lecoutre and Prosser, 2006]. Par contre, dans une solveur parallèle les cœurs disponible peuvent effectuer ces tests SAC gratuitement ( du point de vue wall-clock). Les littéraux que l'on découvre SAC incohérent sont transmis au maître pour les éviter dans ses décisions futures.

<footnote n="2">²disponibles sur http://www.cril.univ-artois.fr/CSC09.</footnote>
<caption>**Algorithm 3:** STR-slice(c: constraint):set of variables</caption>

```c
// Initialization of sets S^val and S^sup, as in STR2
1 S^val ← ∅
2 S^sup ← ∅
3 if lastPast(P) ∈ scp(c) then
4   S^val ← S^val ∪ {lastPast(P)}
5   foreach variable x ∈ scp(c) | x /∈ past(P) do
6     gacValues[x] ← ∅
7     S^sup ← S^sup ∪ {x}
8     if |dom(x)| ≠ lastSize[c][x] then
9       S^val ← S^val ∪ {x}
10      lastSize[c][x] ← |dom(x)|
// Iteration over all entries of c
11 i ← 1
12 while i ≤ entriesLimit[c] do
13   (μ, T) ← entries[c][i] // ith current entry of c
14   if isValidPattern(μ) and then scanSubtable(T) then
15     foreach variable x ∈ scp(μ) | x ∈ S^sup do
16       if μ[x] /∈ gacValues[x] then
17         gacValues[x] ← gacValues[x] ∪ {μ[x]}
18       if |dom(x)| = |gacValues[x]| then
19         S^sup ← S^sup \ {x}
20     i ← i + 1
21   else
22     removeEntry(c, i) // entriesLimit[c] decremented
// domains are now updated and X_evt computed, as in STR2
23 X_evt ← ∅
24 foreach variable x ∈ S^sup do
25   dom(x) ← gacValues[x]
26   if dom(x) = ∅ then
27     throw INCONSISTENCY
28   X_evt ← X_evt ∪ {x}
29   lastSize[c][x] ← |dom(x)|
30 return X_evt
```

La figure 4.1 décrit l'architecture de notre approche. En fait, chaque maître et esclaves ont leur propre copie du problème. Le maître résout le problème tandis
<table><caption>Table 4: Le temps CPU sur quelques instances.</caption><thead><tr><th>Instance</th><th>STR1</th><th>STR2</th><th>STR3</th><th>MDD</th><th>STR-slice</th></tr></thead><tbody><tr><td>a7-v24-d5-ps0.5-psh0.7-9</td><td>879</td><td>334</td><td>367</td><td><strong>25.5</strong></td><td>200 (69% - 5.41)</td></tr><tr><td>a7-v24-d5-ps0.5-psh0.9-6</td><td>353</td><td>195</td><td>324</td><td><strong>16.6</strong></td><td>174 (62% - 5.82)</td></tr><tr><td>bdd-21-2713-15-79-11</td><td>78.5</td><td><strong>23.5</strong></td><td>48.5</td><td>82.6</td><td>31.7 (88.05% - 0.28)</td></tr><tr><td>crossword-ogd-vg12-13</td><td>799</td><td>342</td><td><strong>208</strong></td><td>> 1,200</td><td>242 (73.46% - 0.74)</td></tr><tr><td>crossword-uk-vg10-13</td><td>1,173</td><td><strong>576</strong></td><td>589</td><td>> 1,200</td><td>598 (89.63% - 0.48)</td></tr></tbody></table>

que les esclaves établissent SAC sur quelques littéraux du problème. Une *pile de décisions* est associée à chaque maître et esclave. Le maître stocke toutes les décisions positives et négatives faites dans sa propre *pile de décisions* tandis que les esclaves les copient seulement dans leurs piles, chaque fois qu'il y a de nouvelles décisions. Cette pile décrit l'état du problème de chaque entité. Tous les esclaves testent la cohérence des littéraux qui sont stockés dans la *file de littéraux* qui est une structure de données partagée entre tous les acteurs. Établir la cohérence SAC sur ces littéraux produit de nouveaux faits, de nouveaux messages sont alors transférés dans la *file de messages* qui est une structure de données partagée entre le maître et les esclaves. Le maître à son tour extrait des messages de la *file de messages* pour les exploiter dans son processus de résolution en évitant ainsi des échecs.

**La pile de décisions** La pile de décision stocke toutes les décisions faites par le solveur. Elles peuvent être positives (assignation) ou négatives (réfutation). Chaque décision positive définit un niveau auquel correspond un horodatage qui indique l'instant ou cette décision a été prise. Cet horodatage est obtenu par un compteur global qui est initialisé à 0 et incrémenté chaque fois qu'une décision est prise. Ces informations sont utilisées pour identifier les modifications de la pile de décision. En fait, un horodatage est seulement associé aux décisions positives qui est une caractéristique du solveur AbsCon [Lecoutre and Tabary, 2007]. Des décisions positives sont stockées dans la pile dans un ordre consécutif. Quand un retour arrière est effectué, la valeur causant l'échec est supprimée du domaine de sa variable et cette réfutation est ajoutée au niveau précédent.

Les esclaves obtiennent initialement une copie $\mathcal{P}'$ du problème $\mathcal{P}$ qui est traité par le maître (des variables, des domaines, des contraintes). Pour atteindre le même état de recherche que le maître, les esclaves peuvent soit copier le nouvel état du problème ou obtenir seulement l'ensemble des décisions faites jusqu'ici et les ré-appliquer de nouveau. En fait, dans une itération, ils copient d'une manière incrémentale la pile de décisions du maître (c'est-à-dire la liste de décisions prises
<figure><img src="image_11.png" /><figcaption>Figure 8: Vue d'ensemble de l'architecture.</figcaption></figure>

par le maître), reproduisent le filtrage fait par le maître après ces décisions pour atteindre le même état que le maître et exécutent ensuite leur propre cohérence. La copie progressive de la pile de décisions consiste, d'abord, à identifier la partie de la pile qui est identique dans le maître et dans la copie de l'esclave et ensuite la reproduction de chaque décision prise par le maître après cette partie commune. L'esclave obtient d'abord l'indicateur de pile actuel du maître et identifie ensuite la dernière décision qui a le même horodatage que le maître. Alors, l'esclave
copie chaque décision du maître à partir de cette dernière décision commune. Puisque le maître peut effectuer un retour arrière entre temps, l'esclave vérifie alors que la dernière décision qu'il a copiée ait toujours le même horodatage que dans le maître. Si ce n'est pas le cas, le maître a fait un retour arrière pendant la copie et l'esclave reprend sa copie de la pile de décisions.

**La file de messages** Une fois qu'un esclave a une copie stable de l'état du maître, il choisit un nouveau littéral (x, a) dans la file globale de littéraux et vérifie si le littéral (x, a) est SAC-cohérent. Si ce n'est pas le cas, l'esclave produit un message contenant l'information x ≠ a et son niveau de décision actuel et un horodatage où ces informations ont été déduites. Le message est stocké dans la *file de Messages*. Le maître extraira ces informations quand il est prêt à les l'utiliser. Après que le test SAC a été effectué sur un littéral (x, a), il est remis à la file de littéraux, en mettant à jour sa priorité, pour tester à nouveau sa cohérence plus tard. L'algorithme 36 illustre l'établissement de la cohérence SAC sur l'ensemble de littéraux de la file de littéraux.

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

1. `valueFound` ← `false`
2. `while` $\neg valueFound$ `do`
3. &nbsp;&nbsp;&nbsp;&nbsp;literal ← `getLiteral(literalsQueue)`
4. &nbsp;&nbsp;&nbsp;&nbsp;`if` $\neg assigned(literal.var)$ `and$ |dom(literal.var)| > 1$ `then`
5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`valueFound` ← `true`
6. &nbsp;&nbsp;&nbsp;&nbsp;`else`
7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;literal.countdown --
8. &nbsp;&nbsp;&nbsp;&nbsp;`insert` literal to `literalsQueue`

// while the problem is not solved, there is always a value to test
9. `assign` literal.val to literal.var
10. `consistent` ← `GAC(P, literal.var)`
11. `backtrack()`
    // going back to the previous level in order to test more pairs
12. `if` $\neg consistent$ `then`
13. &nbsp;&nbsp;&nbsp;&nbsp;literal_priority++
14. &nbsp;&nbsp;&nbsp;&nbsp;`putMessage(currentLevel, timeStamp(level], literal)`
    // Putting the inferred result in the queue of messages
15. literal.countdown --
16. `insert` literal to `literalsQueue`
Avant qu'une décision ne soit prise, le maître vérifie si quelques informations ont été déduites par les autres esclaves. Ceci est fait en vérifiant le contenu de la file de messages, qui est lue par le maître et écrite par les esclaves. Quand un message est extrait de cette file, le maître vérifie, en premier lieu, si l'inférence est toujours cohérente par rapport à l'état actuel du solveur. Si le message n'est pas cohérente, il est ignoré. Autrement, l'inférence est prise en compte.

En fait, un message contient deux informations principales :

* le littéral : la paire (variable, valeur) pour éviter dans des assignations futures;

* (niveau, horodatage) : le niveau de la paire (dans l'arbre de recherche) et son horodatage dans lequel la propriété "le littéral est SAC-incohérent" est toujours pertinente.

Les algorithmes 34 et 35 décrivent la gestion des messages par le maître. L'algorithme 35 illustre le processus d'extraction des messages par le maître avant chaque décision prise. La validité du message est retournée par la fonction 34. Une fois que le maître vérifie que le message est toujours pertinent, il le stocke dans sa propre structure de données, appelée setOfInferences. En fait, setOfInferences est une table où setOfInferences[i] définit les messages extraits et utilisés au niveau i. Grâce à cette structure de données, le maître peut réutiliser ces inférences dans des niveaux plus hauts, quand un retour arrière est effectué.

<caption>**Algorithm 5:** isValidMessage(msg: Message): Boolean</caption>

1. **if** msg.level ≤ currentLevel **and** msg.timeStamp = timeStamp(msg.level] **then**
2. **return** true // the message msg is still relevant
3. **return** false

**La file de littéraux** Pour exécuter les différents tests SAC, les littéraux du problème sont regroupés dans une *file de Littéraux*. Les différents esclaves coopèrent pour examiner chaque littéral possible aussi souvent que possible. Puisque quelques littéraux vont plus probablement devenir SAC-incohérent, nous utilisons des priorités pour tester ces littéraux plus souvent que les autres. Donc, pour chaque littéral dans la *file de Littéraux* correspond une priorité, qui est incrémentée quand le littéral est identifié comme SAC-incohérent (voir la ligne 13 de l'algorithme 36). Pour gérer cette priorité nous utilisons l'algorithme Completely Fair Scheduling (CFS) [Li et al., 2009] qui assure l'exécution du processus ayant utilisé le minimum de temps en premier lieu et donc les processus sont ordonnés en fonction du temps d'exécution utilisé.
<caption>**Algorithm 6:** applyMessages(*hasBacktracked*: Boolean)</caption>

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*]
&nbsp;&nbsp;&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*

**Amélioration de la recherche** L'algorithme 37 décrit l'algorithme de recherche utilisé par le maître. En fait, nous utilisons l'algorithme de recherche classique MAC. En plus, on intègre l'extraction de message (ligne 4): un appel à l'algorithme 35 est effectué pour pouvoir tirer profit des faits découverts par l'ensemble des esclaves. De cette manière, les valeurs SAC-incohérents sont supprimés de leurs domaines respectifs en vue de les éviter dans les prochaines décisions.

**Résultats expérimentaux** Les tables 4.2 et 4.4 illustrent les temps moyens (en wall clock) pour quelques séries d'instances en utilisant respectivement les heuristiques *dom/wdeg* et *dom/ddeg*.

Contrairement à nos attentes, notre approche semble être moins efficace que l'algorithme de recherche le plus utilisé MAC. Ceci pourrait être dû au fait que les valeurs incohérentes sont, en fait, facilement déduites et par la suite supprimées par le maître par la propagation. Ceci implique que les informations envoyées ne sont pas aussi fortes que nos attentes pour pouvoir accélérer la recherche de maître. L'heuristique de choix de variable pourrait être aussi la raison derrière l'échec de notre approche. En fait, une analyse approfondie montre que même dans une résolution séquentielle établissant une cohérence forte gratuitement ne peut pas impliquer une réduction importante de l'espace de recherche ce qui explique les résultats obtenus par notre approche.
<caption>**Algorithm 7:** solveProblem(*P*: Constraint network)</caption>

1 finished ← false
2 hasBacktracked ← false
3 while ¬finished do
4     // infer all not used messages
5     applyMessages hasBacktracked
6     // select new pair (variable,value) to assign
7     var ← getNextVariable (variableOrderingHeuristic)
8     val ← getNextValue (valueOrderingHeuristic, var)
9     assign var to val
10    levelBeforeBacktrack ← |past(P)|
11    consistent ← checkConsistencyAfterAssignment (P)
12    if consistent and |past(P)| = n then
13        display solution
14        finished ← true
15    else
16    while ¬consistent do
17        backtrack ()
18        hasBacktracked ← true
19        remove val from dom (var)
20        consistent ← checkConsistencyAfterRefutation (P)
<table><caption>Table 5: Le temps wall claox moyen pour des séries d'instances en utilisant l'heuristique 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>

<table><caption>Table 6: Le temps wall claox moyen pour des séries d'instances en utilisant l'heuristique 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>

## Conclusion

Cette thèse s'articule autour des techniques d'optimisation de la résolution des CSPs en raisonnant sur plusieurs axes.

Dans la première partie, nous traitons la compression des contraintes table. Vu l'expressivité offerte par ces contraintes aux utilisateurs non experts, son utilisation est courante dans le monde industriel. Au fil du temps, le volume des
données manipulées ne cesse d'augmenter ce qui implique l'utilisation de struc-
tures de données compactes pour les stocker, et aussi des algorithmes de filtrage
optimisés pour les gérer pendant le processus de résolution. Dans cette thèse,
nous proposons deux méthodes différentes pour la compression des contraintes de
table. Les deux approches sont basés sur la recherche des motifs fréquents pour
éviter la redondance. Cependant, la façon de définir un motif, la détection des
motifs fréquents et la nouvelle représentation compacte diffère significativement.
Les résultats expérimentaux montrent que l'approche STR<sup>c</sup> permet d'avoir une
compression importante, mais comparée aux variantes STR il rivalise seulement
avec STR1. Quant à STR-slice, les expérimentations montrent des résultats
plus compétitifs où STR-slice supplante STR2 et parfois STR3 malgré qu'elle
est pénalisée parfois par le coût de compression.

La seconde partie est consacrée à une autre façon d'optimiser la résolution
de CSP qui est l'utilisation d'une architecture parallèle. Nous proposons une
méthode où nous utilisons une architecture parallèle pour améliorer le processus
de résolution en établissant des cohérences parallèles. En fait, les esclaves en-
voient à leur maître le résultat obtenu après avoir établi la cohérence partielle
en tant que nouveaux faits. Le maître, à son tour essaye de profiter d'eux en
enlevant les valeurs correspondantes. Contrairement à ce qu'on pensait, le travail
fait par les esclaves n'implique pas d'amélioration significative du processus de
résolution.
Introduction

Constraint Programming (CP) is a powerful paradigm used for modeling and solving combinatorial constraint problems that relies on a wide range of techniques coming from artificial intelligence, operational research, graph theory, ..., etc. The basic idea of constraint programming is that the user expresses its constraints and a constraint solver seeks a solution. A constraint expresses a restriction on the combinations of possible values assigned to variables. A constraint network is defined by a set of variables, each one with its own domain, and by a set of constraints. CP can be used for the most of our daily problems such as Scheduling problems. For example, in order to make a school schedule, we should take into consideration various constraints such as professors and classrooms availability. In the Information Technology (IT) field, "*Constraint programming is an advance that IT has ever done that is closest to the Holy Grail of programming: the user defines the problem, the computer solves it.*" Eugene C. Freuder.

Constraint satisfaction problems (CSP) [Montanari, 1974], is a framework at the heart of CP problems. They correspond to decision problems where we seek for states or objects satisfying a number of constraints or criteria. These decision problems have two answers to the question they encode: *true*, if the problem admits a solution, *false*, otherwise. CSPs are the subject of intense research in both artificial intelligence and operations research. Many CSPs require the combination of heuristics and combinatorial optimization methods to solve them in a reasonable time.

Solving CSP instances can quickly become difficult when the order of problem instances grow. Solvers are composed of two important components: "search" and "inference". In fact, the "inference" mechanism refers to making deductions, whereas, the "search" mechanism consists in building a solution by extending iteratively a partial solution. In order to build a solution, or to prove that no solution exists, a solver alternates between search and inference. It makes a new decision to extend a partial solution and then makes as many deductions as possible. Deductions could be, for example, removing all values that could not appear in a solution. When there are no more deductions that
could be inferred from the last decision, the solver makes a new decision. In
fact, the decision is made with respect to a given heuristic, i.e., the solver
assigns a value to a variable chosen by the heuristic supposing that this choice
could speed up the search or lead to a solution. This is not always the case,
that is the reason why the solver could return back to the previous decisions,
concluding that the last decision leads to a failure and, thus, no solution could
be found from there.

With the improvement of computers, larger and larger problems can be
solved. However, the size of industrial problems grow faster which requires a
vast amount of memory space to store them and entail great difficulties to solve
them. In the late decades, different works were proposed in order to deal with
large problems.

On the one hand, several approaches were proposed in order to
reduce the memory space required to represent constraints and, in
particular, table constraints which are an extensional form of con-
straints. Different approaches use compact data structures to represent
table constraints such as Tries [Gent et al., 2007], Multi-valued Deci-
sion Diagrams (MDDs) [Cheng and Yap, 2010] and Deterministic Fi-
nite Automata (DFA) [Pesant, 2004]. Others proposed new compact
representations such as Compressed tuples [Hubbe and Freuder, 1992],
Short supports [Nightingale et al., 2011, Nightingale et al., 2013],
Smart tuples [Mairy et al., 2015] and Data-mining based approaches
[Jabbour et al., 2013a, Jabbour et al., 2013b].

On the other hand, different approaches were proposed in order
to speed-up the resolution time. We distinguish the use of paral-
lel computing. The problem is then solved using different cores. We
distinguish different techniques such as Work Sharing [Schulte, 2000,
Régin et al., 2013, Régin et al., 2014], Work Stealing [Sleep, 1981,
Kotthoff and Moore, 2010, Kotthoff and Moore, 2010, Chu et al., 2009],
Multi-Agent Search [Rao and Kumar, 1988, Bordeaux et al., 2009] and Port-
folios [Gomes and Selman, 2001, O'Mahony et al., 2008, Amadini et al., 2015,
Dasygenis and Stergiou, 2014].

## Outline

In this thesis, we focus on *Constraint Satisfaction Problems* and, in particular,
the different techniques used to reduce both the required memory space and the
resolution time. The thesis is organized as follows:

* In **Chapter 1**, we introduce the background for constraint satisfaction
problems (CSP) that we use in this thesis. We present, then, various consistencies and the algorithms used to enforce such consistencies. Furthermore, we describe different search algorithms such as *Look-back* approaches, *Look-ahead* approaches and *Maintaining Arc Consistency* search algorithm. Finally, we present some heuristics that are used to guide the search to the most promising research areas.

* Chapter 2 is divided into two main parts. In a first place, we investigate different representations of table constraints and the used algorithms to filter them. In a second place, we introduce the background for parallel computing that we use in this thesis. We present, then, various approaches of constraint programming using parallel computing.

* In Chapter 3, 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. For each approach we describe the compression method used to obtain the new form of table constraints and also the filtering algorithm used during search. The first work STR<sup>c</sup>[Gharbi et al., 2013] was presented at *JFPC 2013* and *CP 2013* (Doctoral Program). The second work STR-*slice* [Gharbi et al., 2014] was presented at *CPAIOR 2014*.

* In Chapter 4, we give a new approach for solving a CSP instance by enforcing consistencies in parallel. In fact, 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.
# Part I

## Background
# Chapter 1

## Constraint Satisfaction Problem

### Contents

<table><tbody><tr><td>1.1</td><td>Introduction to CSP</td><td>41</td></tr><tr><td>1.1.1</td><td>Definitions</td><td>41</td></tr><tr><td>1.1.2</td><td>Complexity</td><td>45</td></tr><tr><td>1.1.3</td><td>Example of a CSP: Map coloring</td><td>46</td></tr><tr><td>1.1.4</td><td>Solvers</td><td>48</td></tr><tr><td>1.2</td><td>Consistency</td><td>48</td></tr><tr><td>1.2.1</td><td>Definitions</td><td>48</td></tr><tr><td>1.3</td><td>Generalized Arc Consistency (GAC)</td><td>50</td></tr><tr><td>1.3.1</td><td>Arc Consistency</td><td>51</td></tr><tr><td>1.3.2</td><td>GAC for Table Constraints</td><td>55</td></tr><tr><td>1.4</td><td>Singleton Arc Consistency(SAC)</td><td>61</td></tr><tr><td>1.4.1</td><td>Definitions</td><td>62</td></tr><tr><td>1.4.2</td><td>SAC1</td><td>63</td></tr><tr><td>1.4.3</td><td>Weak k-SAC</td><td>64</td></tr><tr><td>1.5</td><td>Search</td><td>64</td></tr><tr><td>1.5.1</td><td>Look-back approaches</td><td>65</td></tr><tr><td>1.5.2</td><td>Look-ahead approaches</td><td>66</td></tr><tr><td>1.5.3</td><td>Maintaining Arc Consistency (MAC)</td><td>68</td></tr><tr><td>1.6</td><td>Heuristics</td><td>69</td></tr><tr><td>1.6.1</td><td>Static Variable Ordering (SVO)</td><td>69</td></tr><tr><td>1.6.2</td><td>Dynamic Variable Ordering (DVO)</td><td>69</td></tr><tr><td>1.6.3</td><td>Adaptive Variable Ordering (AVO)</td><td>69</td></tr></tbody></table>
## 1.1. INTRODUCTION TO CSP

Constraint Programming (CP) is a framework for the representing and solving combinatorial constrained problems. In this chapter, we present the different basis of this framework. Since constraint solvers rely on “inference” and “search” techniques, we introduce both of them.

This chapter is organized as follows:

* In Section 1.1, we introduce the different features of constraint satisfaction problems;

* In Section 1.2, we describe several consistencies;

* In Section 1.3, we present Generalized Arc Consistency (GAC), the most important consistency used in constraint satisfaction and the algorithms enforcing GAC on so-called table constraints;

* In Section 1.4, we describe another consistency, Singleton Arc Consistency (SAC), and its different variants;

* In Section 1.5, we describe the most used search algorithm, called MAC, as well as many other techniques used in order to look for a solution(s);

* Finally, we present in Section 1.6 the heuristics commonly used to guide the search.

# 1.1 Introduction to CSP

## 1.1.1 Definitions

In this section, we introduce variables and constraints before defining constraint networks.

**Definition 1 (Variable)** A variable *generally denoted x* has a domain, *denoted dom(x)*, which is the set of values that can be taken by *x*. The current domain of *x* may change, but it is always included in the initial domain denoted $dom^{init}(x)$ ($dom(x) \subseteq dom^{init}(x)$).

We focus, in the context of our work, only on variables with finite domains.

A *variable* may take different states. For example, a variable can be “assigned” or “instantiated” to a value *a* from its domain (it is “unassigned”, otherwise). If the domain of a variable contains only one value, it is called a “singleton” variable.

For defining relations, we need Cartesian products.
## 1.1. INTRODUCTION TO CSP

**Definition 2 (Cartesian Product)** Let $D_1, D_2, \dots, D_r$ be a sequence of $r$ sets. The Cartesian product $D_1 \times D_2 \times \dots \times D_r$, also denoted $\prod_{i=1}^{r} D_i$, is the set $\{(a_1, a_2, \dots, a_r) | a_1 \in D_1, a_2 \in D_2, \dots, a_r \in D_r\}$.

**Example 1** We give an example of a Cartesian product built from domains of variables $x, y$ and $z$ with $dom(x) = dom(y) = dom(z) = \{a, b\}$.

$$dom(x) \times dom(y) \times dom(z) = \begin{cases} (a, a, a), & (b, a, a), \\ (a, a, b), & (b, a, b), \\ (a, b, a), & (b, b, a), \\ (a, b, b), & (b, b, b) \end{cases}$$

**Definition 3 (Relation)** A relation $R$ is defined over a sequence of $r$ sets $D_1, D_2, \dots, D_r$. $R$ is a subset of the Cartesian product $\prod_{i=1}^{r} D_i$ ($R \subseteq \prod_{i=1}^{r} D_i$).

**Example 2** $R_{xyz}$ is a relation defined over $dom(x) \times dom(y) \times dom(z)$ (introduced in Example 1).

$$R_{xyz} = \begin{cases} (b, a, a), \\ (b, a, b), \\ (a, b, a), \\ (b, b, a) \end{cases}$$

**Definition 4 (Literal)** A literal is a pair $(x, a_i)$ where $x \in \mathcal{X}$ and $a_i \in dom(x)$.

**Definition 5 (Constraint)** A constraint $c$ involves a set of variables called the scope of $c$ (denoted $scp(c)$). A constraint $c$ is semantically defined by a relation denoted $rel(c)$ that exhibits the combinations of values allowed by $c$ for all variables of its scope ($rel(c) \subseteq \prod_{x \in scp(c)} dom^{init}(x)$). The arity of a constraint $c$ is the size of $scp(c)$, and is usually denoted by $r$.

We distinguish three forms of constraints: intentional constraints, extensional constraints and global constraints.

Constraints defined in *intension* describe, *implicitly*, the relation between the variables of its scope by a predicate based on a mathematical expression or formula. A predicate maps any combination of literals to a Boolean value. The combination is allowed if the mapped Boolean value is *true*, otherwise it is forbidden. The constraint $x = y$ is such an intentional constraint.

Constraints defined in *extension*, also called table constraints, can be represented in different equivalent ways. For example:

* An explicit relation that lists the allowed or disallowed combinations of values (tuples).
## 1.1. INTRODUCTION TO CSP

**Example 3** $c_{xyz}$ is a ternary constraint represented in extension as follows:

<table><tr><td>x</td><td>y</td><td>z</td></tr><tr><td>(b, a, a)</td><td>(c, a, c)</td><td>(a, b, a)</td></tr><tr><td>(b, b, c)</td><td></td><td></td></tr></table>

* A compatibility hyper-graph $\mathcal{H}$, $\mathcal{H} = (\mathcal{V}, \mathcal{E})$, where $\mathcal{V}$ the set of vertices (nodes) define the literals and $\mathcal{E}$ the set of hyper-edges linking them. Supported pairs are related by solid hyper-edges, whereas dotted links define unsupported ones on c. A 2-uniform hyper-graph is called a graph. For simplicity, we use graphs in our examples.

**Example 4** In Figure 1.1, $c_{xy}$ is a binary constraint represented by a compatibility graph. For example, $(a, a)$ and $(c, b)$ are pairs allowed by $c_{xy}$ whereas $(b, a)$ and $(c, c)$ are disallowed ones.

<figure><img src="image_12.png" /><figcaption>Figure 1.1: The compatibility graph of constraint $c_{xy}$ such that $dom(x) = dom(y) = \{a, b, c\}$.</figcaption></figure>

Global constraints [Bessiere and van Hentenryck, 2003, Régin, 2011a] are constraints defined over an unfixed number of variables. This form of constraints facilitate the problem expression by a user providing a better view of the structure of the problem. For example, a well-known global constraint is *AllDifferent* [Régin, 1994]. This constraint means that all the involved variables must take different values, i.e. no variable can have the same value as another one. Global constraints associated with powerful filtering algorithms (presented in Section 1.3) are one of the main strengths of constraint programming.
1.1. INTRODUCTION TO CSP

**Definition 6 (Constraint network)** A finite Constraint Network (CN) *P* is a triplet < *X*, *C*, *D* > where *X* is a finite set of variables (also denoted vars(*P*)), *C* a set of constraints (also denoted cons(*P*)) such that ∀*c* ∈ cons(*P*), scp(*c*) ⊆ vars(*P*) and *D* is the domains of the variables; *D* = {dom(*x*)|*x* ∈ *X*}.

The main numerical features of a constraint network *P* are as follows:

• *n* the number of variables;

• *d* the size of the greatest domain of a variable;

• *e* the number of constraints;

• *r* the maximum arity of the constraints.

We define below instantiations and tuples.

**Definition 7 (Instantiation)** An instantiation *I* of a set of variables *S*={*x*₁, *x*₂, ..., *x*ₚ} is a set {(*x*ᵢ, *a*ᵢ) | ∀*i* ∈ [1, *r*]; *a*ᵢ ∈ dom-init(*x*ᵢ)}

The set of variables *S* involved in *I* is denoted vars(*I*) and each value *a*ᵢ is
denoted *I*[*x*ᵢ].

An instantiation *I* is valid iff $\forall (x, a_i) \in I, a_i \in \text{dom}(x)$.

**Definition 8 (Tuple)** An *r*-tuple τ on a constraint *c* such that scp(*c*) = {*x*₁, *x*₂, . . . , *x*ₚ} is a sequence of values (*a*₁, *a*₂, . . . , *a*ₚ) such that ∀*i* ∈ [1, *r*]; *a*ᵢ ∈ dom-init(*x*ᵢ). The value *a*ᵢ is denoted by τ[*x*ᵢ].

In the context of this thesis, for simplicity, we make no difference between
a tuple τ = (*a*₁, *a*₂, ..., *a*ₚ) and an instantiation I = {(*x*ᵢ, *a*ᵢ) | ∀*i* ∈ [1, *r*]; *a*ᵢ ∈ dom-init(*x*ᵢ)}. We say that I is the corresponding instantiation of τ.

**Definition 9 (Valid tuple)** An *r*-tuple τ on a constraint *c* such that scp(*c*) = {*x*₁, *x*₂, . . . , *x*ₚ} is valid iff $\forall x \in scp(\tau), \tau[x] \in dom(x)$.

**Example 5** Let us consider a constraint $c_{xyz}$ with $dom(x)=dom(z)=\{a,b,c\}$ and $dom(y)=\{a,c\}$. $\tau_1=(a,a,b)$ is a valid tuple since $\tau_1[x] \in dom(x)$, $\tau_1[y] \in dom(y)$ and $\tau_1[z] \in dom(z)$. However, $\tau_2=(b,b,b)$ is not valid since $\tau_2[y] \notin dom(y)$.

**Definition 10 (Support tuple)** An *r*-tuple τ on scp(*c*) is a support on the *r*-ary constraint *c* iff τ is a valid tuple which is allowed by *c*. If τ is a support on a constraint *c* involving a variable *x* and such that τ[*x*] = *a*, we say that τ is a support for (*x*, *a*) on *c*.

In Example 5, $\tau_1$ is a support for $(x, a)$, $(y, a)$ and $(z, b)$ on $c_{xyz}$.
## 1.1. INTRODUCTION TO CSP

**Definition 11 (Instantiation Projection)** Let $S$ be a set of variables and an instantiation $I$. The projection of $I$ on $S$, denoted $I[S]$, is $I[S] = \{(x, a)|(x, a) \in I \land x \in S\}$.

**Definition 12 (Satisfaction of a Constraint)** A constraint $c \in \mathcal{C}$ is said satisfied by an instantiation $I$ iff $scp(c) \subseteq vars(I)$ and $I[scp(c)] \in rel(c)$.

The domains of variables evolve during search which affects the validity of instantiations. In a constraint network, we distinguish several types of instantiations.

**Definition 13 (Partial/Complete Instantiation)** Considering a constraint network $P$, an instantiation $I$ is said partial if $vars(I) \subset vars(P)$. If $vars(I) = vars(P)$, $I$ is a complete instantiation.

**Definition 14 (Solution)** Considering a constraint network $P$, an instantiation $I$ is a solution of $P$ if $I$ is a complete instantiation that satisfies all the constraints of $P$.

**Definition 15 (Locally consistent Instantiation)** Let $P =< \mathcal{X}, \mathcal{D}, \mathcal{C} >$ be a constraint network, and an instantiation $I$ of a subset $S$ of $\mathcal{X}$. $I$ is said locally consistent iff $\forall c \in \mathcal{C} $ such that $scp(c) \subseteq vars(I)$, $c$ is satisfied by $I$.

**Definition 16 (Globally consistent/inconsistent Instantiation)** An instantiation $I$ is said globally consistent if it can be extended to a solution, otherwise it is globally inconsistent.

### 1.1.2 Complexity

In this sub-section, we introduce three main complexity classes:

* *P problems* for which a polynomial time algorithm exists ($O(n^k)$) such that $n$ is the size of the problem and $k$ is a constant. In the complexity class $P$, problems can be solved on a deterministic Turing machine [Herken, 1995] in polynomial time. The AKS (Agrawal–Kayal–Saxena) primality test [Bornemann, 2003] is a problem belonging to the complexity class $P$. This problem consists in determining whether a number is prime or composite;

* *NP problems* for which a verification algorithm exists to verify, in a deterministic way, if a solution to the problem is valid or not in polynomial time. NP problems can be solved on a non-deterministic Turing machine in polynomial time. One of the well-known problems of this class is the integer factorization which is the decomposition of a composite number into a product of smaller integers.
1.1. INTRODUCTION TO CSP

The constraint satisfaction problem belongs to the *NP-complete* complexity class.
The most notable characteristic of NP-complete problems is that the required
time to solve such problems grows quickly as the size of the problem grows (under
the assumption that P ≠ NP).

1.1.3 Example of a CSP: Map coloring

We take the example of a problem called “map coloring”. This problem con-
sists in coloring a map in a such way that there is no two adjacent regions
having the same color. We mean by “adjacent” two regions sharing a same
boundary line. The four-color theorem discovered by Francis Guthrie in the
early 1850s (would-be proved by Alfred Bray Kempe in 1879 and proved in
[Appel and Haken, 1977]), claims that “every planar map is four colorable”. To
illustrate that, we take the example of a Tunisian map illustrated in Figure 1.2.

Since our aim is to use only four different colors to color this map, we first
express this problem as a CSP. The four colors that we can use are *white*(*w*),
*light gray*(*lg*), *mid gray*(*mg*) and *dark gray*(*dg*) which compose the domain of
the different variables. Figure 1.2 presents all variables of the problem which are
the regions to be colored. We have 24 variables since there are 24 regions. For the
constraint part, we add a binary constraint each time we have two regions sharing
a boundary line. As a consequence, the map coloring problem is formalized as a
constraint network:

• P = < X, Y, Z >;

• X = {x_i | i ∈ [0, 23]};

• $\mathcal{D} = \{dom(x_i) | i \in [0, 23]\}$ such that $dom(x_i) = \{w, lg, mg, dg\}$;

$$
\bullet \mathcal{C} =
\left\{
\begin{array}{llll}
c_{x_0 x_2} : x_0 \neq x_2 & c_{x_0 x_3} : x_0 \neq x_3 & c_{x_0 x_4} : x_0 \neq x_4 & c_{x_1 x_2} : x_1 \neq x_2 \\
c_{x_1 x_6} : x_1 \neq x_6 & c_{x_1 x_7} : x_1 \neq x_7 & c_{x_2 x_3} : x_2 \neq x_3 & c_{x_2 x_7} : x_2 \neq x_7 \\
c_{x_3 x_4} : x_3 \neq x_4 & c_{x_3 x_5} : x_3 \neq x_5 & c_{x_3 x_8} : x_3 \neq x_8 & c_{x_3 x_9} : x_3 \neq x_9 \\
c_{x_4 x_5} : x_4 \neq x_5 & c_{x_5 x_9} : x_5 \neq x_9 & c_{x_6 x_7} : x_6 \neq x_7 & c_{x_6 x_11} : x_6 \neq x_{11} \\
c_{x_7 x_7} : x_7 \neq x_8 & c_{x_7 x_{11}} : x_7 \neq x_{11} & c_{x_7 x_{12}} : x_7 \neq x_{12} & c_{x_7 x_{15}} : x_7 \neq x_{15} \\
c_{x_9 x_{10}} : x_9 \neq x_{10} & c_{x_{10} x_{13}} : x_{10} \neq x_{13} & c_{x_{11} x_{12}} : x_{11} \neq x_{12} & c_{x_{11} x_{15}} : x_{11} \neq x_{15} \\
c_{x_{11} x_{18}} : x_{11} \neq x_{18} & c_{x_{12} x_{13}} : x_{12} \neq x_{13} & c_{x_{12} x_{15}} : x_{12} \neq x_{15} & c_{x_{12} x_{16}} : x_{12} \neq x_{16} \\
c_{x_{12} x_{17}} : x_{12} \neq x_{17} & c_{x_{13} x_{14}} : x_{13} \neq x_{14} & c_{x_{14} x_{16}} : x_{14} \neq x_{16} & c_{x_{15} x_{17}} : x_{15} \neq x_{17} \\
c_{x_{15} x_{18}} : x_{15} \neq x_{18} & c_{x_{16} x_{17}} : x_{16} \neq x_{17} & c_{x_{17} x_{21}} : x_{17} \neq x_{21} & c_{x_{18} x_{19}} : x_{18} \neq x_{19} \\
c_{x_{18} x_{20}} : x_{18} \neq x_{20} & c_{x_{18} x_{21}} : x_{18} \neq x_{21} & c_{x_{19} x_{20}} : x_{19} \neq x_{20} & c_{x_{20} x_{21}} : x_{20} \neq x_{21} \\
c_{x_{20} x_{22}} : x_{20} \neq x_{22} & c_{x_{20} x_{23}} : x_{20} \neq x_{23} & c_{x_{21} x_{22}} : x_{21} \neq x_{22} & c_{x_{22} x_{23}} : x_{22} \neq x_{23}
\end{array}
\right\}
$$

Figure 1.2 shows a solution to the problem where:

• x₀ = x₁ = x₅ = x₈ = x₁₄ = x₁₇ = x₂₀ = w
1.1. INTRODUCTION TO CSP

<figure><img src="image_13.png" /><figcaption>Figure 1.2: Complete instantiation of the Tunisian map coloring (Solution).</figcaption></figure>

• $x_2 = x_4 = x_6 = x_9 = x_{13} = x_{15} = x_{19} = x_{23} = lg$

• $x_{10} = x_{11} = x_{12} = x_{21} = mg$

• $x_3 = x_7 = x_{16} = x_{18} = x_{22} = dg$
### 1.1.4 Solvers

In constraint programming, we distinguish two major steps: modeling problems and solving them. Modeling problems refers to expressing its variables and constraints and solving them means looking for a solution or proving that there does not exist one.

To model constraint satisfaction problems several modeling languages have been proposed such as *OPL* [van Hentenryck, 1999], *Zinc* [de la Banda et al., 2006] and *Essence* [Frisch et al., 2007]. Simple formats exist also such as XCSP based on XML [Roussel and Lecoutre, 2009].

Several solvers have been developed such as *Choco* [Rochart et al., 2006], *Gecode* [Schulte et al., 2006], *Comet* [Nyström et al., 2003], *Minion* [Gent et al., 2006] and *ILOG*<fnref n="1" /> solver.

In the context of this thesis, we use *AbsCon* [Lecoutre and Tabary, 2007], the solver developed at CRIL. We used the instances benchmarks available at http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html

## 1.2 Consistency

In order to solve CSP instances, there are two major categories of algorithms and techniques: “Inference” and “Search”. Since CSP is *NP-complete*, finding a solution can be difficult. To speed up this process, we can use inference techniques whose aim is to simplify the problem typically by reducing the search space. If we cannot benefit from inference techniques, an “exploration” of the search space, called “Search” (see Section 1.5), is needed in order to look for a solution.

### 1.2.1 Definitions

Some inference algorithms and techniques are based on “constraint filtering” which consists in removing combination(s) of values while preserving constraints semantics in order to speed up the search space exploration [Montanari, 1974]. This filtering process is described on the basis of “consistencies” which are constraint network properties. A consistency corresponds to a certain level of coherence. It can be “local”, if it deals with a subset of variables, or “global” if it concerns the entire network.

**Definition 17 (k-consistency)** Let $P$ be a constraint network and $k$ be an integer such that $1 \le k < n$; $n = |vars(P)|$. $P$ is k-consistent [Freuder, 1978] iff for every subset of size $k-1$ $S_{k-1} \subset vars(P)$ and every additional variable $y$ such that $y \in vars(P) \setminus S_{k-1}$, every locally consistent instantiation $I$ of $S_{k-1}$

<footnote n="1">¹www.ilog.com</footnote>
## 1.2. CONSISTENCY

on *P* can be extended to a locally consistent instantiation *I*′ such that $\text{vars}(I') = S_{k-1} \cup \{y\}$.

A *2-consistent* constraint network *P* is said *arc-consistent*.

It is important to note that a *k-consistent* constraint network *P* is not necessarily *j-consistent* with $1 \le j < k$. A stronger property can be defined.

**Definition 18 (Strong k-consistency)** Let *P* be a constraint network and *k* an integer such that $1 \le k < n$ where $n = |\text{vars}(P)|$. *P* is strong *k*-consistent iff it is *j*-consistent $\forall j \in [1, k]$.

A stronger consistency can be defined over a constraint network *P* (See Section 1.4.3).

**Definition 19 (Global consistency)** A constraint network *P* is globally consistent iff it is strongly *n*-consistent.

We focus, in the context of this thesis, on “Domain-filtering” consistencies which detect some inconsistent values, in the domains of variables, aiming to discard them in order to simplify the problem.

**Example 6** Figure 1.3 illustrates the practical effect of enforcing a domain-filtering consistency. Taking the example of map coloring introduced in Section 1.1.3, we present three constraints $c_{x_0x_2}$, $c_{x_0x_3}$ and $c_{x_0x_4}$. The initial domains of variables $x_0$, $x_2$, $x_3$ and $x_4$ are the same; $\text{dom}(x_0) = \text{dom}(x_2) = \text{dom}(x_3) = \text{dom}(x_4) = \{w, lg, mg, dg\}$. After assigning *w* to the variable $x_0$, enforcing domain-filtering consistency on variables $x_2$, $x_3$ and $x_4$ induces removing the value *w* from their domains in order to not violate the constraints semantics (two neighbor regions cannot have the same color).

In the context of this thesis, we focus on local consistencies which are properties applied to a subset of variables or constraints. Historically [Montanari, 1974], distinguished three main consistencies.

* Node Consistency 1-consistency

* Arc Consistency 2-consistency

* Path Consistency

In the next sections, we introduce Arc Consistency and its generalization GAC and also a stronger consistency SAC.
## 1.3. GENERALIZED ARC CONSISTENCY (GAC)

<figure><img src="image_14.png" /><figcaption>Figure 1.3: Illustration of domain filtering.</figcaption></figure>

# 1.3 Generalized Arc Consistency (GAC)

Generalized Arc Consistency (GAC) is the most important consistency, which is a property that corresponds to the maximum level of filtering, used in practice, when constraints are treated independently.

**Definition 20 (Generalized Arc Consistency)** Let $P$ be a constraint network, $c$ a constraint such that $c \in \text{cons}(P)$ and $x$ a variable such that $x \in \text{scp}(c)$. A literal $(x, a)$ is GAC-consistent iff there is a valid tuple $\tau \in \text{rel}(c)$ such that $\tau[x] = a$. A variable $x$ is GAC-consistent iff $\forall a \in \text{dom}(x)$, $(x, a)$ is GAC-consistent. A constraint $c$ is GAC-consistent iff $\forall x \in \text{scp}(c)$, $x$ is GAC-consistent. A constraint network $P$ is GAC-consistent iff $\forall c \in \text{cons}(P)$, $c$ is GAC-consistent.

**Example 7** Let us consider an allDifferent global constraint on three variables $x$, $y$ and $z$ such that $\text{dom}(x) = \text{dom}(z) = \text{dom}(y) = \{a, b\}$. If we suppose that $x$ is assigned to $a$ and $y$ to $b$, using the domain filtering technique the domain of $z$ does not contain anymore a possible value since $z$ should be different from $x$ and $y$. The allDifferent constraint is thus GAC-inconsistent.

$$ \text{dom}(x) = \{a,b\} \implies \text{dom}(y) = \{a,b\} \implies \text{dom}(z) = \{a,b\} $$

Now, if we consider that $\text{dom}(z) = \{a, b, c\}$, by assigning $a$ to $x$ and $b$ to $y$, the variable $z$ could be assigned to $c$ and then the allDifferent constraint is GAC-consistent.
## 1.3. GENERALIZED ARC CONSISTENCY (GAC)

$$dom(x) = \{a,b\} \implies dom(y) = \{a,b\} \implies dom(z) = \{a,b,c\}$$

In Section 1.3.2, we explore filtering algorithms which enforce GAC on table constraints.

### 1.3.1 Arc Consistency

Arc Consistency (AC) corresponds to GAC when constraints are binary.

**Example 8** Let P be a constraint network described by its compatibility graph in Figure 1.4. The variables of P are vars(P) = {x, y, z} such that dom(x) = dom(y) = dom(z) = {a, b, c}. The constraints of P are cons(P) = {c<sub>xy</sub>, c<sub>xz</sub>, c<sub>yz</sub>}.
These constraints are defined in extension such that c<sub>xy</sub> = {(a, a), (b, b), (c, c)}, c<sub>xz</sub> = {(a, b), (b, a), (c, c)} and c<sub>yz</sub> = {(a, b), (c, a)}. P is not arc-consistent since there are some values in the domain of vars(P) which are not arc-consistent. This is the case of the literals (z, c) and (y, b) that have no supports on c<sub>yz</sub>.

<figure><img src="image_15.png" /><figcaption>Figure 1.4: An arc-inconsistent network P.</figcaption></figure>

To enforce AC on P, we proceed to several constraint filterings. We start by enforcing AC on c<sub>yz</sub> described in Figure 1.5. The literal (z, c) is not arc-consistent, so it is removed from the domain of the variable z. Hence, all values supported by (z, c) lose their support (illustrated by a dotted link) since it is discarded: c<sub>xz</sub>, originally arc-consistent, loses a support for (x, c) and becomes not arc-consistent. The literal (y, b) is also not arc-consistent: it is removed from dom(y) and the literal (x, b) has no more a support on c<sub>xy</sub> (originally arc-consistent). The obtained network, denoted AC(P) and illustrated in Figure 1.5(b), is still not arc-consistent.

As c<sub>xy</sub> and c<sub>xz</sub> become not arc-consistent, we enforce AC on them. The literal (x, b) does not have a support on c<sub>xy</sub>, so it is removed from dom(x) causing the inconsistency of the literal (z, a) on c<sub>xz</sub>. This is described in Figure 1.6(a). The literals (z, a) and (x, c) are removed while enforcing AC on c<sub>xz</sub> (Figure 1.6(b)).
## 1.3. GENERALIZED ARC CONSISTENCY (GAC)

<figure><img src="image_16.png" /><figcaption>Figure 1.5: Enforcing AC on $c_{yz}$.</figcaption></figure>

The literal (y, c) has then no support for all the constraints of P. By removing (y, c), we obtain the final arc-consistent network (Figure 1.6(c)).

<figure><img src="image_17.png" /><figcaption>Figure 1.6: Enforcing AC on constraints originally arc-consistent.</figcaption></figure>
## 1.3. GENERALIZED ARC CONSISTENCY (GAC)

Example 8 shows that enforcing arc-consistency on a constraint network $P$ may lead to removing a literal $(x, a)$ which is in its turn a support for another literal $(y, b)$. As a consequence, a AC-consistent constraint may become not AC-consistent due to a support removal. The process of “constraint propagation” is repeated until it reaches a fixed point [Granas and Dugundji, 2003, Bessiere, 2006] where the constraint network is arc-consistent ($AC(P) = P$) or an inconsistency is detected due to a domain wipe-out ($AC(P) = \perp$). Several algorithms have been proposed to enforce

<table><caption>Table 1.1: The worst-case complexity of several AC algorithms on binary constraint networks.</caption><thead><tr><td>Algorithm</td><td>Time complexity</td><td>Space complexity</td></tr></thead><tbody><tr><td>AC1</td><td>O(end<sup>3</sup>)</td><td>O(n<sup>2</sup>)</td></tr><tr><td>AC3</td><td>O(ed<sup>3</sup>)</td><td>O(e + nd)</td></tr><tr><td>AC4</td><td>O(ed<sup>2</sup>)</td><td>O(ed<sup>2</sup>)</td></tr><tr><td>AC6</td><td>O(ed<sup>2</sup>)</td><td>O(ed)</td></tr><tr><td>AC7</td><td>O(ed<sup>2</sup>)</td><td>O(ed)</td></tr><tr><td>AC2001</td><td>O(ed<sup>2</sup>)</td><td>O(ed)</td></tr><tr><td>AC3<sup>rm</sup></td><td>O(ed<sup>3</sup>)</td><td>O(ed)</td></tr></tbody></table>

AC: AC1, AC3 [Mackworth, 1977], AC4 [Mohr and Henderson, 1986], AC6 [Bessiere, 1994], AC7 [Bessiere et al., 1999], AC2001 [Bessiere and Régin, 2001, Zhang and Yap, 2001] and AC3<sup>rm</sup> [Lecoutre and Hemery, 2007]. These algorithms have different complexities in terms of time and space (presented in Table 1.1).

We present only both AC3 and AC2001 algorithms. These two algorithms use the same *doAC* propagation algorithm (presented in Algorithm 8) calling Algorithm *revise* (in line 4) which differs from an *AC* algorithm to another. Algorithm 8 takes as input a constraint network $P$. *doAC* returns a Boolean indication; “true” if the algorithm reaches an arc-consistent network and “false” if an inconsistency is detected (there is an empty domain), denoted $AC(P) = \perp$. *doAC* algorithm maintains a propagation queue $Q$ containing literals $(c, x)$ where $c \in \mathscr{C}$ and $x \in \text{scp}(c)$. These literals contained in $Q$ are revised by Algorithm *revise* which removes all values $a \in \text{dom}(x)$ that do not have a support on $c$. If *revise* removes at least one value, it checks if $\text{dom}(x) = \emptyset$. If it is the case, a global inconsistency is detected and “false” is returned, otherwise the queue $Q$ is updated by adding all literals $(c', y)$ where $c' \in \mathscr{C}$ is a constraint involving $x$. All these literals should be revised in the next iteration since it is possible that a removed literal $(x, a)$ is a support for another literal $(y, b)$ on a constraint $c'$ (as shown in Example 8). The constraint propagation achieves its fixed point when $Q$ is empty ($Q = \emptyset$: there is no literal $(c, x)$ to revise) and “true” is returned indicating that the constraint network respects the *AC* property.
1.3. GENERALIZED ARC CONSISTENCY (GAC)

<caption>**Algorithm 8:** doAC (*P* = (*X*, *D*, *C*): Constraint network): Boolean</caption>

1 $Q \leftarrow \{(c, x)|c \in C \land x \in scp(c)\}$
2 **while** $Q \neq \emptyset$ **do**
3 &nbsp;&nbsp;&nbsp;choose then delete $(c, x)$ from $Q$
4 &nbsp;&nbsp;&nbsp;**if** revise$(c, x)$ **then**
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $dom(x) = \emptyset$ **then**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** false
7 &nbsp;&nbsp;&nbsp;**else**
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $Q \leftarrow Q \cup \{(c', y)|c' \in C \land x \in scp(c') \land y \in scp(c') \land y \neq x \land c \neq c'\}$
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** true

AC3 [Mackworth, 1977] AC3 algorithm uses revise-3 revision technique (Algorithm 9). Each literal (c, x) is revised in a manner that revise-3 checks if for each value in the current domain of x, there exists a support on c (Line 3). If a support is found, the checking process continues until each value of dom(x) is verified. If revise-3 does not find a support for (x, a) on c, this value is removed from dom(x) (Line 4). revise-3 algorithm returns true iff there is at least one value removed from dom(x). AC3 algorithm has a time complexity of O(ed³) where e is the number of constraints of P and d is the size of the greatest domain of a variable of the network (as presented in Section 1.1.1).

<caption>**Algorithm 9:** revise-3(c: constraint, x:variable): Boolean</caption>

// scp(c) = {x, y}
1 modified ← false
2 **foreach** a ∈ dom(x) **do**
3 &nbsp;&nbsp;&nbsp;**if** ∃b ∈ dom(y) such that (a, b) ∈ rel(c) **then**
4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dom(x) ← dom(x) \ a
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** modified ← true
6 **return** modified

AC2001 [Bessiere and Régin, 2001, Zhang and Yap, 2001] AC2001
has an optimized *revise* algorithm in a manner that speeds up the support de-
tection process. *revise-2001* (presented in Algorithm 10) uses the data structure,
called *last*, which stores the last support found on a constraint *c*, such that
*scp(c) = {x, y}*}, for a variable *x* and a value *a*. This structure will speed up
the support searching. In other terms, it is not required anymore to iterate, *in*
*each revision*, over all values of *dom(y)* to find a support, but only checking if
*last[c, x, a]* (last found support) still exists in *dom(y)* is enough (Line 8). If the
last found support does not exist in *dom(y)*, the searching process continues from
*last[c, x, a]* position and so looking for a support does not restart from scratch
1.3. GENERALIZED ARC CONSISTENCY (GAC)

(Line 4). This explains why the condition (b > last[c, x, a]) is added. If there
is no “new” support found, the literal (x, a) is considered arc-inconsistent and
it is removed from dom(x) (Line 5), otherwise the “new” found support (y, b)
is stored in last[c, x, a] (Line 8). The time complexity of AC2001 algorithm is
O(ed²) which is reduced compared to AC3 (O(ed³)).

<caption>**Algorithm 10:** revise-2001(c: constraint, x:variable): Boolean</caption>

```c
// scp(c) = {x, y}
1 modified ← false
2 foreach a ∈ dom(x) do
3     if last[c, x, a] ∉ dom(y) then
4         if ∃b ∈ dom(y) such that b > last[c, x, a] ∧ (a, b) ∈ rel(c) then
5             dom(x) ← dom(x) \ a
6             modified ← true
7         else
8             last[c, x, a] ← b
9 return modified
```

1.3.2 GAC for Table Constraints

Table constraints, i.e., constraints given in extension by listing the tuples of values allowed (positive table) or forbidden (negative table) for a set of variables, are widely studied in Constraint Programming. This is because such constraints are present in many real-world applications from areas such as design and configuration, databases, and preferences modeling. Sometimes, table constraints provide the unique natural or practical way for a non-expert user to express her constraints. So far, research on table constraints has mainly focused on the development of fast algorithms to enforce Generalized Arc Consistency and/or to compress their representation. Algorithms *AC3* and *AC2001* presented in the previous section are generalized for *n-ary* constraints as *GAC3* and *GAC2001* and could be used for table constraints. We introduce different variants of Simple Tabular Reduction (STR) technique used to manage table constraints during search.

For the sake of simplicity, we only consider positive table constraints.

**Classical schemes** We distinguish two classical schemes for support seeking. *GAC-valid* scheme iterates over valid tuples until an allowed one is found. *GAC-allowed* scheme iterates over allowed tuples until a valid one is found. Since iterating over allowed/valid tuple is expensive, several STR variants are proposed to speed up enforcing GAC on table constraints. *GAC-valid+allowed*
1.3. GENERALIZED ARC CONSISTENCY (GAC)

[Lecoutre and Szymanek, 2006] alternates in iteration over both valid and al-
lowed tuples without any additional data-structure.

**Simple Tabular Reduction (STR)**

STR [Ullmann, 2007], also called STR1, is one of the most efficient techniques to
enforce GAC on table constraints. This approach differs significantly from the
other techniques and aims to reduce dynamically, and during search, table con-
straints complexities. In fact, enforcing GAC consists in removing invalid tuples
in a manner that the table maintains only the allowed tuples. This technique fa-
cilitates detecting generalized arc-inconsistent values inducing tuples removing.
As a consequence, a table contains only supports. We present STR algorithm
and its optimized variants. However, we will keep the backtracking issues (going
back to the previous search state) for a further section (Section 1.5.1).

The table constraint *table*[c] is split into two major parts. The first one
contains the allowed valid tuples, also called *current tuples*, forming the *current
table*. The remaining part contains all tuples removed at different levels of search.
In our context, a level of search corresponds to the number of positive decisions
made. Managing the set of tuples is provided by:

*   *position*[c] is an array of size *t* that provides indirect access to the tuples of *table*[c]. In fact, this array is used in order to achieve an *O*(1) permutation since we permute indexes instead of tuples. *table*[c][*position*[c][*i*]] represents the *i*th tuple of *c*. At any given time the values in *position*[c] are a permutation of {1, 2, ..., *t*}.

*   *currentLimit*[c] is the index of the last current tuple in *table*[c]. The elements in *position*[c] at indexes ranging from 1 to *currentLimit*[c] are positions of the current tuples of *c*. As a consequence, the current table of *c* is composed of exactly *currentLimit*[c] tuples.

*   *levelLimits*[c] is an array of size *n*+1 such that *levelLimits*[c][*p*] is the position of the first invalid tuple of *table*[c] removed at search level *p*. If there is no tuple removed at level *p*, *levelLimits*[c][*p*]=−1. All tuples removed at level *p* (if *levelLimits*[c][*p*]≠ −1) can be accessed using indexes at locations in array *position*[c] ranging from *currentLimit*[c]+1 to *levelLimits*[c][*p*]. *levelLimits*[c] is exploited in Backtracking and it is indexed from 0 to *n*. *levelLimits*[c][0] is used to store the tuples removed at pre-processing [Benson et al., 1992] (the set of investigations done before searching for solution(s)) .

*   *gacValues*[c] [Ullmann, 1977] is an array of size *r*, where *r* is the arity of *c*. To each uninstantiated variable *x* corresponds a set *gacValues*[c][*x*] containing all values in *dom*(*x*) which are proved to have a support when GAC is enforced on *c*.
## 1.3. GENERALIZED ARC CONSISTENCY (GAC)

<figure><img src="image_18.png" /><figcaption>Figure 1.7: Initialization of STR data structures for a positive table constraint $c_{xyz}$; $dom(x) = dom(y) = dom(z) = \{a, b, c\}$.</figcaption></figure>

**Example 9** To illustrate the use of the different data structures, we describe the different changes during search. $c_{xyz}$ is a ternary positive table constraint such that `scp(c_{xyz}) = \{x, y, z\}` and `dom(x) = dom(y) = dom(z) = \{a, b, c\}`. `rel(c_{xyz})` is presented in Figure 1.7 which describes the initial states of position[c], levelLimits[c], currentLimit[c] and gacValues[c].

We consider that a decision made at level 1 (for a variable of the constraint network involving $c_{xyz}$) induces (by constraint propagation) the removal of $(z, a)$. STR is then applied (Figure 1.8) such that $dom^1(x) = dom^1(y) = \{a, b, c\}$ and $dom^1(z) = \{b, c\}$. Tuple $\tau_1$ is no longer valid, so it is removed by swapping its position with the currentLimit position. levelLimits[$c_{xyz}$][1] is updated to 6 as it is the position of the first invalid tuple in this level. The currentLimit is also updated to 5 (the last current tuple)(Figure 1.8(a)). The process is continued by swapping position[$c_{xyz}$][1] and position[$c_{xyz}$][5]. The final result is described in 1.8(c). The array gacValues[$c_{xyz}$] is updated where gacValues[$c_{xyz}$][$x$]=dom$^1(x)$, gacValues[$c_{xyz}$][$z$]=dom$^1(z)$ but gacValues[$c_{xyz}$][$y$]≠ dom$^1(y)$. The literal $(y, b)$ is not supported anymore and will be removed. currentLimit[$c_{xyz}$] is equal to 3 which means that there are three remaining valid tuples in $c_{xyz}$ after enforcing GAC. At level 2, the literal $(x, a)$ is removed by propagation. Enforcing GAC is then required. Figure 1.9 describes the final result where levelLimits[$c_{xyz}$][2] is turned to 3 referencing the first removed tuple. The variable $y$ loses also the value $c$ since gacValues[$c_{xyz}$][$y$]=\{a\}≠ dom$^2(y) = \{a, c\}$ meaning that this value is no longer supported by any current tuple of $c_{xyz}$.

The worst-case time complexity of `enforceGAC-STR` is $O(r'd + rt')$ where $r'$ is the uninstantiated variables ($r' = |scp(c) \setminus past(P)|$) and $t'$ is the current
1.3. GENERALIZED ARC CONSISTENCY (GAC)

<figure><img src="image_19.png" /><figcaption>Figure 1.8: Enforcing GAC-STR on $c_{xyz}$ after the removal of $(z, a)$ at level 1.</figcaption></figure>
## 1.3. GENERALIZED ARC CONSISTENCY (GAC)

<figure><img src="image_20.png" /><figcaption>Figure 1.9: Enforcing GAC-STR on $c_{xyz}$ after the removal of $(x, a)$ at level 2; $(y, c)$ is not supported.</figcaption></figure>

tuples $(past(P))$ is the last assigned variable). The worst-case space complexity of `enforceGAC-STR` is $O(n + rt)$.

**STR2** [Lecoutre, 2011] An optimized variant of STR is proposed in [Lecoutre, 2011] where we can distinguish two optimizations.

In a first place, it is useless to continue looking for supports for domain values if these ones have already been detected GAC-consistent. To avoid such redundant operations, the $S^{sup}$ set is introduced. All uninstantiated variables in `scp(c)` whose domain contains at least one unsupported value are stored in $S^{sup}$.

In a second place, useless validity operations are avoided. It is true that, for each variable $x$ in `scp(c)`, if there is no backtrack and $dom(x)$ does not change since the last GAC-STR call, the current value $\tau[x] \in dom(x)$. A second set, denoted $S^{val}$, is defined which contains all uninstantiated variables in `scp(c)` whose domain has been reduced since the last call of GAC-STR.

The used GAC-STR is called `enforceGAC-STR2` (presented in Algorithm 11). The gain obtained through $S^{sup}$ use is obvious in Lines 16 and 25 where, instead of iterating over all variables in `enforceGAC-STR`, `enforceGAC-STR2` iterates only over those contained in $S^{sup}$. Initially contains all uninstantiated variables (Line 7), $S^{sup}$ set is updated in Line 20 where the variable $x$ is removed if it has been found that all the value of its domains are supported ($|dom(x)| = |gacValues[c][x]|$).

The set $S^{val}$ contains the last assigned variable if it is involved in `scp(c)` (lastPast(P)) and, eventually all variables having a domain smaller than the last stored size (`lastSize[c][x]`) in the last call (Lines 4 and 9). The set $S^{val}$ is used in `isValidTuple2` (introduced in Algorithm 12) to reduce tests to only variables
1.3. GENERALIZED ARC CONSISTENCY (GAC)

contained in $S^{val}$ whose domains has not been changed since the last call.

**Algorithm 11:** `enforceGAC-STR2(P:constraint network, c: constraint):set of variables`

```p
// Initialization of sets S^{val} and S^{sup}
1 S^{val} ← ∅
2 S^{sup} ← ∅
3 if lastPast(P) ∈ scp(c) then
4   S^{val} ← S^{val} ∪ {lastPast(P)}
5 foreach variable x ∈ scp(c)|x ∉ past(P) do
6     gacValues[c][x] ← ∅
7     S^{sup} ← S^{sup} ∪ {x}
8     if |dom(x)| ≠ lastSize[c][x] then
9       S^{val} ← S^{val} ∪ {x}
10      lastSize[c][x] ← |dom(x)|
// Iteration over all current tuples of c
11 i ← 1
12 while i ≤ currentLimit[c] do
13   index ← position[c][i]
14   τ ← table[c][index]
15   if isValidTuple(c, S^{val}, τ) then
16     foreach variable x ∈ scp(c)|x ∈ S^{sup} do
17       if τ[x] ∉ gacValues[c][x] then
18         gacValues[c][x] ← gacValues[c][x] ∪ {τ[x]}
19         if |dom(x)| = |gacValues[c][x]| then
20           S^{sup} ← S^{sup} \ {x}
21     i ← i + 1
22   else
23   S^{sup} ← S^{sup} \ {x}
// domains are now updated and X_{evt} computed
24 X_{evt} ← ∅
25 foreach variable x ∈ S^{sup} do
26   dom(x) ← gacValues[c][x]
27   if dom(x) = ∅ then
28     throw INCONSISTENCY
29   X_{evt} ← X_{evt} ∪ {x}
30   lastSize[c][x] ← |dom(x)|
31 return X_{evt} // X_{evt} contains variables with reduced domains
```
## 1.4. SINGLETON ARC CONSISTENCY(SAC)

**Algorithm 12:** `ValidSTuple(c: constraint, S<sup>val</sup>:variables, τ: tuple):`
**Boolean**
1 **foreach** variable *x* ∈ S<sup>val</sup> **do**
2     **if** τ[*x*] ∉ dom(*x*) **then**
3     **return** false
4 **return** true

According to [Lecoutre, 2011], there exists situations where applying `enforceGAC-STR2` is $O(t + rd)$, which means that `enforceGAC-STR2` is potentially $r$ times faster than `enforceGAC-STR`.

**STR3 [Lecoutre et al., 2012]** STR3 is also an optimized variant of STR which differs significantly from STR and STR2 in representing invalid tuples. Rather than discarding them explicitly from the table, invalid tuples are partitioned off in a different way avoiding duplicated effort in re-establishing the consistency of values across the search tree as it commonly happens with conventional GAC algorithms. The idea is similar to GAC4 [Mohr and Masini, 1988]: each element of a table is examined at most once along any path of the search tree.

The worst-case accumulated cost along a single path of length $m$ in the search tree involving a positive $r$-ary table constraint containing $t$ tuples is $O(rt + m)$ for STR3 whereas it is $O(rtm)$ for STR2. The space complexity of STR3 for a single table constraint is $O vd$ whereas the space complexity for STR2 is $O(r)$ (not counting space for the table representation itself).

Experiments in [Lecoutre et al., 2012] show that STR3 (which is greedy in memory space) is much faster than STR2 when the average size of the tables is not reduced drastically during search. However, where simple tabular reduction can eliminate many tuples from the tables that they become largely empty, STR2 is faster than STR3.

Christophe: à revoir

## 1.4 Singleton Arc Consistency(SAC)

*Singleton arc consistency (SAC)* is a consistency stronger than arc consistency allowing to identify more inconsistent values before/during search. SAC is kind of looking one step in all directions (*Breadth-First Search* of level 1).
## 1.4. SINGLETON ARC CONSISTENCY(SAC)

### 1.4.1 Definitions

**Definition 21 (Constraint network such that $x = a$)** Let $P$ be a constraint network, a variable $x \in \mathcal{X}$ and a value $a \in \text{dom}(x)$, $P|_{x=a}$ is the constraint network obtained after reducing $\text{dom}(x)$ to $\{a\}$.

**Definition 22 (Singleton Arc-Consistent network)** A constraint network $P$ is singleton arc-consistent iff $\forall x \in \mathcal{X}, \forall a \in \text{dom}(x), \text{GAC}(P|_{x=a}) \neq \perp$.

**Example 10** We consider again the constraint network $P$ used in Example 8 (Figure 1.4). Figure 1.10 describes enforcing SAC on a constraint network $P$. Figure 1.10(a) is the obtained network after assigning $a$ to $x$. $\text{dom}(x)$ is, thus, reduced to only $a$. $P|_{x=a}$ is GAC, and, so $(x, a)$ is SAC. Figure 1.10(b) is the obtained network after assigning $b$ to $x$. $(z, a)$ is the only support of $(x, b)$ on $c_{xz}$ and $(y, b)$ is also the only one on $c_{xy}$. However, $\{(y, b), (z, a)\} \notin \text{rel}(c_{yz})$. As a consequence, $\text{GAC}(P|_{x=b}) = \perp$ and $(x, b)$ is not SAC.

<figure><img src="image_21.png" /><figcaption>Figure 1.10: Enforcing Singleton Arc-Consistency on $P$.</figcaption></figure>

Singleton consistencies have received much attention: SAC1 [Debruyne and Bessiere, 1997], SAC2 [Bartak and Erben, 2004], SAC-Opt [Bessiere and Debruyne, 2004], SAC-SDS [Bessiere and Debruyne, 2005], SAC3 and SAC3+ [Lecoutre and Cardon, 2005]. Table 1.2 describes the time and space complexities of exploring consistencies on binary constraint networks of these different algorithms. For SAC3+ algorithm, the variable $b^+$ denotes the total number of times a branch is built or checked by the algorithm and $b_{max}$ denotes the maximum number of branches recorded at the same time by the algorithm.
## 1.4. SINGLETON ARC CONSISTENCY(SAC)

<table><caption>Table 1.2: The worst-case complexity of the SAC algorithms on binary constraint networks.</caption><thead><tr><td>Algorithm</td><td>Time complexity</td><td>Space complexity</td></tr></thead><tbody><tr><td>SAC1</td><td>O(en<sup>2</sup>d<sup>4</sup>)</td><td>O(ed)</td></tr><tr><td>SAC2</td><td>O(en<sup>2</sup>d<sup>4</sup>)</td><td>O(n<sup>2</sup>d<sup>2</sup>)</td></tr><tr><td>SAC-Opt</td><td>O(end<sup>3</sup>)</td><td>O(end<sup>2</sup>)</td></tr><tr><td>SAC-SDS</td><td>O(end<sup>4</sup>)</td><td>O(n<sup>2</sup>d<sup>2</sup>)</td></tr><tr><td>SAC3</td><td>O(en<sup>2</sup>d<sup>4</sup>)</td><td>O(ed)</td></tr><tr><td>SAC3+</td><td>O(b<sup>+</sup>ed<sup>2</sup>)</td><td>O(ed + b<sub>max</sub>nd)</td></tr></tbody></table>

### 1.4.2 SAC1

SAC1 [Debruyne and Bessiere, 1997] is the first proposed algorithm in order to enforce singleton arc consistency. Algorithm 13 starts by enforcing GAC on the whole constraint network (Line 1). SAC algorithm iterates then over all literals $(x, a)$ such that $x \in \mathcal{X}$ and $a \in \text{dom}(x)$ (Line 6). If a literal is detected to be SAC-inconsistent, it is removed from its domain and GAC is enforced to propagate this removal (Line 8). If enforcing GAC returns an empty domain (Lines 2 and 9) *false* is returned meaning that *P* is proved to be SAC-inconsistent ($\text{SAC}(P) = \perp$); otherwise *true* is returned.

<caption>**Algorithm 13: SAC(P: constraint network):Boolean**</caption>

1. $P \leftarrow \text{GAC}(P)$ // GAC is initially enforced
2. **if** $P = \perp$ **then**
3. &nbsp;&nbsp;&nbsp;&nbsp;**return** *false*
4. **repeat**
5. &nbsp;&nbsp;&nbsp;&nbsp;**modified** $\leftarrow$ *false*
6. &nbsp;&nbsp;&nbsp;&nbsp;**foreach** $(x, a)$ such that $x \in \text{vars}(P) \land a \in \text{dom}(x)$ **do**
7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $\text{GAC}(P|_{x=a}) = \perp$ **then**
8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**P** $\leftarrow \text{GAC}(P|_{x \neq a})$ // *a* is removed from $\text{dom}(x)$ and GAC is enforced
9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $P = \perp$ **then**
10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** *false*
11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**modified** $\leftarrow$ *true*
12. **until** $\neg$**modified**
13. **return** *true*

SAC2 [Bartak and Erben, 2004], an optimized variant of SAC, is based on the fact that if $\text{GAC}(P|_{x=a}) \neq \perp$ then the literal $(x, a)$ remains SAC-consistent
### 1.5. SEARCH

as long as its supports exists. SAC-Opt [Bessiere and Debruyne, 2004], unlike SAC1 and SAC2, doesn't restart checking values from scratch but uses the stored sub-problem for each SAC-consistent values. In order to avoid some useless tests, SAC-Opt requires a huge memory space especially on large constraints. Ensuring a trade-off between time and space complexity, SAC-SDS [Bessiere and Debruyne, 2005], an optimized variant, shares data structures required for establishing GAC on the different sub-problems. Unlike the previous variants, SAC3 [Lecoutre and Cardon, 2005] does not use a *Breadth-First Search* but builds fewer branches of greater length maintaining GAC at each step. In fact, a current branch is extended until a dead-end (a domain is wiped-out so it impossible to make a new assignment) is reached. SAC3+, also presented in [Lecoutre and Cardon, 2005], is an improvement associating with each branch a domain so it is easier to determine which previously built branch(s) must be reconsidered when a value is removed.

#### 1.4.3 Weak k-SAC

Weak k-Singleton Arc Consistency [van Dongen, 2006] is a stronger form of SAC. It is equal to singleton arc consistency when $k = 1$ and stronger than SAC when $k > 1$. By analogy to Definition 17, we define Weak k-SAC.

**Definition 23 (Weak k-Singleton Arc-Consistency)** Let $P$ be a constraint network and $1 \le k \le n$ be an integer. A literal $(x, a)$ of $P$ is weakly k-SAC-consistent iff there exists an instantiation $I$ on a set of $k-1$ variables such that $x \notin \text{scp}(I)$ and $I$ is a valid instantiation such that $\text{GAC}(P|_{\{(x,a)\}\cup I}) \ne \bot$. A variable $x$ is weakly k-SAC-consistent iff $\forall a \in \text{dom}(x)$, $a$ is weakly k-SAC-consistent. $P$ is weakly k-SAC-consistent iff $\forall x \in \mathcal{X}$, $x$ is weakly k-SAC-consistent.

Algorithm 14 illustrates the enforcement of weak k-SAC consistency on a constraint network $P$. Following SAC, weak k-SAC starts by enforcing GAC on the whole constraint network (Line 1). All literals $(x, a)$ are collected into a queue $Q_{wsac}$. Treated one by one, WSAC calls the function *extendable* to verify if it is possible to instanciate $k$ variables. If it is not the case, the literal $(x, a)$ is removed and the process continues with another literal.

## 1.5 Search

Several algorithms are proposed ensuring the “search” mechanism. We distinguish two major categories: *look-back* and *look-ahead* techniques.
## 1.5. SEARCH

<caption>**Algorithm 14:** WSAC($P$: constraint network, $k$: integer):Boolean</caption>

1 $P \leftarrow GAC(P)$ // GAC is initially enforced
2 if $P = \perp$ then
3 $\lfloor$ return false
4 $Q_{wsac} \leftarrow \{(x, a) | x \in \text{vars}(P) \wedge a \in \text{dom}(x)\}$
5 while $Q_{wsac} \neq \emptyset$ do
6 $\lfloor$ pick and delete $(x, a)$ from $Q_{wsac}$
7 if $\neg \text{extendable}(P|_{x=a}, k)$ then
8 $\lfloor$ $P \leftarrow GAC(P|_{x \neq a})$ // $a$ is removed from $\text{dom}(x)$ and GAC enforced
9 if $P = \perp$ then
10 $\lfloor$ return false
11 $\lfloor$ $Q_{wsac} \leftarrow \{(x, a) | x \in \text{vars}(P) \wedge a \in \text{dom}(x)\}$
12 return true

### 1.5.1 Look-back approaches

**Standard Backtrack (SBT)** Backtrack technique is usually used in order to solve constraint satisfaction problem instances. It extends, incrementally, a partial instantiation aiming to reach a possible solution. To do that, a depth-first search is performed assigning variables one by one. If a conflict is detected when assigning $x = a$, i.e. an instantiation $I$ violates a constraint $c$, another value of $x$ must be found (edge 1 in Figure 1.11). If there is no value in $\text{dom}(x)$ satisfying $\mathcal{C}$ of $P$, a chronological backtrack is performed inducing looking for another value for the previous variable (edge 2 in Figure 1.11). This process continues until all variables of the constraint network $P$ are assigned. In the other case, and after exploring the whole search space, we say that $P$ is “unsatisfiable”.

There are also other methods using backtracking that differs from SBT. We distinguish:

* **Gaschnig-backjumping [Gaschnig, 1979]:** this approach uses backtracking in a different way. In fact, if for a variable $x$ there is no value from its domain that, added to a partial instantiation $I$, satisfies a constraint $c$ of $P$, the backtrack is not performed for the last assigned variable. This approach uses “culprit” variables, which are the recent assigned variables causing this incompatibility. As a consequence, Backtracking to the recent “culprit” variable, could lead to a solution.

* **Conflict-directed backjumping (CBJ) [Prosser, 1993]:** this approach avoids “Thrashing” which is exploring the same dead-ending sub-trees. Using nogoods, which are assignment sets that are not contained in any
## 1.5. SEARCH

<figure><img src="image_22.png" /><figcaption>Figure 1.11: Possible standard backtracks on *P*.</figcaption></figure>

solution, this technique avoids the “wrong” assignments that could lead to a failure. For each conflict, the set of nogoods leading to this conflict are stored, and thus, the backjumping is performed at the level of the recent decision leading to the conflict.

* **Dynamic Backtracking (DBT) [Ginsberg, 1993]:** Dynamic Backtracking uses a set of nogoods in order to detect the decision in charge of the last conflict. However, unlike the previous techniques, DBT removes the culprit decisions while maintaining the other decisions.

### 1.5.2 Look-ahead approaches

Unlike *look-back* approaches that look back on the made decisions in order to revise them and extend them to a solution, *look-ahead* approaches, introduced in [Haralick and Elliott, 1980], enhance exploring the search space by anticipating failures and reducing the search space. We distinguish the *Partial-Lookahead* and *Full-Lookahead*.

These inference techniques evaluate the impact of each decision on the domain of each unassigned variable. After each decision, a consistency is maintained on the constraint network in order to remove the inconsistent values. As a consequence, the search space is reduced and it contains only the consistent values avoiding by this filtering possible failures.

We present Forward Checking (FC), a *Partial-Lookahead* approach, introduced in [Haralick and Elliott, 1980].
1.5. SEARCH

**Forward Checking (FC)** After each decision, FC technique applies a partial
arc-consistency form on the constraint network. Only the neighborhood (vari-
ables involved in the same constraints as the variable *x*) of the assigned variable
is revised.

**Example 11** Figure 1.12 illustrates FC approach. After the first decision x₁ = a, the domain of x₁ neighborhood is revised: the value a is removed from dom(x₂) and dom(x₃) to respect the semantic of constraints cₓ₁x₂ and cₓ₁x₃. Assigning x₂ to b, induces the removal of the literal (x₃, b). After the decision x₃ = c (c is one of the coherent values left in dom(x₃)), dom(x₄) loses the value c.

<figure><img src="image_23.png" /><figcaption>Figure 1.12: Forward Checking on *P*.</figcaption></figure>
1.5. SEARCH

1.5.3 Maintaining Arc Consistency (MAC)

In order to enhance the effectiveness of search approaches, we may main-
tain the consistency of the constraint network associated to each node by ap-
plying one of the filtering algorithm (seen in Section 1.3 and 1.4). MAC
[Sabin and Freuder, 1994] is the backtrack algorithm that maintains GAC dur-
ing search. MAC is considered to be the most efficient complete approach to
solve CSP instances.

<caption>Algorithm 15: MAC(*P*: constraint network)</caption>

1 consistent ← GAC(P) // GAC is initially enforced
2 if ¬consistent then
3   return
4 I ← ∅
5 finished ← false
6 while ¬finished do
7   pick a literal (x, a) of P such that x / ∈ past(P)
8   I.push(x, a)
9   dom(x).reduceTo(a, |I|) // x is assigned the value a
10  consistent ← GAC(P)
11  if consistent ∧ |I| = n then
12   print(I) // a solution has been found
13   consistent ← false // inserted to keep looking for
14   solutions
15  while ¬consistent ∧ |I| ≠ ∅ do
16   (x, a) ← I.pop()
17   foreach variable y ∈ vars(P) \ vars(I) do
18   dom(y).restoreUpto(|I| + 1) // domains are restored
19   dom(x).removeValue(a, |I|) // a is removed from dom(x)
20   consistent ← dom(x) ≠ ∅ ∧ GAC(P)
21  if ¬consistent then
22   finished ← true

Algorithm 15 enforces MAC on a constraint network *P*. GAC is initially enforced at each node (Line 1). MAC select a new unassigned variable to assign (Line 7), GAC is then enforced on *P* (unlike FC). If after the assignment of *x*, *P* is consistent and all variables are assigned, a solution is then found. Otherwise (*P* is not GAC-consistent), a backtrack is performed (Lines 14 - 19) until *P* becomes GAC-consistent. Inconsistent values are removed to avoid such failures in the future.
1.6 Heuristics

To guide a CSP instance solving, we may ensure at each node of the search tree
that the “right” decisions are made. Algorithms presented in Section 1.5 don’t
propose any order in which the variable are assigned or the values are chosen. At
a given node of search, the choice of a literal (x, a) is determined by an heuristic
that evaluates the “best” variable and the “best” value among all the possible
candidates.

According to [Wallace, 2005], two principles are used in heuristics: “fail first” and “promise” principles. Usually, variable ordering heuristics use the “fail first” principle and “promise” principle for value ordering heuristics. For the variables heuristics, we distinguish three categories:

1.6.1 Static Variable Ordering (SVO)

For these heuristics, the order is defined before search from the problem struc-
tures. As a consequence, the same priority order is conserved during the search.
For example:

• lexico : the variables are ordered by a lexicographical order of their names.

* deg: the variables are ordered by their degrees. A variable degree of variable corresponds to the number of constraints in which the variable is involved. We distinguish *maxDegree* (respectively *minDegree*) which corresponds to a decreasing order (respectively increasing order) of degrees.

1.6.2 Dynamic Variable Ordering (DVO)

These heuristics exploit different information on the problem current state in
order to determine the most promising variable at a search node. For example:

* ddeg: Variables are ordered in a decreasing order of their “current” degree. In other words, *ddeg* chooses first the variable connected to the greatest number of unassigned variables.

* dom/ddeg [Bessiere and Régin, 1996]: This dynamic heuristic chooses first the variable having the smallest ratio:

$$
\frac{\text{current domain size}}{\text{ddeg}} \qquad (1.1)
$$

1.6.3 Adaptive Variable Ordering (AVO)

AVO heuristics combine the dynamic and static information of the problem.
They exploit information about past states of the search, which are not only
about the current branch but also on the branches already explored.
1.6. HEURISTICS

* wdeg: Variables are ordered in a decreasing order of their “current” weighted degree. In fact, for each constraint corresponds a weight which is incremented each time it is violated during search. As a consequence, variables involved in the constraints that are often violated, have the highest priority.

* dom/wdeg [Boussemart et al., 2004]: This dynamic heuristic chooses first the variable having the smallest ratio:

$$ \frac{\text{current domain size}}{\text{wdeg}} \qquad (1.2) $$

* Impact [Refalo, 2004]: This heuristic is based on the impact of an assignment. In fact, the impact is evaluated with respect to the average space search reduction after an assignment. The variable impact is the sum of the assignments impacts of each value of its domain. This impact is maintained during search.

* Counting-Based heuristic [Pesant et al., 2012]: This heuristic aims to keep most of solutions when assigning variables. This is done by determining what proportion of solutions to each constraint agrees with that assignment.

* Activity-Based heuristic [Michel and Hentenryck, 2012]: This heuristic chooses variables based on their activity during propagation. In fact, for each variable *x* corresponds a counter which measures its activity that corresponds to how often the domain of *x* is reduced during the search. This counter is maintained during search.
# Chapter 2

## Compression and Parallel computing

### Contents

<table><tr><td>2.1</td><td>Compression techniques</td><td>72</td></tr><tr><td>2.1.1</td><td>Compact representation of table constraints</td><td>72</td></tr><tr><td>2.1.2</td><td>Compression-based approaches</td><td>78</td></tr><tr><td>2.2</td><td>Parallel computing</td><td>91</td></tr><tr><td>2.2.1</td><td>Definitions</td><td>92</td></tr><tr><td>2.2.2</td><td>Parallel performance measurements</td><td>93</td></tr><tr><td>2.2.3</td><td>Parallel programming models</td><td>96</td></tr><tr><td>2.2.4</td><td>CSP solving using parallel programming models</td><td>100</td></tr></table>
## 2.1. COMPRESSION TECHNIQUES

In this chapter, we introduce the state-of-the-art of both compression and parallel computing. This chapter is organized as follows:

* we describe several compression-based approaches for table constraints in Section 2.1;

* we describe parallel computing features and models and we present related parallel CSP approaches in Section 2.2.

## 2.1 Compression techniques

Table constraints are important for modeling parts of many problems, but they admit practical limitations because they are sometimes too large to be represented in a direct way. In order to reduce space and/or time complexity, researchers have focused on various forms of compression. In Section 2.1.1, we present several compact data structures used in the representation of table constraints. Moreover, in Section 2.1.2, we introduce some compression-based approaches using both compact representation and optimized filtering.

### 2.1.1 Compact representation of table constraints

Several compact data structures aim to reduce the space required to represent these constraints. We distinguish tries [Gent et al., 2007], Multi-valued Decision Diagrams (MDDs) [Cheng and Yap, 2010] and Deterministic Finite Automata (DFA) [Pesant, 2004]. These approaches use general structures to represent table constraints in a compact way, so as to facilitate the filtering process.

#### Tries

A trie [Fredkin, 1960], also called “prefix” tree, is an ordered data structure used to store and retrieve, usually, strings. All the children of a node have a common prefix which allows to represent a large set of values composing a language. The term *trie* comes from the word *retrieval*. In a trie, edges are labeled with a symbol of the language. As a result, to read a word, it is required to go through all the path starting from the root to the leaf or to the node ending this word. Each node contains some information. Values are associated with leaves or inner nodes ending a word. These values correspond to keys of interests such as frequency or weight. Seeking for a word in a trie is done in $O(k)$ time; where $k$ is the length of a search string.

**Example 12** In Figure 2.1, nodes represent the word read from the root until that node and keys are listed for the nodes corresponding to a word form the English language (bold circles). Each complete English word has an arbitrary integer value associated with it.
## 2.1. COMPRESSION TECHNIQUES

<figure><img src="image_24.png" /><figcaption>Figure 2.1: A trie of English words.</figcaption></figure>

In [Gent et al., 2007] tries are first used to represent a table of *n-ary* constraint *c*. The different levels of the trie are the different variables in `scp(c)`. To each variable corresponds a level. The variables are assigned to levels in the same order in which they appear in the scope of the constraint. The language used to label the edges is the domain of the variables. All paths from the root have the same length since all tuples are a combination of the same number of values (*r*).

**Example 13** Figure 2.2 illustrates the trie (Figure 2.2(b)) built from the positive table constraint $c_{xyz}$ defined in extension (Table 2.2(a)) as in [Gent et al., 2007]. The three variables involved in $c_{xyz}$ are the three levels of the trie. Tuples sharing the same first value(s) share the same first edge(s) in the trie. For example, tuples $\tau_1$ and $\tau_2$ have the same literal $(x, a)$ in $c_{xyz}$ which is represented by the edge labeled by a in level 1. Moreover, tuples $\tau_6$ and $\tau_7$ have two literals in common which are $(x, c)$ and $(y, c)$. This is the reason that they share the edge labeled *c* in the first level and its child edge labeled *c* in the second level. The total number of edges of this trie is 15. In this figure, all paths are ending by a true node ⌜ meaning that all illustrated tuples are allowed by the constraint.

Since tries allow us to share prefixes which reduce space complexity, different tests of validity can be avoided at the first levels which may be advantageous to reduce time complexity. In some cases, one single validity test may prevent us from useless tests for a huge number of tuples, but this depends on the order of the scope of the constraint. However, in [Gent et al., 2007], authors used *r* tries for each constraint; each one corresponds to a variable (the order of the scope is changed: the first level is dedicated to this variable); to speed up support seeking which penalizes the space complexity required to represent such constraints.

Algorithm 16 describes GAC enforcement on a trie. In fact, this algorithm looks for a valid support $\tau$ for a literal $(x, a)$ and returns it if it exists. `trie(x, a)` is
## 2.1. COMPRESSION TECHNIQUES

<table><caption>(a) Positive table constraint $c_{xyz}$.</caption><thead><tr><th></th><th>x</th><th>y</th><th>z</th></tr></thead><tbody><tr><td>τ<sub>1</sub></td><td>a</td><td>b</td><td>a</td></tr><tr><td>τ<sub>2</sub></td><td>a</td><td>c</td><td>c</td></tr><tr><td>τ<sub>3</sub></td><td>b</td><td>a</td><td>c</td></tr><tr><td>τ<sub>4</sub></td><td>b</td><td>b</td><td>a</td></tr><tr><td>τ<sub>5</sub></td><td>b</td><td>b</td><td>b</td></tr><tr><td>τ<sub>6</sub></td><td>c</td><td>c</td><td>a</td></tr><tr><td>τ<sub>7</sub></td><td>c</td><td>c</td><td>b</td></tr></tbody></table>

<figure><img src="image_25.png" /><figcaption>Figure 2.2: A trie representation of a table constraint.</figcaption></figure>

**Algorithm 16: SeekValidSupportTrie(x: variable, a: value): Tuple**

```c
// τ is the valid support which is the output
1 τ[x] ← a
2 return extendSupport(trie(x, a), τ)
```

the root node of the sub-trie that contains all levels except the one corresponding to variable *x*. Algorithm 16 is a recursive function that performs a depth-first search (Lines 3 - 9). If this function returns *nil* (Line 10), there doesn't exit any support for the literal (*x*, *a*) on the constraint represented by the trie. Otherwise, the support is returned at Line 2 when the search achieves a *true* node $\mathbf{1}$.

## Multi-valued Decision Diagrams

Using a trie data structure allows to discard prefix redundancy. Decision Diagrams allows to discard both prefix and suffix redundancy which is used in [Cheng and Yap, 2010, Cheng and Yap, 2006]. This reduces the size of represented data and also prevents from redundant tests especially in the lower levels
## 2.1. COMPRESSION TECHNIQUES

<caption>**Algorithm 17:** extendSupport(*node*: Node, *τ*: Tuple): Tuple</caption>

1. **if** *node* = ∅ **then**
2.   **return** *τ*
3.   *x* ← *node*
4.   **foreach** *child* ∈ *node*.getChildren() **do**
5.     **if** *child*.value ∈ *dom*(*x*) **then**
6.       *τ*[*x*] ← *child*.value
7.       *τ'* ← *extendSupport*(*child*, *τ*)
8.       **if** *τ'* ≠ *nil* **then**
9.         **return** *τ'*
10.    **return** *nil*

which is the case for tries. A Multi-valued Decision Diagram (MDD) is an arc-labeled *Directed Acyclic Graph* (DAG). An MDD contains *n* levels such that each level corresponds to a variable. Each edge is labeled by a symbol of the language represented by the MDD. An MDD is either the *t*-terminal (allowed values) or *f*-terminal (disallowed values). If all domains are binary the decision diagram is called “binary” (Binary Decision Diagram (BDD) [Bryant, 1986]).

**Example 14** Figure 2.3 illustrates the *t*-terminal MDD corresponding to the positive table constraint $c_{xyz}$ defined in extension (Table 2.2(a)). The three variables involved in $c_{xyz}$ are the three levels of the MDD. Tuples sharing the same first value(s) or/and the same last value(s) have the same edge(s) in the depicted MDD. For example, tuples $\tau_2$ and $\tau_3$ have the same suffix $(z, c)$ that is why they share the same edge labeled *c* in the level 3. Tuples $\tau_4$, $\tau_5$, $\tau_6$ and $\tau_7$ end either by $(z, a)$ or $(z, b)$ which is translated in MDD by the two shared edges labeled *a* and *b* in the third level. The total number of edges of this MDD is 12.

Algorithm 18 describes *mddc* algorithm. This algorithm doesn't use the revision-based technique meaning that rather than looking for a support for each value, GAC is enforced globally by discarding all GAC-inconsistent values contained in the MDD starting each time from scratch. This may supplant enforcing GAC on tries. In fact, *mddc* keeps for each variable $x_i$ a set $S_i$ of unsupported values of its domain. *mddcSeekSupports* algorithm goes through all nodes of MDD using a Depth First Search (DFS) for traversing the MDD from the root node and updates the sets $S_i$: two main sets are maintained $\xi^{YES}$ for visited and consistent edges (having a positive terminating node: *t*-terminal), and $\xi^{NO}$ for inconsistent edges due to pruned values (having a negative terminating node: *f*-terminal). Since each edge represents a value, after doing a DFS, the values that have not been kept are removed since there is no longer any path from the root
## 2.1. COMPRESSION TECHNIQUES

<figure><img src="image_26.png" /><figcaption>Figure 2.3: MDD built from the table constraint in Figure 2.2(a).</figcaption></figure>

<table><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>ξ<sup>YES</sup> &leftarrow; ∅</td><td></td></tr><tr><td>2</td><td>restore(ξ<sup>NO</sup>, st)</td><td></td></tr><tr><td>3</td><td>foreach i &isin; [1..r] do</td><td></td></tr><tr><td>4</td><td>∫ S<sub>i</sub> &leftarrow; dom(x<sub>i</sub>)</td><td>// values that have no support yet</td></tr><tr><td>5</td><td>Δ &leftarrow; r + 1</td><td></td></tr><tr><td>6</td><td>mddcSeekSupports(G, 1)</td><td></td></tr><tr><td>7</td><td>foreach i &isin; [1..Δ − 1] do</td><td></td></tr><tr><td>8</td><td>∫ dom(x<sub>i</sub>) &leftarrow; dom(x<sub>i</sub>) \ S<sub>i</sub></td><td></td></tr><tr><td>9</td><td>st' &leftarrow; state(ξ<sup>NO</sup>)</td><td></td></tr><tr><td colspan="3">// Maintaining GAC during search</td></tr><tr><td>10</td><td>if ∃S<sub>i</sub> &isin; 𝒳 such that S<sub>i</sub> &ne; ∅ then</td><td></td></tr><tr><td>11</td><td>∫ return(YES, st')</td><td>// domains have changed</td></tr><tr><td>12</td><td>else</td><td></td></tr><tr><td>13</td><td>∫ return(No, st')</td><td></td></tr></tbody></table>

to a t-terminal node corresponding to this value. During search some additional data structures and optimization are used to achieve efficient operations (Lines 1, 2 and 9).

Clearly, in terms of space complexity using MDDs is more advantageous than using trie knowing that, in [Gent et al., 2007], for each constraint *r* tries are required but just one MDD is enough.

In [Perez and Régin, 2014], the authors present MDD4 algorithm, which adapts GAC4 [Mohr and Masini, 1988] algorithm to MDD constraints. The two main improvements are:

* the way MDD is maintained during search: Tuples are not represented
## 2.1. COMPRESSION TECHNIQUES

explicitly in an MDD constraint. They are the different paths from the root to a positive terminal. To enforce GAC, *mddc* checks each time it goes through an edge if its value is still valid. MDD4 algorithm, proposes to delete the inconsistent values, thus its corresponding edges in order to reduce these redundant tests;

* the way *S* lists are maintained: MDD4 establishes a relation between the values in domains and their corresponding edges of the MDD through *S* lists. Hence, for each literal (*x*, *a*), *S*(*x*, *a*) contains the set of edges in the MDD corresponding to this value (labeled with the value *a* in the level *x*). If *S*(*x*, *a*) becomes empty that means that there is no more an edge for this value and then *dom*(*x*) can be reduced by removing *a*.

## Deterministic Finite Automata

A *deterministic finite automata (DFA)* *M* is a 5-tuple (*Q*, Σ, δ, *q*₀, *F*) where:

* *Q* is a finite set of states;

* Σ is a finite set of input symbols called the alphabet;

* δ is a transition function (δ : *Q* × Σ → *Q*);

* *q*₀ is the initial state (*q*₀ ∈ *Q*);

* *F* is a set of final states (*F* ⊆ *Q*).

DFA is a deterministic finite state machine which accepts/refuses a finite set of symbols contained in the alphabet Σ. Starting from the initial state *q*₀, the state machine transition for each symbol, considering the transition function δ, from a state to another. If one of the final states included in *F* is reached, the input word is said “accepted” by the state machine. As a consequence, the set of accepted words compose the “regular” language recognized by *M* and denoted *L*(*M*).

**Example 15** Figure 2.4 illustrates the DFA representation of the positive table constraint *c*<sub>xyz</sub> defined in extension (table in Figure 2.4(a)). The regular expression representing table[*c*<sub>xyz</sub>] is (a + b)(bc + c(a + b)).

DFA is used in [Pesant, 2004] to represent a global constraint called *regular* which is a kind of global constraint generalizing the stretch constraint introduced in [Pesant, 2001]. This type of constraint is used in rostering problem where every team of a working group has an identical schedule as the others but it is out of phase. A regular expression can represent a valid sequence of activities. However, for the *allDifferent* global constraint, the number of states of the associated DFA is exponential in the number of symbols in the alphabet (|*Q*| = 2|Σ|).
## 2.1. COMPRESSION TECHNIQUES

<figure><img src="image_27.png" /><figcaption>Figure 2.4: DFA representation of the table constraint in Figure 2.4(a).</figcaption></figure>

The filtering algorithm used to enforce GAC (presented in [Pesant, 2004]) constructs, in a first stage, a directed multi-graph, and then, collects the set of states that support a value (x, a). In [Tiedemann et al., 2007], the authors prove that MDD reduction gives smaller and more efficient graphs in terms of propagation time than straight DFA unfolding used for the regular constraint.

### 2.1.2 Compression-based approaches

Tries [Gent et al., 2007], Multi-valued Decision Diagrams (MDDs) [Cheng and Yap, 2010] and Deterministic Finite Automata (DFA) [Pesant, 2004] are such general structures, which are used to represent table constraints compactly, so as to speedup filtering. These data structures were introduced previously in Section 2.1.1.

Several approaches propose different compressed representations of table constraints and different ways to filter them. Compressed tuples [Hubbe and Freuder, 1992], Short supports [Nightingale et al., 2011, Nightingale et al., 2013] and Smart tuples [Mairy et al., 2015] present new definitions of supports that differ from the classic ones. Data-mining based approaches [Jabbour et al., 2013a, Jabbour et al., 2013b] compress table constraints giving another representation using data mining features. In this section, we introduce four different categories of compressed tables:
## 2.1. COMPRESSION TECHNIQUES

* Short Supports;

* Cartesian-product based approaches;

* Smart tuples;

* Data-mining based approaches.

In each category, we present an approach that enforces GAC using STR algorithm.

### Short Supports

As presented in Definition 10 in Chapter 1, a literal $(x, a)$ is valid if there exists a valid tuple $\tau$ in the table constraint $c$ such that $\tau[x] = a$. Based on this idea, [Nightingale et al., 2011, Nightingale et al., 2013] proposes a new representation of table constraints in which for each literan $(x, a)$ corresponds the set of its supporting tuples. This form is obtained before search.

In fact, a short support (i.e. tuple) is a generalization of a support tuple defined in Definition 10.

**Definition 24** A short support for constraint $c$ is a valid tuple $s$ built on a subset of $scp(c)$. Whereas, when a support is built on $scp(c)$, it is called a full-length support.

**Example 16** Let us consider the Element [Colton and Miguel, 2001] constraint $z = x_k$ such that $dom(x_0) = dom(x_1) = dom(x_2) = dom(z) \in \{a, b, c\}$ and $dom(k) \in \{0, 1, 2\}$. This constraint is satisfied when the $k^{th}$ variable $x_k$ takes the same value as the variable $z$. $s = \{(x_1, a), (k, 1), (z, a)\}$ is a short support satisfying this constraint. $s$ does not contain a value for each variable, which is the case for variables $x_0$ and $x_2$. As a consequence, any extension of $s$ with valid values for $x_0$ and $x_2$ is a support such as $fs = \{(x_1, a), (k, 1), (z, a), (x_0, b), (x_2, c)\}$.

In [Nightingale et al., 2013], authors use a new symbol to represent the missing variables. In fact, considering a constraint $c$ such that $scp(c) = \{x_1, x_2, x_3, x_4\}$ and a short support (tuple) $\tau = \{(x_1, a), (x_2, b)\}$, $\tau$ is represented as $\tau = \{a, b, *, *\}$ where * indicates that variables $x_3, x_4$ are not mentioned in $\tau$.

SHORTGAC is the algorithm that enforces GAC using short supports. SHORTGAC maintains a set of short supports supporting all the valid values of the variables involved in the scope of this constraint. Classically, enforcing GAC on table constraints means looking for supports for unsupported values. SHORTGAC looks for support in two different ways. First, as for classic tuples, SHORTGAC assumes that a value $(x, a)$ is supported if there exists a short support $s$ such that $s[x] = a$. Second, SHORTGAC considers that a value $(x, a)$ is supported by a short support $s$ if $s$ does not involve $x$, i. e. $\forall v \in dom(x), (x, v) \notin s$.
## 2.1. COMPRESSION TECHNIQUES

In [Nightingale et al., 2011], three main data structures are used in SHORT-GAC algorithm:

* `numSupports`: the total number of valid supports.

* `supportsPerVar[x]`: an array indicating the number of supports supporting each variable `x`.

* `supportsPerLit[x][a]`: a 2-dimensional array indicating the set of short supports containing the literal `(x, a)`.

SHORTGAC algorithm considers that each variable `x` for which `supportsPerVar[x] < numSupport` is fully supported and there is no need to look for supports for this variable. In fact, `supportsPerVar[x] < numSupport` for a variable `x` means that there exists a support `s` that does not involve `x`. As a consequence, `s` is a support for all values in `dom(x)` and so, `x` is supported and the algorithm does not have to look for supports for the literals `(x, a)`. Otherwise, in the case where `supportsPerVar[x] = numSupport` meaning that `x` is involved in all short supports, SHORTGAC seeks for a support for each value `a ∈ dom(x)` for which `|supportsPerLit[x][a]|=0` (i.e. the value has no support).

**Example 17** Let us consider a table constraint $c_{x_1x_2x_3}$ such that the current domains of the variables involved in `scp(c_{x_1x_2x_3})` are: `dom(x_1) = dom(x_3) = \{0, 1, 2\}` and `dom(x_2) = \{0, 1\}`. `table(c_{x_1x_2x_3})` contains two short supports $s_0 = \{(x_1, 0), (x_2, 1)\}$ and $s_1 = \{(x_1, 1), (x_3, 0)\}$. Hence, `numSupports = 2` as depicted in Figure 2.5(c). The data structure supportsPerLit is depicted in Figure 2.5(a) where for each value `(x, a)` corresponds the list of short supports involving it. For example, for the variable $x_3$ only the value `0` is involved in a support of `table(c_{x_1x_2x_3})`. The two remaining values are not contained in any short support. The symbol `×` indicates that a value `(x, a)` is not valid, which is the case for the value `(x_2, 2)`. The supportsPerVar data structure (Figure 2.5(b)) indicates the number of short supports supporting each variable `x` which is the sum of `supportsPerLit[x][a]` for each value `a ∈ dom(x)`. In our case, `supportsPerVar[x_2] = supportsPerVar[x_3]=1` which is less than `numSupports` meaning that both $x_2$ and $x_3$ are fully supported. We have `supportsPerVar[x_1]=numSupports`, so we have to look for a support for `(x_1, 2)` since `|supportsPerLit[x_1][2]|=0`. `table(c_{x_1x_2x_3})` does not contain any support for `(x_1, 2)` so this value is removed and `supportsPerLit[x_1][2]` is updated to `×`.

Experimental results show that in three case studies (Element [Colton and Miguel, 2001], Lex-ordering [Frisch et al., 2002] and Rectangle Packing [Simonis and O'Sullivan, 2008]), SHORTGAC is faster than other methods such as GAC-Schema.
## 2.1. COMPRESSION TECHNIQUES

<figure><img src="image_28.png" /><figcaption>Figure 2.5: SHORTGAC data structures.</figcaption></figure>

Interestingly, Simple Tabular Reduction technique is used in [Nightingale et al., 2013] to enforce GAC on short supports (SHORTSTR2). The main feature is that when a short support does not involve some variable $x$, it supports all values of $x$, this is called *implicit support*. SHORTSTR2 is a slight modified version of STR2 taking into consideration this new form of a tuple. Experimental results do not show a huge compression ratio, but a GAC algorithm that competes with STR2.

### Cartesian-Product based approaches

Cartesian product is another classical mechanism to represent compactly large sets of tuples. For instance, it has been applied successfully for handling sets of solutions [Hubbe and Freuder, 1992, Régin, 2011b], symmetry breaking [Focacci and Milano, 2001, Fahle et al., 2001], and learning [Katsirelos and Bacchus, 2005, Lecoutre et al., 2007]. So far, this form of compression has been used in two distinct GAC algorithms for table constraints: by revisiting the general GAC-schema [Katsirelos and Walsh, 2007] and by combining compressed tuples with STR [Xia and Yap, 2013]. In fact, rather than listing allowed tuples in $rel(c)$, Cartesian products are used (See Definition 2)

**Example 18** We give an example of a relation $rel(c)$ defined over three variables $x$, $y$ and $z$ with $dom(x) = dom(y) = dom(z) = \{a, b\}$.

$$rel(c) = \left\{ \begin{array}{l} (b, a, a), \\ (b, a, b), \\ (b, b, a), \\ (b, b, b) \end{array} \right\}$$

Using Cartesian product $rel(c)$ could be represented by one compressed tuple as follows:

$$rel(c) = \{ (\{b\}, \{a, b\}, \{a, b\}) \}$$
## 2.1. COMPRESSION TECHNIQUES

In [Xia and Yap, 2013], Cartesian product is used to compress tuples, called c-tuples, in table constraints. Figure 2.6 illustrates the table constraint representation using c-tuples. The first eight tuples are compressed in $\tau_{c0}$ as a Cartesian product listing the possible values that could be taken by each variable.

<figure><img src="image_29.png" /><figcaption>Figure 2.6: c-tuple representation.</figcaption></figure>

To enforce GAC on such tables, authors proposed two algorithms STR2-C (compressed tuples STR2 variant) and STR3-C based on STR2 and STR3 variants. We only illustrate the STR2-C algorithm. The validity of a c-tuple [Focacci and Milano, 2001, Katsirelos and Walsh, 2007] is defined as: a c-tuple is valid if the Cartesian product contains at least one valid tuple. As a consequence, unlike STR2 which considers that all values belonging to a valid tuple are GAC consistent, the valid c-tuple, in STR2-C, may contain GAC-inconsistent values which implies more consistency tests for that c-tuple. That is the reason why, a pointer is used to separate the inconsistent values from the unchecked ones for each variable (similar to *currentLimit* pointer).

Let us consider the example in Figure 2.6 and assuming that the value $(x_4, a)$ is removed, $\tau_0, \tau_2, \tau_4$ and $\tau_6$ (in Figure 2.6(a)) are no more valid. However, in the compressed table (in Figure 2.6(b)) using c-tuple, we cannot remove tuple $\tau_{c0}$ since it contains tuples $\tau_1, \tau_3, \tau_5$ and $\tau_7$ that are still valid which implies the validity of $\tau_{c0}$.

Experimental results show that STR2-C and STR3-C are competitive with STR variants when the table can be compressed enough to outweigh the additional costs. However, encoding table constraints as a set of c-tuples remains difficult since it is not done in a natural way.

### Smart Tables

Smart table constraints [Mairy et al., 2015] are a new compact representation of table constraints using arithmetic constraints which reduce significantly the
## 2.1. COMPRESSION TECHNIQUES

memory space required to encode such combination of values.

**Example 19** Let us consider the table constraint $c_{x_1x_2x_3}$ depicted in Figure 2.7(a) such that $dom(x_1)=dom(x_2)=dom(x_3)=\{0,1,2\}$. This table constraint could be represented using arithmetic constraints as in the Smart table constraint depicted in Table 2.7(b). In fact, in all tuples of $c_{x_1x_2x_3}$ the value of the variable $x_1$ is always equals to the value of the variable $x_3$. This explains the first arithmetic constraint $x_1 = x_3$ in $sc_{x_1x_2x_3}$. All the values taken by the variable $x_2$ are less or equal to 1 ($x_2 \le 1$). The symbol $*$ taken by the variable $x_3$ is the same used in [Nightingale et al., 2013].

<figure><img src="image_30.png" /><figcaption>Figure 2.7: Smart table representation.</figcaption></figure>

Smart table constraints could be considered a disjunction of conjunctions of basic arithmetic constraints since each smart tuple contains a conjunction of basic arithmetic constraints. Smart table constraints are an interesting tool to express different global constraints.

The filtering algorithm used for smart table constraints, called smartSTR, is inspired from STR. In fact, we associate for each smart tuple $sc$ a sub-problem $P_{sc}$ which is represented by tree-like structure (forest of trees) collecting all valid values supporting the arithmetic constraints of $sc$. smartSTR checks sequentially all the valid smart tuples. However, the only difference between smartSTR and the classic STR is the way that valid values (i. e. supports) set is maintained. Since the supported values in smart tuples are stored in trees, a smart tuple is considered valid iff each tree (corresponding to each arithmetic constraint) has at least one solution.

Experimental results show an important spatial and time complexity reduction using smart table constraints instead of classic table constraints. These results competes with SHORTGAC and outperforms it especially when table constraints are larger.

Short supports, compressed tuples and smart tuples introduced in the previous sections are a generalization of classical tuples in tables of constraints.
## 2.1. COMPRESSION TECHNIQUES

These new representations don't offer the same fluency in the expression of such constraints especially to non-expert users. C-tuples and short supports need a compression algorithm to transform a classical table constraint. However, smart table offers a facility of expression of constraints. In fact, it can be considered a tool that combines intentional, extensional and global constraints. It is also possible to use C-tuples and short supports as smart tuples. For example, a short support {$a, b, *, *$} is also a smart tuple since both techniques use the "*" symbol. A c-tuple can be represented as a smart tuple as follows: $\tau_{c0} = \{{\{a\}, \{a, b\}, \{a, b\}, \{a, b\}\}}$ is written as $sc = \{\in \{a\}, \in \{a, b\}, \in \{a, b\}, \in \{a, b\}\}$.

### Data-mining based approaches

Other techniques of compression based on data-mining techniques are used in order to reduce the size of table constraints. We first introduce the different features used in data mining that are used in our contribution in Chapter 3 and then we explore the related works using this technique.

**Data-mining features** Data mining is the process of discovering interesting knowledge from a large amount of data. Since the development of computer science, there has been an information explosion, which is increasing in a fast way. The problem was not any more a simple problem of storage of information, but rather the way to analyze this important heap of data, which led to the development of data mining techniques (since the beginning of 1990s). That is why the main objective of data mining consists in looking for and extracting “useful” information from a big amount of data stored in databases or warehouses.

In the field of data mining, a pattern is composed of a set of items, called **itemset**. This term comes from the domain of the supermarkets systems (the market basket) [Agrawal et al., 1993] which was the source of inspiration for the domain of data mining. In the analysis of a basket, the data consist in a number of purchases realized by the customers. Every transaction consists of a number of articles, which a customer bought together. In Data mining, a pattern could be of different types: a word, a sentence, a sequence of molecules or nucleotides in the case of looking for a sequence DNA [Witten and Frank, 2005], etc. In the context of our contribution, a pattern is a set of values taken by variables.

**Definition 25 (Transactional Database)** Let $I = \{a_1, a_2, ..., a_m\}$ be a set of items such as products (Juice, Bread, Milk, ..., and so on). DB is a set of transactional database $DB = \{T_1, T_2, ..., T_n\}$ where each transaction $T_i$ is a set of items such that $T_i \subseteq I$. Each transaction is associated with a unique identifier, transaction identifier (TID)

The concept of *frequent itemset* was introduced for transactions databases.
## 2.1. COMPRESSION TECHNIQUES

**Definition 26 (Frequent pattern)** Let $I = \{a_1, a_2, \dots, a_m\}$ be a set of **items**, and a transaction database **DB**. The **support count** $\sigma$ (or occurrence frequency) of a pattern $\mu$, which is a set of items, is the number of transactions containing $\mu$ in **DB**. The **support** $s$ of a pattern $\mu$ is the fraction of transactions that contains $\mu$, $s(\mu) = \sigma(\mu)/|DB|$.

$\mu$ is a **frequent pattern** if $\mu$'s support is greater than a predefined minimum support threshold $minSup$ such that $minSup \in [0, 1]$.

A k-itemset $\mu$ consists of k items of $I$. The set of frequent patterns is defined:

$$F(DB, min\_sup) = \{\mu \subseteq I | s(\mu) \geq min\_sup\} \quad (2.1)$$

**Example 20** Let us consider the transaction database depicted in Table 2.1, which represents different market baskets and their contents:

<table><caption>Table 2.1: Transaction database of different market baskets.</caption><thead><tr><td>TID</td><td>Items</td></tr></thead><tbody><tr><td>1</td><td>Bread, Milk</td></tr><tr><td>2</td><td>Bread, Cookies, Juice, Eggs</td></tr><tr><td>3</td><td>Milk, Cookies, Juice, Coke</td></tr><tr><td>4</td><td>Bread, Milk, Cookies, Juice</td></tr><tr><td>5</td><td>Bread, Milk, Cookies, Coke</td></tr></tbody></table>

As said before, an itemset is a collection of one or more items. {$Bread, Milk, Cookies$} is a 3-itemset.

**Support count ($\sigma$):** $\sigma(\{Bread, Milk, Cookies\})=2$, since this itemset appears two times in transaction database.

**Support:** $s(\{Bread, Milk, Cookies\})=2/5$ represents the fraction of transactions that contains this itemset.

Let $minSup$ be equal to $2/5$, the pattern {$Bread, Milk, Cookies$} is frequent since $s(\{Bread, Milk, Cookies\}) \geq minSup$. For simplicity, we use the support terminology to represent a **support count ($\sigma$)** in the next examples. It is important to note that the term support refers, in data mining context, to the frequency of a pattern which is different from the one used in a CSP context.

Several data mining algorithms, such as Apriori [Agrawal and Srikant, 1994] and Frequent-Pattern Growth (FP-Growth) [Han et al., 2000] among others (See more in [Wu et al., 2008]), can be used to identify frequent patterns. We are only introducing FP-Growth [Han et al., 2000, Han et al., 2004] algorithm since we use it in our contribution (Chapter 3). This choice is made since FP-Growth seems to be the suitable algorithm to use for our compression
## 2.1. COMPRESSION TECHNIQUES

process since it offers the best frequent patterns detection in terms of space and time. In fact, FP-Growth constructs a Frequent Pattern Tree (FP-Tree) from a transaction database, which satisfy the minimum support (minSup) [Pramod and Vyas, 2010]. This algorithm does not use the candidate generation technique, which is a feature that consists in generating k-itemsets from (k − 1)-itemsets, and due to the compact structure used it does not require a huge memory space. Moreover, this algorithm requires only two scans of the transaction database.

The FP-Growth algorithm is composed of two main steps:

**Step 1: FP-Tree construction** This step consists of building the compact data structure called FP-Tree. This construction is done using one pass over the data-set. The algorithm:

1. detects the frequent items;

2. orders the transactions with respect to a decreasing order based on the items frequencies;

3. removes the infrequent items taking into consideration the minimal support threshold fixed.

**Example 21** Let us consider a transaction database DB presented in Figure 2.8(a):

<figure><img src="image_31.png" /><figcaption>Figure 2.8: Transaction database evolution.</figcaption></figure>

1. calculating support: s(B)=8; s(A)=7; s(C)=5; s(D)=4; s(E)=1.
## 2.1. COMPRESSION TECHNIQUES

2. ordering itemsets: all transactions in the Figure 2.8(b) are ordered taking into account a decreasing order of items support.

3. removing infrequent items: if we consider minSup=5, we have to remove items D and E since they are not frequent. Figure 2.8(c) illustrates the final result.

After ordering the transaction database and removing from it infrequent items, the algorithm builds an FP-Tree using one pass over the transaction database. An FP-Tree is, in fact, a trie (see Section 2.1.1) where each branch represents the frequent part of a transaction. Each node of an FP-Tree contains the number of branches which share that node, and labeled with the concerned item. The root node does not have any label. FP-Growth reads one transaction at a time and maps it to a path: a path, from the root, composed of the frequent items of the transaction is added to the FP-Tree. The decreasing order of support is used. Paths can overlap when a transaction $T_i$ shares the same items as a prefix with a transaction $T_j$. In this case, the nodes counters are incremented. The more paths are overlapped, the higher the compression is. The nodes labeled with the same value are linked with a dashed link. This is used in the patterns extraction step.

The FP-Tree allows us to obtain a smaller size of data than the uncompressed data especially when many transactions share several items. The size of the tree depends on how the items are ordered. Data-mining techniques experts usually use a decreasing order based on support, but it does not always lead to the smallest tree [Han et al., 2004].

**Example 22** Figure 2.9 illustrates the different step of the FP-Tree construction. In Figure 2.9(a), we add a path corresponding to transaction 1 of the database. In Figure 2.9(b), transaction 2 shares prefix “b” with the path added previously which explains the fact that the two paths share node “b”. The counter of this node is, thus, incremented. In Figure 2.9(c), we add the path corresponding to transaction 3. The value “a” already exists in the FP-Tree, that is why the two nodes labeled with the value “a” are linked with a dashed link. This is the case for the nodes labeled with the value “c”. Adding transaction 4, increments the two nodes “b” and “a” since the path exists already (Figure 2.9(d)). Transaction 5 adds the node “c” at the end of the path $b \to a$ while incrementing the nodes counters (Figure 2.9(e)). All the remaining transactions correspond to existing path (see Figures 2.9(f), 2.9(g), 2.9(h), 2.9(i) and 2.9(j)). Figure 2.9(j) depicts the final FP-Tree obtained at the end of step 1.

**Step 2: Frequent Itemset Generation** This step consists in extracting the frequent itemsets from the FP-tree. This extraction is done using a bottom-up algorithm, which detects frequent itemsets starting from leaves to the root.
## 2.1. COMPRESSION TECHNIQUES

<figure><img src="image_32.png" /><figcaption>Figure 2.9: FP-tree construction by adding the different transactions.</figcaption></figure>

First, we extract prefix path sub-trees ending in an item or an itemset. Then, each prefix path sub-tree is processed recursively to extract the frequent itemsets. To check if the ending item is frequent, FP-Growth accumulates linked counters and verify if the sum is greater than minSup threshold. If it is the case, the endings are removed from the sub-tree and the process is repeated this time to check if we can add another item to this suffix. To do that, the algorithm uses the conditional FP-Tree, which is an FP-Tree that would be built if we only consider transactions containing a particular itemset.

**Example 23** Figure 2.10 represents all sub-trees ending respectively with “a”, “b” and “c”. In fact, to obtain such sub-trees, the edges not ending by such values are removed. All these sub-trees are extracted from the complete FP-Tree
## 2.1. COMPRESSION TECHNIQUES

represented in Figure 2.9(j).

For example, Figure 2.11 represents conditional FP-Trees on “a” (Figure 2.11(d)) and “c” (Figure 2.11(c)), which is the updated sub-tree of the ones presented in Figures 2.10(a) and 2.10(c). In fact, to obtain Figure 2.11(c), we only consider transactions that contain the item “c”. In each remaining transaction, only the items before the item “c” are represented. It is equivalent to keeping only the paths ending by the node “c”, from the FP-Tree represented in Figure 2.9(j), and removing all edges pointing to the node “c”. This step aims to look for eventual frequent items, added to “c”, we obtain a frequent itemset. This is not the case for this conditional FP-Tree since $s(a) = 1 + 2 = 3 < \minSupport = 5$. In the case of condition FP-Tree on “a”, we have $s(b) = 5 = \minSupport$. As a consequence, “a” and “ba” are two frequent itemsets ending in “a” extracted from FP-Tree. The result of this step is represented in Table 2.2 where the results of sub-trees are merged for the same suffix.

<figure><img src="image_33.png" /><figcaption>Figure 2.10: Prefix path sub-trees.</figcaption></figure>

<table><caption>Table 2.2: The frequent itemsets ($\minSupport=5$).</caption><thead><tr><td>Suffix</td><td>Frequent Itemsets</td></tr></thead><tbody><tr><td>a</td><td>{a}, {b, a}</td></tr><tr><td>b</td><td>{b}</td></tr><tr><td>c</td><td>{c}</td></tr></tbody></table>

**Data-mining based approaches: related works** In Jabbour et al., 2013b, data-mining techniques are used to reduce the size of propositional formulae in Conjunctive Normal Form (CNF). This approach is extended to CSP [Jabbour et al., 2013a]. In fact, additional variables and values are needed, and constraints are reformulated using Tseitin extension principle [Tseitin, 1983]. This principle consists in converting a Disjunctive Normal Form (DNF) formula which is a disjunction of conjunctions to a CNF formula which is a conjunction
## 2.1. COMPRESSION TECHNIQUES

<table><caption>(a) Data-set: transactions ending in c.</caption><thead><tr><td>TID</td><td>Items</td></tr></thead><tbody><tr><td>1</td><td>{B, A}</td></tr><tr><td>2</td><td>{B, C}</td></tr><tr><td>3</td><td>{A, C}</td></tr><tr><td>4</td><td>{B, A}</td></tr><tr><td>5</td><td>{B, A, C}</td></tr><tr><td>6</td><td>{B}</td></tr><tr><td>7</td><td>{A}</td></tr><tr><td>8</td><td>{B, A, C}</td></tr><tr><td>9</td><td>{B, A}</td></tr><tr><td>10</td><td>{B, C}</td></tr></tbody></table>

<figure><img src="image_34.png" /><figcaption>(c) FP-Tree conditional on c.</figcaption></figure>

<table><caption>(b) Data-set: transactions ending in a.</caption><thead><tr><td>TID</td><td>Items</td></tr></thead><tbody><tr><td>1</td><td>{B, A}</td></tr><tr><td>2</td><td>{B, C}</td></tr><tr><td>3</td><td>{A, C}</td></tr><tr><td>4</td><td>{B, A}</td></tr><tr><td>5</td><td>{B, A, C}</td></tr><tr><td>6</td><td>{B}</td></tr><tr><td>7</td><td>{A}</td></tr><tr><td>8</td><td>{B, A, C}</td></tr><tr><td>9</td><td>{B, A}</td></tr><tr><td>10</td><td>{B, C}</td></tr></tbody></table>

<figure><img src="image_35.png" /><figcaption>(d) FP-Tree conditional on a.</figcaption></figure>

<caption>Figure 2.11: Conditional FP-Tree.</caption>
## 2.2. PARALLEL COMPUTING

of disjunctions by introducing new variables in order to prevent combinatorial explosion due to such conversion. Let us consider a DNF:

$$ (x_1 \land \dots \land x_l) \lor (y_1 \land \dots \land y_m) \lor (z_1 \land \dots \land z_n) $$

The conversion of this DNF to a CNF using the distributive characteristic of disjunction over conjunction causes a combinatorial explosion:

$$ (x_1 \lor y_1 \lor z_1) \land (x_1 \lor y_1 \lor z_2) \land \dots \land (x_l \lor y_m \lor z_n) $$

Applying Tseitin extension principle, by using additional variables $(t_1, t_2, t_3)$, we get:

$$ (t_1 \lor t_2 \lor t_3) \land (t_1 \rightarrow (x_1 \land \dots \land x_l)) \land (t_2 \rightarrow (y_1 \land \dots \land y_m)) \land (t_3 \rightarrow (z_1 \land \dots \land z_n)) $$

Authors extend this technique to CSP and especially table constraints. This is introduced by Figure 2.12 which illustrates the Rewriting Rule used to reduce table constraints based on Tseitin extension principle. Let us consider the positive table constraint $c$ in Figure 2.12(a) and the itemset $I = \{(x_1, 0), (x_3, 0)\}$ which occurs four times. In order to compress $c$, authors propose to add a new variable $z$ and two new values $c_1$ and $c_2$, such that $dom(z) = \{c_1, c_2\}$. In fact, these values will replace the possible combination of values taken by $x_1$ and $x_3$ in the compressed table constraint such that $c_1 \rightarrow (0, 0)$ and $c_2 \rightarrow (0, 1)$. The Rewriting Rule presented in this paper generate two new constraints $c_0$ which is defined in Figure 2.12(b), such that $scp(c_0) = \{z, x_1, x_3\}$ and $c'$ which is the compressed form of table constraint defined in Figure 2.12(c). The space required to represent the standard table constraint, not including the cost of the scope and variables, is $8 \times 4 = 32$, however, for the compressed table constraint it is equal to $3 \times 2 + 8 \times 3 = 30$. To the best of our knowledge, no experimentation on this approach was conducted, which prevents us from concluding about the efficiency of this approach. In other terms it is not clear if the compression is high enough to outweigh the cost of additional variables and values.

## 2.2 Parallel computing

Parallel computing has evolved during these last decades. It is no longer the matter of high equipped data centers since computers keep evolving to a higher number of processors. With the emergence of multicore processors <fnref n="1" />, application need parallelism to exploit all available power of a machine offering this type of architecture. The Central Processing Unit (CPU) of computers has more and more cores which speeds up computing tasks. Graphics Processing Unit (GPU) is another unit which manipulates computer graphics and image processing. This

<footnote n="1">¹A multi-core processor is an integrated circuit to which two or more processors have been attached in order to enhance performance by processing simultaneously multiple tasks.</footnote>
### 2.2.2 Parallel performance measurements

To evaluate parallel solutions several metrics are used, but the most important one is speedup.

#### Speedup

*Speedup* describes how much faster a parallel algorithm runs with respect to the best sequential one. For a problem of size *n*, the *speedup* $S_p$ is expressed as follows:

$$S_p = \frac{T_s}{T_p} \qquad (2.2)$$

where $T_s$ is the resolution time of the sequential algorithm and $T_p$ is the resolution time of a parallel algorithm on *p* processors. We mean by resolution time the wall clock time required to finish the resolution.

If the speedup increases *linearly* as a function of *p*, then we speak of *linear speedup*. Linear speedup means that the overhead of the algorithm is always in the same proportion with its running time, for all *p*. In the particular case of $T_p = T_s/p$, we then speak of *perfect linear speedup*. In practice, most programs achieve sub-linear speedup ($T_p \ge T_s/p$). When $T_p \le T_s/p$, we achieve a super-linear speedup. Figure 2.13 shows the four possible speedups. If a problem cannot be

<figure><img src="image_36.png" /><figcaption>Figure 2.13: Possible speedup curves.</figcaption></figure>

completely parallelized (one of the causes for sub-linear speedup), only a partial speedup is expected. Hence, rather than considering the speedup expressed in Equation 2.2 Amdahl and Gustafson proposed each one an expression, called a law of speedup. The two laws give different points of view about the execution time scale with the number of processors for computing partial speedup.
## 2.2. PARALLEL COMPUTING

**Amdahl's law** Amdahl's law [Amdahl, 1967] expresses the maximum expected overall speedup of a sequential algorithm using $p$ processors as follows:

$$S(p) = \frac{T_s}{T_p} = \frac{t_s + t_p}{t_s + \frac{t_p}{p}} \qquad (2.3)$$

where $t_s$ is the computation time needed for the sequential part and $t_p$ is the computation time needed for the parallel part.

Let $\alpha$ denote the sequential portion of the computation:

$$\alpha = \frac{t_s}{t_s + t_p} \qquad (2.4)$$

We get, then

$$S(p) = \frac{1}{\alpha + \frac{(1-\alpha)}{p}} \qquad (2.5)$$

If $p \mapsto \infty$:

$$S(p) = \frac{1}{1 - \alpha} \qquad (2.6)$$

which means that if we assume that a computer has as many processors as we want the maximum expected speedup is $\frac{1}{1-\alpha}$. If we take the example of a sequential algorithm requiring 10 hours using a single processor core and only 9 hours could be parallelized, the maximum expected speedup is $10(\frac{1}{10})$. Amdahl's law is useful for algorithms that need to scale its performance as a function of the number of processors, fixing the problem size $n$. This type of scaling is known as strong scaling. However, this law does not fully exploit the computing power that becomes available as the number of cores increases. Figure 2.14 illustrates the total work evolution with respect to Amdahl's law where $\varepsilon \mapsto 0$ when the number of cores $\mapsto \infty$. The assumption is “the problem size does not change with the number of CPUs”.

**Gustafson's law** Rather than fixing a problem size, Gustafson's law [Gustafson, 1988] uses fixed-time model. This model considers that the work per processor is fixed when increasing the number of processors $p$ and the size of the problem $n$. Gustafson's law states that the time of a parallel system is composed of the computation time needed for the sequential part $t_s^*$ and the computation time needed for the parallel part $t_p^*$ executed by $p$ processors ($T(p) = t_s^* + t_p^*$). The expected speedup is expressed as follows:

$$S(p) = \frac{t_s^* + t_p^*p}{t_s^* + t_p^*} \qquad (2.7)$$

Let $\alpha^*$ denote the sequential portion of the computation on the parallel system:

$$\alpha^* = \frac{t_s^*}{t_s^* + t_p^*} \qquad (2.8)$$