Frédéric Pennerath
email: frederic.pennerath@centralesupelec.fr

An Efficient Algorithm for Computing Entropic Measures of Feature Subsets

Keywords: Pattern mining, Entropic measures, Algorithm efficiency, Approximate Functional Dependency, Pattern redundancy

Entropic measures such as conditional entropy or mutual information have been used numerous times in pattern mining, for instance to characterize valuable itemsets or approximate functional dependencies. Strangely enough the fundamental problem of designing efficient algorithms to compute entropy of subsets of features (or mutual information of feature subsets relatively to some target feature) has received little attention compared to the analog problem of computing frequency of itemsets. The present article proposes to fill this gap: it introduces a fast and scalable method that computes entropy and mutual information for a large number of feature subsets by adopting the divide and conquer strategy used by FP-growth -one of the most efficient frequent itemset mining algorithm. In order to illustrate its practical interest, the algorithm is then used to solve the recently introduced problem of mining reliable approximate functional dependencies. It finally provides empirical evidences that in the context of non-redundant pattern extraction, the proposed method outperforms existing algorithms for both speed and scalability.

Introduction

Entropic measures such as conditional entropy or mutual information have been used numerous times in pattern mining, for instance to characterize valuable itemsets [START_REF] Knobbe | Maximally informative k-itemsets and their efficient discovery[END_REF][START_REF] Heikinheimo | Finding low-entropy sets and trees from binary data[END_REF][START_REF] Heikinheimo | Low-Entropy Set Selection[END_REF] or approximate functional dependencies [START_REF] Dalkilic | Information Dependencies[END_REF][START_REF] Mampaey | Mining Non-redundant Information-Theoretic Dependencies between Itemsets[END_REF][START_REF] Mandros | Discovering Reliable Approximate Functional Dependencies[END_REF]. In such setting, one considers datasets where data are described by nominal features, i.e. features with a finite number of possible values. These data are interpreted as IID samples of some distribution for which the set F of features are seen as categorical random variables. For every considered subset X ⊆ F of features, the entropy H(X ) can be approximated by an empirical estimation Ĥ(X ) =t σ D (t) log 2 (σ D (t)) where frequencies σ D (t) are computed for all value combinations t (latter called tuples) of X observed in the dataset. A similar expression allows to empirically estimate mutual information I(X ; Y) = H(X ) + H(Y) -H(X ∪ Y) between X and a target feature subset Y, usually restricted to a single target feature.

Entropy H(X ) measures the amount of uncertainty when guessing samples of X , or equivalently, the quantity of information conveyed by it. Similarly mutual information I(X ; Y) is the amount of information shared between feature subsets X and Y. Both quantities have interesting properties. In particular X → H(X ) and X → I(X ; Y) are non negative monotonic functions in lattice (2 F , ⊆) of feature subsets. This property builds up a formal analogy with the anti-monotonic property of itemset frequency so that some frequent itemset mining techniques such as the levelwise search used by Apriori [START_REF] Agrawal | Fast Algorithms for Mining Association Rules in Large Databases[END_REF] have been transposed for the computation of entropic measures (see for instance [START_REF] Mampaey | Mining Non-redundant Information-Theoretic Dependencies between Itemsets[END_REF]). Despite this analogy the problem of designing fast and scalable algorithms to compute entropy of feature subsets has received little attention compared to the problem of computing frequency of itemsets, for which many algorithms have been proposed [START_REF] Bayardo | Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations[END_REF]. The present article addresses this problem as it introduces a new algorithm to compute entropy and mutual information for a large number of feature subsets, adopting the same divide and conquer strategy used by FP-growth [START_REF] Han | Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach[END_REF] -one of the most efficient frequent itemset mining algorithm [START_REF] Bayardo | Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations[END_REF].

In order to illustrate its practical interest, the algorithm is then used to solve specifically the recently introduced problem of mining reliable approximate functional dependencies [START_REF] Mandros | Discovering Reliable Approximate Functional Dependencies[END_REF]. Given a target feature Y , the problem consists in finding the top-k feature sets X 1≤i≤k which have the k highest reliable fractions of information relatively to Y . This score denoted F0 (X ; Y ) is a robust estimation of the normalized mutual information between X and Y that is unbiased and equal to 0 in case of independence between X and Y . This prevents from misinterpreting strong observed dependencies between X and Y that are not statistically representative because they are based on a too small number of data. In the same article, an algorithm is proposed to mine exactly or approximatively the top-k reliable approximate functional dependencies (RAFD) using a parallelized beam search strategy coupled to a branch and bound pruning optimization.

While authors of [START_REF] Mandros | Discovering Reliable Approximate Functional Dependencies[END_REF] focus on small values for k (mainly k = 1), we are interested by much larger values, typically k = 10 4 . This interest seems counterintuitive as the only presumable effect of increasing k is to produce more uninteresting patterns with lower scores. In reality, top-k patterns provide highly redundant pieces of information as similar patterns are likely to have similar scores. Increasing k provides a substantial list of top-k patterns from which can be extracted a reduced set of still highly scored but non redundant patterns called Locally Optimal Patterns (LOP) [START_REF] Pennerath | Fast Extraction of Locally Optimal Patterns Based on Consistent Pattern Function Variations[END_REF][START_REF] Pennerath | The Model of Most Informative Patterns and Its Application to Knowledge Extraction from Graph Databases[END_REF]: Given a pattern scoring function and given a neighbourhood function that maps every pattern to a set of neighbouring patterns, a pattern P is locally optimal if its score is maximal within P 's neighbourhood. The neighbourhood generally used is a δ-metric neighbourhood: two sets of features X 1 and X 2 are neighbours if their distance d(X , X ) defined as the cardinalily |X ∆X | of their symmetric difference is not greater than δ. Once top-k patterns have been mined, LOPs can easily be extracted by checking for every top-k pattern if some better ranked pattern is one of its neighbour (however this naive algorithm with a complexity in Θ(k 2 ) only works for relatively small values of k. For more elaborate algorithm, see [START_REF] Pennerath | Fast Extraction of Locally Optimal Patterns Based on Consistent Pattern Function Variations[END_REF]).

For sake of illustration, the amount of redundancy of a top-k pattern X can be assessed by the minimal distance δ min (X ) between X and any better scored pattern: the higher the distance, the more original the pattern. The first columns of Tab. 1 provide the histogram of δ min of top-2 to top-10000 patterns, computed on some datasets used in the evaluation section. For almost every dataset, between 97 % to 100 % of top-k patterns differ only with one single feature from a better scored pattern. On the other side, the last four columns of Tab. 1 provide the rank distribution of LOPs (for δ = 1) in the sorted list of top-k patterns. One notices that a significant part of LOPs have large ranks. It is thus essential to be able to mine top-k patterns with large values for k. Main contributions of this paper are:

1. An algorithm to compute entropy and mutual information of feature subsets, resulting from a non straightforward adaptation of the frequent itemset mining algorithm FP-growth [START_REF] Han | Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach[END_REF]. 2. An adaptation of the previous algorithm to address the problem of discovering the top-k Reliable Approximate Functional Dependencies [START_REF] Mandros | Discovering Reliable Approximate Functional Dependencies[END_REF]. The algorithm mines large numbers of patterns with low memory footprint so that it becomes possible to extract "hard-to-reach" locally optimal patterns. 3. Empirical evidences that for both problems, proposed algorithms outperform existing methods for both speed and scalability.

The rest of the paper is structured as follows: section 2 considers the general problem of fast and scalable computation of entropic measures on sets of features and introduces the algorithm HFP-growth. Section 3 introduces algorithm IFPgrowth to compute mutual information relatively to some target feature and applies it to the discovery of Reliable Approximate Functional Dependencies. Section 4 presents comparative tests performed to evaluate speed and scalability of HFP-growth and IFP-growth, before section 5 concludes.

2 An Algorithm to Compute Entropy of Feature Subsets

Definitions and Problem Statement

Let's first define properly the required notions of entropy and data partitions. Given a dataset D of n data described by a set F of nominal features, data are interpreted as IID samples of some distribution where every feature X ∈ F is seen as a categorical random variable defined over some domain denoted D X . Given a subset X = {X 1 , . . . , X k } of features listed in some arbitrary order, its joint distribution P X is defined over the cartesian product

T (X ) = D X1 × • • • × D X k containing all k-tuples (x 1 , . . . , x k ) for all x 1 ∈ D X1 , . . . , x k ∈ D X k .
Assuming the undefined form 0 × log 2 (0) is equal to zero, the entropy H(X ) of this joint distribution is defined as:

(1) H(X )

def = E log 2 1 P X = - t∈T (X ) P X (t) log 2 (P X (t))
The empirical entropy Ĥ(X ) estimates this entropy from the available samples, replacing probability P X (t) of tuple t with its relative frequency σ D (t) in D.

Entropy is a monotonic function: given two feature subsets X 1 and X 2 , X 1 ⊆ X 2 implies Ĥ(X 1 ) ≤ Ĥ(X 2 ). The entropy is minimal and equal to zero for the empty set ; it is maximal for the whole set F of features. In order to formalize the problem of computing efficiently the entropy of a large number of feature subsets, one considers the analog problem of computing frequency of frequent patterns.

To this end, one defines the relative entropy ĥ(X ) as the ratio of Ĥ(X ) over the maximal possible entropy Ĥ(F) of all features so that its values are always between 0 and 1. One then says a subset X of features is definite relatively to some threshold h max ∈ [0, 1] if ĥ(X ) ≤ h max (Definite subsets of binary features are also called low-entropy sets in [START_REF] Heikinheimo | Low-Entropy Set Selection[END_REF]). The considered problem is then the following:

Problem 1. Given a dataset D of nominal features and a threshold h max ∈ [0, 1], the problem of mining definite feature subsets consists in computing the empirical entropy of every definite subset of features relatively to h max and D.

While this problem can naively be solved by implementing an APriori like algorithm [START_REF] Agrawal | Fast Algorithms for Mining Association Rules in Large Databases[END_REF] based on formula 1, this method is highly unefficient, not only because the APriori approach is not the best strategy but also because expression 1 requires for every feature subset X to compute frequencies of all possible tuples whose number increases exponentially with the size of X . In order to provide a more efficient algorithm, empirical entropy should be defined as a function of data partitions. A data partition is any partition of the dataset D. Any subset X of features can be mapped to a data partition. For this purpose, let's say two data d 1 and d 2 are equivalent relatively to X if for every feature X of X , their respective values X(d 1 ) and X(d 2 ) are equal. The set of equivalence classes defines the said data partition denoted P (X ) of X . The empirical entropy Ĥ(X ) can thus be rewritten as the entropy H (P (X )) of its data partition defined as:

(2) H (P (X ))

def = P ∈P(X ) |P | |D| log 2 |D| |P | = log 2 (n) - P ∈P(X ) |P | log 2 (|P |) n
The set of data partitions builds a lattice with intersection and union operators that necessarily induces an ordering relation called refinement relation: a partition P 1 is a refinement of (or is included in) a partition P 2 if every part of P 1 is included in any part of P 2 . The intersection P 1 ∩ P 2 is the most general refinement of P 1 and P 2 :

(3)

P 1 ∩ P 2 = { P 1 ∩ P 2 / P 1 ∈ P 1 , P 2 ∈ P 2 , P 1 ∩ P 2 = ∅}
It is easy to prove by double inclusion that the data partition of a set X of features is the intersection of data partitions of all features of X :

(4)

P (X ) = X∈X P ({X})
This latter property is essential to design an efficient mining algorithm. Indeed let's assume there exists some encoding of data partitions that enables an efficient procedure to compute the intersection of two data partitions and its entropy.

Under this hypothesis, it gets possible to enumerate efficiently in a depth first search manner the definite feature subsets, by intersecting the data partition P (X ) of the current pattern X with the data partition P ({Y }) of the next feature Y / ∈ X to add and then by pruning the current branch as soon as the entropy of resulting partition P (X ∪ {Y }) is larger than H limit = h max × Ĥ(F). The next section explains the algorithm in details.

Algorithm HFP-growth

The presented algorithm is called HFP-growth since it adopts FP-growth's data structure called FP-tree along with its divide and conquer strategy [START_REF] Han | Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach[END_REF]. The symbol of entropy "H" emphasizes the fact HFP-growth computes entropy of definite features sets instead of frequency of frequent itemsets. The next paragraphs develop the three main components of HFP-growth: first, the HFP-tree data structure that is an adaptation of FP-trees, then the algorithmic primitives to process the HFP-tree which are the most different part compared to FP-growth, finally the global algorithm with its divide and conquer approach.

HFP-tree FP-growth is a frequent itemset mining algorithm that stores the whole dataset in memory thanks to a compact data structure called FP-tree. Many variants of FP-tree exist. Only the simplest most essential form is presented here: An FP-tree is mainly a lexicographic tree, also called trie, that encodes a dataset viewed as a collection of itemsets. In order for the trie to have the smallest memory footprint and thus the smallest number of nodes, the

F1 F2 F3 a c f a c g a d f a e f b c f b c g b d f b e f Table 2. Dataset (8) f (6) a (4) b (4) c (4) d (2) e (2) g (2) (6) (3) (1) (3) (1)
(1)

(1) (1) (1)
(1)

(1)

(1)

Levels Nodes

Fig. 1. Equivalent FP-tree unfrequent items are removed and the remaining frequent items are sorted in decreasing order of frequency. The FP-tree represented on Fig. 1 is built from dataset shown on Table 2. An FP-tree also provides for every item i a single linked list enumerating nodes representing item i in the lexicographic tree, traversing the trie from left to right. These lists are called levels hereafter. Levels are represented with dashed lines on Fig. 1. A node n represents the itemset containing items of levels intersecting the branch from the root node up to n. For instance rightmost node of g's level represents itemset bcg. Every node essentially stores pointers to its parent node and to its right sibling in its level, along with a counter set to the number of data containing node's itemset. HFP-tree is (8)

F 3 (H = 0.81) F 1 (H = 1) F 2 (H = 1.5) f (6) g (2) (6) (2) a (4) b (4) (3) (1)
(3)

(1)

(1) (1) (1)
(1)

(1)

Groups Levels Nodes Fig. 2. An HFP-tree

an FP-tree with some differences as shown on Fig. 2:

-An HFP-tree has additional components called groups of levels. Every group corresponds to some feature X. X's group is the entry point for levels, one for each possible value of X. Levels attached to X's group thus represent the parts of P ({X}). -A group also stores entropy Ĥ({X}) of X computed at startup when reading the dataset. Features whose entropy Ĥ({X}) is greater than H limit are not considered as they cannot be part of a definite feature set. This allows to sort groups in increasing order of entropy so that nodes representing the most definite features are close to the root node whereas leaf nodes at the bottom of the tree represent the most fluctuating features: this trick reduces the number of nodes, while remaining compatible with the intersection procedure explained later. In particular it does not interlace levels of different groups as standard FP-tree would do (like f and g levels of group F 3 on Fig. 1). -A node stores in addition to fields already mentioned for FP-tree, two additional node pointers called master and heir that are essential for processing the tree as explained in the next subsection. -Another difference compared to FP-growth is that only one HFP-tree is built to represent the input dataset. This characteristic is very convenient as HFP-growth does not dynamically allocate memory but at startup. If HFPgrowth succeeds in building its tree (and in practice it always does on current datasets less than few gigabytes), it will eventually complete without running out of memory after potentially several hours of processing. In comparison FP-growth clones many FP-trees during its run. However this advantage has to be mitigated as some later FP-growth implementations have managed to avoid FP-tree cloning.

Processing HFP-tree The interest of HFP-tree is to enable a fast computation of data partitions when feature subsets are enumerated in a depth search order consistent with the way features are indexed. To explain why, let's describe in a first stage how a data partition P (X ) is encoded in the HFP-tree for some given subset X of features without explaining how this encoding can be built. In the followings, index i of feature X i refers to the feature of the i th group: feature X 1 matches the first group, i.e the closest of the tree root, feature X 2 matches the 2 nd closest group and so on. Let's assume

X = {X i1 , . . . , X i k } with i 1 < • • • < i k . Individual nodes in X i k 's levels represent parts of P ∪ i k i=1 {X i } = ∩ i k i=1 P ({X i }). Since P ∪ i k i=1 {X i } is a refinement of P (X )
, for any given part P of P (X ), there are several nodes of X i k 's group that are part of P , or put another way, data members of P are covered by different nodes of X i k 's group. These nodes representing P might spread among several levels of the i k th group but they can be identified as those sharing a same reference to a representative node called master node. This master node can be any node of any previous or current group (i.e whose index is not greater than i k ). The only requirement is that two nodes belong to the same part if and only if their master nodes are the same. The use of master nodes to implicitely represent parts of partitions avoids dynamic memory allocation of objects to explicitely represent these parts. This implementation technique substantially improves speed. At startup, the only available partition encoding is represented by the root node, which is a special node as it is the only one not to be a member of any level of any group. The root node is its own master node. It represents the zero entropy partition P (∅) = {D} of the empty set of features, made of a single part containing the whole dataset.

Now the remaining issue is to define the recursive generation of partition encodings: given a current pattern X whose partition is encoded on nodes of the i k th group, how can be generated partition encoding for any child pattern X ∪ {X i k+1 } of X ? Put another way, let's consider some new feature X j with j > i k and let's assume nodes of the previous (j -1) th group encode partition of X , then the j th group must generate two different exploration branches:

-Either one adds feature X j to current pattern X . In this case, one has to encode on nodes of the j th group, partition P (X ∪ {X j }) = P (X )∩P ({X j }) using 1) the available encoding of partition P (X ) by nodes of the (j -1) th group and 2) the partition P ({X j }) whose parts are levels of the j th group. This is called the intersect operation applied to the j th group. -Or feature X j is not added to X . In this case, one simply has to forward the available encoding of P (X ) from nodes of the (j -1) th group to nodes of the current j th group. This is called the skip operation applied to the j th group.

The skip operation can easily be parallelized as it simply consists for every node n of every level of the j th group to declare its master node to be the master node of its parent node. The intersect operation is more subtle as every part of the j -1 th group might be intersected by different levels of the j th group. For every level L of the j th group, one has to gather nodes of L whose parents are member of the same part of P (X ), say otherwise, whose parents have the same master node. These subsets define new parts of P (X ∪ {X j }) as illustrated on Fig. 3. More precisely, every time the parent of a node n of L has a master m not

F 1 F 2 a b (3) (1) (3) (1)
(1)

(1) c master heir Fig. 3. Running intersect on c's level after skipping F3 and intersecting F1 processed yet, a new part P of P (X ∪ {X j }) is discovered. n is then designated as the master of P and its reference is saved in master m as its heir node. When other nodes are found such that the master m of their parents is the same as the one for n, they receive the heir of m as their master. After processing nodes of a level, all discovered parts are complete so that the sum appearing in expression 2 can be updated by their cardinalities. After processing all levels of the group j, its nodes completely encode partition P (X ∪ {X j }) and since the sum of expression 2 is completed, intersect can return entropy Ĥ(X ∪ {X j }).

Algorithm Once the HFP-tree has been built, HFP-growth uses a divide and conquer strategy based on the two previous operations skip and intersect. This strategy is similar with the one of FP-growth but while skip and intersect require a top down recursion (i.e. from the top of the tree to the bottom), FPgrowth's algorithm requires to process levels in a bottom up order, starting from the deepest levels in the FP-tree. Let m be the number of groups in the HFPtree, i.e. the number of features of F after removing feature X with entropy less than H limit . The algorithm is based on a recursive mine function as shown by pseudocode 1. For every feature index i from 1 to m -1, it recursively calls mine Inputs : A dataset D and a threshold hmax ∈ [0, 1] Output: List of definite feature sets X with their entropy Ĥ (X ) HFP-tree T , H limit ← build-HFP-tree(D, hmax) ; output(∅, 0) ; mine(∅, 1) function mine(X , j) is if j ≤ number m of groups of T then H ← intersect(T , j) ; if H ≤ H limit then output(X ∪ {Xj}, H) ; mine(X ∪ {Xj}, j + 1) end skip(T , j) ; mine(X , j + 1) end end Algorithm 1: The HFP-growth algorithm on the next i + 1 th feature twice: first after applying the procedure intersect on the i th group in the case the returned entropy is not greater than H limit , second after appling skip to the i th group systematically.

An Algorithm to Compute Mutual Information of Feature Subsets

In this section one shows how HFP-growth can be adapted to compute efficiently mutual information of feature subsets with some target feature, along with an unbiased variant of it introduced in [START_REF] Mandros | Discovering Reliable Approximate Functional Dependencies[END_REF]. Because the main subject of this paper is the efficient computation of entropic measures, one could limit the study to mutual information since computing the unbiased variant does not fundamentally change the algorithm. However this provides at the same time a sounder statistical problem to solve and an existing algorithm to compare with. The resulting algorithm is called IFP-growth, "I" standing for information.

Problem Statement

Mutual information I(X ; Y) = H(X ) + H(Y) -H(X ∪ Y) estimates the amount of information shared by two feature subsets X and Y. It is equal to zero in case X and Y are independent. Mutual information is particularly interesting in supervised problems where Y is restricted to a single target feature Y . In such problems, one searches to predict Y from highly dependent feature subsets X , i.e. with a large mutual information I(X ; {Y }). Mutual information can be estimated empirically from data partitions according to:

(5) Î(X ; Y) = Ĥ(P (Y)) + Ĥ(P (X )) -Ĥ(P (X ) ∩ P (Y))

Because H(Y) is an upper bound for I(X ; Y), one often uses a normalized mutual information F (X ; Y) = I(X ;Y) H(Y) within the range [0, 1] called fraction of information ratio in [START_REF] Dalkilic | Information Dependencies[END_REF][START_REF] Mandros | Discovering Reliable Approximate Functional Dependencies[END_REF]. As stated in the introduction, mutual information X → Î(X , Y) is a non decreasing function of X . Obviously the more features in X , the more predictable Y from X . However one should not forget that a dataset D is a limited sampling of the real joint distribution of X and Y. For large feature sets X , data partition of P (X ∪ Y) is the intersection ∩ X∈X ∪Y P ({X}) of many data partitions. Therefore parts of P (X ∪ Y) get statistically very small when the size of X increases. Within these small parts, strong but spurious dependencies appear between X and Y even when X and Y are drawn from independent distributions. New entropic measures have since been proposed in [START_REF] Vinh | Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance[END_REF][START_REF] Romano | Standardized Mutual Information for Clustering Comparisons: One Step Further in Adjustment for Chance[END_REF][START_REF] Romano | A Framework to Adjust Dependency Measure Estimates for Chance[END_REF][START_REF] Mandros | Discovering Reliable Approximate Functional Dependencies[END_REF]. These measures are similar in spirit with mutual information but robust to the previous "just by chance" artefact. One of these mesures considered in [START_REF] Mandros | Discovering Reliable Approximate Functional Dependencies[END_REF] is the reliable fraction of information F0 (X ; Y) that is unbiased, i.e whose expected value is 0 when X and Y are independent. More precisely F0 (X ; Y) = F (X ; Y) -m0(X ,Y)

Ĥ(Y)
where m0 (X , Y) is the expected value of Î(X ; Y) under hypothesis of independence between X and Y. This bias is computed using a permutation model defined over contingency tables of X and Y respectively. Since the elements in these tables are nothing else than the cardinalities of parts in P (X ) and P (Y), m0 (X , Y) can be rewritten as m0 (P (X ) , P (Y)), i.e as a function depending only on P (X ) and P (Y). The exact expression of m0 (P (X ) , P (Y)) is given by a sum of expected values for hypergeometric distributions. The detailed equation and derivation details are provided in [START_REF] Mandros | Discovering Reliable Approximate Functional Dependencies[END_REF] with reference to [START_REF] Vinh | Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance[END_REF][START_REF] Romano | Standardized Mutual Information for Clustering Comparisons: One Step Further in Adjustment for Chance[END_REF]. The expression of F0 (X ; Y) to compute is finally: [START_REF] Heikinheimo | Low-Entropy Set Selection[END_REF] F0 (X ; Y) = 1 + Ĥ(P (X )) -Ĥ(P (X ) ∩ P (Y)) -m0 (P (X ) , P (Y))

Ĥ(P (Y))

It is worth noting X → F0 (X ; Y) is not a monotonic function as mutual information is. It has the expected nice property of penalizing with low scores not only short non informative sets of features X but also long informative but not statistically representative patterns. Finding the top-k feature sets X with highest score F0 (X ; {Y }) relatively to a target feature Y is thus a sound and non trivial optimization problem addressed in [START_REF] Mandros | Discovering Reliable Approximate Functional Dependencies[END_REF]: the resulting associations X → Y are called the top-k reliable approximate functional dependencies (RAFD). A mining algorithm is also proposed in [START_REF] Mandros | Discovering Reliable Approximate Functional Dependencies[END_REF] whose implementation is called dora. This algorithm finds these dependencies using a beam search strategy coupled to a branch and bound pruning: it backtracks the current branch as soon as the upper bound 1 -m0 (X ; {Y })/ Ĥ({Y }) of scores accessible from the current pattern X is not greater than score F0 (X k ; {Y }) of the worst top-k pattern X k found so far. In order to process difficult datasets, the algorithm can also solve a relaxed version of this problem: it consists in replacing the previous pruning condition by predicate α × (1 -m0 (X ; {Y })/ Ĥ({Y })) ≤ F0 (X k ; {Y }) for some parameter α ∈]0, 1], a value α = 1 corresponding to the exact resolution. This approximation amounts to find k feature subsets ( Xi ) 1≤i≤k so that the lowest score F0 ( Xk ; {Y }) of these patterns is not lower than α × F0 (X k ; {Y }) where X k is the pattern with the lowest score among the real top-k patterns (X i ) 1≤i≤k . In summary, mining reliable approximate functional dependencies is defined by a dataset D, a target feature Y , a number k and an α coefficient. A new algorithm to address this problem is proposed in the next section.

Algorithm IFP-growth

Two preliminary remarks can be done about equation 6: first P (Y) and a fortiori Ĥ(P (Y)) are constants independent of X so that they can be computed once forever at startup. Second F0 (X ; Y) could be computed directly with two parallel HFP-trees: one whose groups encode P ({X}) for every feature X ∈ F \ {Y }, the second whose groups encode P ({X} ∩ P ({Y })). However this approach is memory-costly while it is possible to get a solution with a unique HFP-tree. The resulting algorithm IFP-growth is summarized by pseudocode 2.

A first trick of IFP-growth is to put the group of target feature Y at the bottom of HFP-tree, independently of its entropy. This last group is processed differently than the others. Another trick is to switch the order HFP-growth calls intersect and skip: IFP-growth first develops the skip's branch before intersect's one. When intersect is applied to i k th group in order to generate encoding of P ({X i1 , . . . , X i k }), combination of these two changes allow:

-First to save in global variables the entropy Ĥ(X ) (that intersect just returned) and the bias m0 (X ; {Y }) that can be computed from constant P (Y) and from P (X ) (whose encoding has also been computed by intersect). -Then to call recursively the skip operation on the successive groups up to reaching the last group of Y without modifying values of the two global variables. Calling intersect then returns Ĥ(X ∪ {Y }). At this points all terms of equation 6 are available to compute F0 (X k ; {Y }) and see if this score is sufficient for it to be inserted in the priority queue Q storing the top-k patterns. As shown by pseudocode 2, the branch and bound pruning strategy with coefficient α can seamlessly be integrated in IFP-growth. However IFP-growth pruning is assumed to be less efficent than dora's one since dora uses a beam search strategy converging quickly to good top-k pattern candidates while HFPtree dictates more rigidly the order in which subsets must be enumerated.

Empirical Evaluation

For sake of comparison, datasets considered in [START_REF] Mandros | Discovering Reliable Approximate Functional Dependencies[END_REF] are reused (see the KEEL data repository at http://www.keel.es). However in order to limit their number, only the most challenging datasets given on Table 3 are considered, defined as those whose processing by either IFP-growth or dora requires more than 10 seconds for k = 1. In order to be fair with dora whose beam search strategy is compatible with an intensive use of multithreading, tests are run on an Intel Xeon Silver 4414 biprocessor with a total of 20 hyper-threaded cores. The memory footprint of every running algorithm is monitored (internal Java Virtual Machine's heap size for dora and processus heap size for other algorithms) and limited to 45 GB. Source codes of HFP-growth, IFP-growth and HApriori can be downloaded from https://github.com/P-Fred/HFP-Growth whereas dora is available from http://eda.mmci.uni-saarland.de/prj/dora. Evaluation of HFP-growth Since HFP-growth cannot be straightforwardly compared with an existing algorithm, one studies to what extent the well known performance gap between FP-growth and the baseline algorithm APriori [START_REF] Bayardo | Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations[END_REF] is reproduced between HFP-growth and the APriori counterpart, specially implemented for this purpose. This latter algorithm, hereafter called H-APriori, uses the same levelwise pruning method as APriori to remove candidate subsets having at least one predecessor that is not definite. It then computes in one pass over the dataset the entropies of all remaining candidates using formula 1. HFPgrowth's processing times (resp. memory footprints) as functions of h max are given on Fig. 4 (resp. Fig. 5). The time (resp. memory) gain factor defined as the ratio of H-APriori's processing time (resp. memory footprint) over HFPgrowth's one is provided on Fig. 6 (resp. Fig. 7). HFP-growth appears 1 to 3 orders of magnitude faster than H-APriori, with a speedup factor increasing with threshold h max . Memory gain is even bigger: HFP-growth has a low constant memory footprint of few megabytes (values on Fig. 5 appear to be rounded by the OS's heap allocation mechanism) whereas H-APriori shortly requires many gigabytes of memory to store candidate patterns. While HFP-growth can run as long as necessary, H-APriori often runs out of memory before completing.

Evaluation of IFP-growth In order to limit the number of tests to compare IFP-growth and dora, one only considers the exact problem of discovering RAFD, i.e for α = 1. However similar conclusions can be drawn for values of α less than one. Table 3 summarizes processing times and memory footprints of both algorithms for the selected datasets and for increasing values of k from 1 to 10 6 . A memory footprint of "> 45" means the algorithm prematurely stopped as it ran out of memory. A processing time of "> 3h." means the algorithm was interrupted after a time limit of 3 hours. Results are similar with the ones ob- tained for HFP-growth: For all datasets and all values of k, IFP-growth appears always faster than dora. The gap between processing time tends to increase with k. While dora cannot complete 15 over the 16 datasets for k = 10 6 as it requires more than 45 GB, IFP-growth never runs out of memory as it requires at least 10 3 times less memory than dora, with a memory footprint always much less than 1GB, even for large values of k.

Processing time (s.) Memory footprint (GB) Dataset Algo. k = k = k = k = k = k = k = k = (n, m, c) 1

Conclusion

In this paper, an efficient algorithm computes entropy of definite feature subsets likewise efficient algorithms exist to compute frequency of frequent itemsets. This algorithm proves to be much faster and scalable than its counterpart based on a levelwise approach. This algorithm is extended to compute mutual information and reliable fraction of information relatively to some target feature. Again, when applied to the discovery of the top-k reliable approximate functional dependencies, this algorithm shows an important gain of time and space efficiency compared to the existing algorithm. While these algorithms have been instanciated on two specific problems, they should be considered as generic algorithmic building blocks enabling to solve various data mining problems relying on entropic measures such as entropy or mutual information. These algorithms can also be easily adapted for computing any other non entropic measures whose expression depends mainly on data partitions. This is the case of the first scores proposed in the context of approximate functional dependencies. The level of performance of these algorithms also enable a more systematic search of sets of non redundant informative subsets of features. Another promising application is the extraction of Bayesian networks from data as these models can be seen as solutions of entropy-based optimization problems.

Ackowledgements This work has been partially supported by the European Interreg Grande Région project "GRONE".

F kth 0 ← 0 ;Algorithm 2 :

 002 Inputs : A dataset D, target feature Y , number k, coef. α ∈ [0, 1] Output: List of top-k feature sets (Xi) 1≤i≤k with their score F0 (Xi) Q ← build-min-priority-queue() ; HFP-tree T , HY ← build-IFP-tree(D, Y ) ; mine(∅, 1) ; Output content of Q function mine (X , j) is if j < number m of groups of T then skip(T , j) ; mine(X , j + 1) ;HX ← intersect(T , j) m0 ← compute-bias(T , j) ; if 1 -m0/HY > F kth 0 /α then mine(X ∪ {Xj}, j + 1) end else HXY ← intersect(T , j) ; F0 ← 1 + (HX -HXY -m0)/HY ; Q.insert((X , F0)) ; if Q.size > k then Q.pop-min() ; F kth 0 ← min(Q).F0 end end endThe IFP-growth algorithm

Fig. 7 .

 7 Fig. 7. Memory gain factors

Table 1 .

 1 Histograms

			Distance δmin	Rank of LOP
							11-101-1001-
	Dataset	1	2	3	4 > 1 1-10 100 1000 10000
	german	9968 29	2	32	4	8	13	7
	lymphography 9964 33	1	1 36	4	5	15	12
	vehicle	9943 54	1	1 57	6	20	17	14
	sonar	9753 233	5	7 247	7	27	77	136
	penbased	9719 279	0	1 281	10	76 154	41
	segment	9961 38	0	0 39	5	5	22	7
	specftheart	9902 95	0	1 98	3	8	36	51
	twonorm	5157 4840	2	0 4843	10	90 900 3843
	wdbc	9865 130	2	1 135	9	19	41	66

of δmin and LOPs' rank among the top-10000 patterns.

Table 3 .

 3 Comparison of processing times and memory footprints of IFP-growth (IFPG) and dora for various datasets and values for k. Datasets are sorted from the easiest to the most difficult (according to IFPG's processing time for k = 10 6 ). Tuples under dataset names provide the main dataset characteristics: for a tuple (n, m, c), n is the number of data, m is the number of features and c is the number of classes for the target feature.

				10 2 10 4 10 6	1	10 2 10 4 10 6
	german	IFPG	21	22	23	22 0.005 0.006 0.007 0.010
	(1000,20,2)	dora	110 110 130 150	14	15	16	18
	lymphography IFPG	46	50	73 110 0.005 0.005 0.010 0.036
	(148,18,4)	dora	69	80 120 410	14	16	17	27
	vehicle	IFPG	130 140 160 160 0.006 0.007 0.008 0.36
	(846,18,4)	dora	820 840 880 ???	26	26	26 > 45
	sonar	IFPG	220 260 320 470 0.005 0.005 0.007 0.12
	(208,60,2)	dora 1300 1600 2000 ???	38	40	42 > 45
	penbased	IFPG	30	38 225 500 0.023 0.023 0.024 0.030
	(10992,16,10) dora	160 260 5000 ???	15	16	43 > 45
	segment	IFPG	12	20 110 600 0.008 0.009 0.015 0.044
	(2310,19,7)	dora	43	84 390 ???	15	15	22 > 45
	spectfheart	IFPG 1800 2000 2200 2300 0.005 0.006 0.007 0.13
	(267,44,2)	dora	??? ??? ??? ??? > 45 > 45 > 45 > 45
	twonorm	IFPG	160 170 370 4600 0.019 0.019 0.020 0.10
	(7400,21,3)	dora 2800 3600 ??? ???	43	43 > 45 > 45
	wdbc	IFPG	120 300 710 6330 0.007 0.007 0.008 0.12
	(569,30,2)	dora	510 770 1800 ???	18	21	32 > 45
	ring	IFPG	970 1100 1900 6700 0.019 0.019 0.020 0.140
	(7400,20,2)	dora > 3h. ??? ??? ??? ??? > 45 > 45 > 45
	satimage	IFPG	780 1300 3700 > 3h. 0.026 0.026 0.028	???
	(6435,36,7)	dora 4500 > 3h. ??? ???	31 ??? > 45 > 45
	ionosphere	IFPG	640 2300 > 3h. > 3h. 0.010 0.010 ???	???
	(351,33,2)	dora 1900 > 3h. ??? ???	30 ??? > 45 > 45
	texture	IFPG 3000 4500 > 3h. > 3h. 0.025 0.025 ???	???
	(5500,40,11) dora > 3h. > 3h. ??? ??? ??? ??? > 45 > 45
	coil2000	IFPG > 3h. > 3h. > 3h. > 3h. ??? ??? ???	???
	(9822,85,2)	dora > 3h. > 3h. > 3h. ??? ??? ??? ??? > 45
	spambase	IFPG > 3h. > 3h. > 3h. > 3h. ??? ??? ???	???
	(4597,57,2)	dora > 3h. > 3h. > 3h. ??? ??? ??? ??? > 45
	optdigits	IFPG > 3h. > 3h. > 3h. > 3h. ??? ??? ???	???
	(5620,64,10) dora	??? ??? ??? ??? > 45 > 45 > 45 > 45
	splice	IFPG > 3h. > 3h. > 3h. > 3h. ??? ??? ???	???
	(3190,60,3)	dora	??? ??? ??? ??? > 45 > 45 > 45 > 45


Rabih Bashroush
email: r.bashroush@qub.ac.uk

Adel Noureddine
email: a.noureddine@uel.ac.uk

ICT Energy Demand: what got us here won't get us there! Rabih Bashroush (University of East London), Eoin Woods (Endava) and Adel Noureddine (University of East London)

Background

IT activity has entered a new era. In 2008, the number of things connected to the internet exceeded the number of people (Evans, 2008), while Cisco predicted that in 2011, 20 typical households would generate more traffic than the entire internet in 2008 (Evans, 2008). We are witnessing an explosive growth in data driven by more affordable storage systems and the proliferation of mobile, IoT, social media, and smart cities to name a few. Add to this the software applications being created around this data, from business analytics to apps that can monitor your cow's pregnancy through a sensor connected to its tail and send you an SMS when she will most likely calf. The vast majority of the applications being developed are cloud-based, meaning constantly increasing demand on data centres, where many of the large Tech companies are continuously expanding their capacity.

Currently, data centres consume a substantial amount of energy and are thought to produce more Greenhouse Gas emissions than the entire aviation sector. In 2013, data centres in the U.S. alone consumed an estimated 91 billion KWh of electricity, and this is expected to rise to 140 billion KWh by 2020 [START_REF] Delforge | America's Data Centers Consuming and Wasting Growing Amounts of Energy[END_REF]. It is not surprising therefore that a recent survey of data centre managers showed that power density and energy efficiency are among their top current and future concerns (Intel Corporation, 2012). This is particularly important for Colocation and Managed Service data centre providers who are based within or close to large cities where grid power availability is limited.

So, can data centres cope with this demand and continue to support the exponential growth of the big data and cloud revolution? We cannot be sure, but we can see that the challenges are widely recognised: a number of related areas are the subjects of active research, ranging from new cooling technologies to more energy efficient servers and building designs, to runtime workload consolidation and management techniques. However, the software architecture community has been slower to recognise their potential contribution and to mobilise to meet this challenge. Addressing energy efficiency at the architecture level is still far from being mainstream. Can we continue designing systems without any consideration of their energy and power efficiency and let others worry about running them in an energy efficient way? Should energy efficiency be a bolt-on system property, or a quality attribute that is addressed at the design stage?

Why aren't Software Architects helping, yet?

Software architects may not be prioritising energy efficiency for a number of reasons. Firstly, we currently have very little understanding of the impact of design decisions on energy efficiency or an understanding of how it affects other system qualities such as user experience, reliability and performance. Without this knowledge, it is difficult to perform trade-off analysis to understand the benefit or cost of improving energy efficiency. Minor changes to the system design could yield substantial benefits, such as avoiding unnecessary polling or eliminating redundant housekeeping tasks that prevent equipment from entering lower-power states. However, a lack of relevant design tools and frameworks mean that it is still difficult to achieve more sophisticated optimisations that include consideration of contextual information about the runtime environment.

Second, in order to achieve the next order of magnitude in energy efficiency, we need to think outside traditional design boundaries. This will require people from different specialisations and departments to work together. This can often be difficult to achieve, given current organisational software governance structures, with different teams sometimes having competing objectives, not to mention human dynamics and political barriers. Current technologies also provide few mechanisms to allow communication across different technology layers (that is, the application software, middleware, hardware, network, cooling, power infrastructure, etc.) which would enable cross-layer optimization.

Finally, so far, energy efficiency rarely features as an end-user requirement or concern. On one hand, there is the problem of split incentives where operators of systems (e.g. administrators data centre managers) do not pick up the energy bill (which tend to come out from the facilities budget). Accordingly, they would see very little return from any savings made from energy efficiency. On the other hand, ICT energy costs, given current energy prices, do not constitute more than 1% to 3% of a typical organisation's budget. So, when efficiency is pursued, it is easier to achieve it by addressing areas with larger budget share (e.g. payroll!). This problem is exacerbated by the lack of benchmarks, metrics and reliable data to allow realistic comparisons of different energy efficiency opportunities and their realistic returns.

What do Software Architects Think?

In an attempt to understand the practicing architect's perspective on energy efficiency, we surveyed a small number of representative architects from organisations across a number of domains. We asked them whether they had to deal with an energy efficiency related challenge in a recent project (over the past five years), and whether they felt they were equipped with the right tools to address such challenges. Additionally, we asked architects whether they believed energy efficiency would be a major architectural concern over the coming five years. The results from the survey are discussed below. So what did they say? As can be seen from Figure 2 below, while the majority of surveyed architects did not have to deal with energy efficiency concerns over the past five years (83%), most thought this would be a major concern over the next five years (67%). Yet only a quarter of them agreed or strongly that they had the right tools to address these challenges (Figure 3). The survey results confirmed our view of the challenges software architects face with respect to energy efficiency, particularly around the lack of tool support to address energy at an architectural level, and the current low priority that many stakeholders place on addressing energy concerns in solution design.

Opportunities & Future Directions

Although this appears to be a gloomy situation for energy efficiency, in fact a range of potential solutions and energy saving opportunities do exist, we just need to recognise them and learn to exploit them.

Starting from the deployment view of a system, when considering placement of workload across the data centre, we can base allocation on the cooling profile, which consumes on average about 40% of the total data centre energy, rather than just the power or performance profiles often used today.

Then when designing applications, we could move beyond today's typical SLA based system quality requirements. Most SLAs for throughput, availability and performance are rigid time-based measures that do not consider energy usage as a factor. If we moved towards specifying these requirements in more flexible ways, based on outcomes over time, this would allow many applications to include energy efficiency and pricing as part of their design. By taking into account the time of the day, the current real-time energy price and other environmental factors, some types of large applications can manage their processing in real-time to minimise their energy cost.

Another direction to consider as application designers is how we match different types of workload to different types of processing environment in order to minimise energy costs.

Today we tend to focus on ease of application construction and the performance of different application platforms. If we can make estimates of energy consumption available for different types of platforms then this is another dimension to consider. For example, vector-based hardware architectures can offer considerable energy savings for some types of data intensive applications, while running some types of mainstream hardware at lower clock speeds reduces energy consumption while having little impact on the perceived performance for many types of application.

The other trend that we feel is inevitable is the eventual energy rating of software products. Just as industrial equipment became regulated so that its energy efficiency was stated clearly, and then consumer domestic appliances, today our IT hardware is energy rated but our software is not. Given the rising tide of environmental awareness, the likely ongoing rise in energy prices and the ever increasing IT workloads, it seems very likely that software too will become energy rated.

The metric we are missing in order to rate the energy efficiency of software is a measure of the work performed by a piece of software for a certain amount of energy consumed. This isn't something we can do easily today, but it is another active research area, with researchers investigating a range of approaches. The basic idea is to identify a representative characteristic operation for a particular piece of software (perhaps sending or receiving a million messages for a message bus, or processing 1000 single item orders via a web shop) and to measure the energy consumed to process that workload. This allows us to calculate the Application Work Energy Efficiency (AWEE) as the work_performed / energy_consumed (European Commission, 2014) and allows us to compare the energy efficiency of similar applications.

In summary, there is little today that we as software architects can simply take "off the shelf" and start using to monitor and minimise the energy consumption of our software. However, only a few years ago, this could also have been said of our colleagues working in

Figure 1 .

 1 Figure 1. Breakdown of participants by sector Figure 1 above shows the breakdown of participants based on the type of organization that they worked in. Although the survey was small-scale (confidence level of 80% and error margin of 20%), it can be seen from the pie chart that the respondents were representative of the IT sector based on organisation type.

Figure 2 .

 2 Figure 2. Breakdown of Prominence of Energy Efficiency

data centre and infrastructure architecture. In contrast, today, they need to be aware of and using standards such as the EU Code of Conduct on Data Centres (European Commission JRC Insitute for Energy and Transport, 2015) and Green Grid Data Centre Maturity Model (The Green Grid, 2015). A similar process for software seems inevitable and so now is the time for us as software architects to start understanding this emerging area and making sure that our contributions and concerns are heard.


Robert J Woodward
email: rwoodwar@cse.unl.edu

Berthe Y Choueiry
email: choueiry@cse.unl.edu

Christian Bessiere
email: bessiere@lirmm.fr

A Reactive Strategy for High-Level Consistency During Search

Constraint propagation during backtrack search significantly improves the performance of solving a Constraint Satisfaction Problem. While Generalized Arc Consistency (GAC) is the most popular level of propagation, higher-level consistencies (HLC) are needed to solve difficult instances. Deciding to enforce an HLC instead of GAC remains the topic of active research. We propose a simple and effective strategy that reactively triggers an HLC by monitoring search performance: When search starts thrashing, we trigger an HLC, then conservatively revert to GAC. We detect thrashing by counting the number of backtracks at each level of the search tree and geometrically adjust the frequency of triggering an HLC based on its filtering effectiveness. We validate our approach on benchmark problems using Partition-One Arc-Consistency as an HLC. However, our strategy is generic and can be used with other higher-level consistency algorithms.

Introduction

Generalized Arc Consistency (GAC) is the go-to consistency enforced in backtrack search for solving Constraint Satisfaction Problems (CSPs). Recent work showed that difficult instances benefit from enforcing higher-level consistency (HLC) [Karakashian et al., 2010;[START_REF] Woodward | [END_REF][START_REF] Lecoutre | [END_REF][START_REF] Balafrej | [END_REF]]. An open question is to determine when GAC is sufficient and when a more aggressive (but likely more costly) consistency is warranted.

We claim that techniques for enforcing HLCs during search can be organized along orthogonal dimensions and identify three such 'axes:' where, when, and how much of an HLC to enforce, as shown in Figure 1. In summary, the 'where' axis identifies specific (or groups of) variables/constraints on which an HLC is enforced; the 'when' axis identifies at what point, during search, HLC is enforced; and the 'how much' axis indicates whether HLC is allowed to reach a fixpoint or forced to terminate earlier. The point of origins of those three axes indicates the 'strongest' application of HLC (i.e., enforce HLC uniformly over the entire future subproblem, at each variable instantiation, and until quiescence). In this paper, we present PREPEAK + as a reactive strategy that operates on the two dimensions 'when ' and 'how much.' In particular, (a) we introduce a triggering strategy, PREPEAK, that tracks search performance and triggers HLC when search starts thrashing (i.e., when), and (b) choose to enforce HLC on a fraction of the (ordered) propagation queue and within a bounded time duration (i.e., how much).

We validate PREPEAK + using as HLC the consistency property Partition-One Arc-Consistency (POAC) [START_REF] Bennaceur | Hachemi Bennaceur and Mohamed-Salah Affane. Partition-k-AC: An Efficient Filtering Technique Combining Domain Partition and Arc Consistency[END_REF][START_REF] Balafrej | [END_REF]. This choice is justified by the fact that POAC is implemented with singleton tests and only standard GAC propagators (e.g., propagators of table constraints or global constraints), which probably makes it the easiest and most immediate HLC to implement in constraint solvers. We empirically show that PREPEAK + (with POAC) outperforms GAC on all kinds of binary/non-binary and structured/unstructured CSPs. We re-iterate that PRE-PEAK + is generic and can be used in combination with any HLC. Indeed, preliminary results on other consistencies are extremely encouraging.

The paper is structured as follows. Section 2 reviews background information. Section 3 reviews and organizes related work along the three identified dimensions. Section 4 describes our triggering strategy PREPEAK and Section 5 discusses our strategy of how much HLC to enforce. Section 6 evaluates our approach and Section 7 compares our approach to other techniques. Finally, Section 8 concludes this paper.

Background

A constraint network is defined by P = (X , D, C). X is a set of variables where a variable x i ∈ X has a finite domain dom(x i ) ∈ D. A constraint c i ∈ C is given by its scope scope(c i ) and its relation rel(c i ): scope(c i ) is the sequence of variables to which

c i applies; rel(c i ) is the set of combi- nations of |scope(c i )| values satisfying c i . A tuple belonging to rel(c i ) ∩ xi∈scope(ci) dom(x i ) is called a support of c i .
A solution of P assigns, to each variable, a value from its domain such that all the constraints are satisfied. The problem of deciding the existence of a solution is called a Constraint Satisfaction Problem (CSP) and is known to be NP-complete. To this day, backtrack search remains the only sound and complete algorithm for solving CSPs [START_REF] Bitner | [END_REF]. Search operates by assigning a value to a variable and backtracks when a dead-end is encountered.

After each variable assignment, constraint solvers enforce some consistency on the unassigned variables to remove values from their domains that are inconsistent, given the constraints with the current assignment and, thus, cannot participate in a solution [START_REF] Haralick | [END_REF]Sabin and Freuder, 1994]. Such filtering prunes 'barren' subtrees from the search space and can reduce thrashing and consequently the search effort. The higher the consistency level enforced during search, the stronger the pruning and the lesser the search effort. However, higher levels of consistency may take more time/space to enforce.

The most commonly enforced consistency property is Generalized Arc Consistency (GAC) [Mackworth, 1977]. A constraint network is GAC iff, for every constraint c i , and every variable x ∈ scope(c i ), every value v ∈ dom(x) is consistent with c i (i.e., appears in some support of

c i ). Let (x i , v i ) denote a variable-value pair, (x i , v i ) ∈ P iff v i ∈ dom(x i ). GAC(P ∪ {x i ← v i })
is the constraint network after assigning x i ← v i and running GAC. Singleton Arc-Consistency (SAC) ensures that for each (x i , v i ) ∈ P, GAC(P ∪ {x i ← v i }) does not have any empty domain [START_REF] Debruyne | [END_REF]. Testing GAC(P ∪ {x i ← v i }) is called a singleton test. A higher-level consistency property that has recently shown promise is Partition-One Arc-Consistency (POAC) [START_REF] Bennaceur | Hachemi Bennaceur and Mohamed-Salah Affane. Partition-k-AC: An Efficient Filtering Technique Combining Domain Partition and Arc Consistency[END_REF]. A constraint network P = (X , D, C) is POAC iff P is SAC and for all (x i , v i ) ∈ P, for all x j ∈ X , there exists v j ∈ dom(x j ) such that (x i , v i ) ∈ GAC(P ∪ {x j ← v j }). POAC is guaranteed to enforce a higher-level consistency than SAC and SAC than GAC [START_REF] Bennaceur | Hachemi Bennaceur and Mohamed-Salah Affane. Partition-k-AC: An Efficient Filtering Technique Combining Domain Partition and Arc Consistency[END_REF]. [START_REF] Balafrej | [END_REF] introduced two algorithms for enforcing POAC, namely, POAC-1 and its adaptive version APOAC. In POAC-1, all the CSP variables are singleton tested, and the process is repeated over all the variables until a fixpoint is reached. In APOAC, the process is interrupted as soon as a given number of variables are processed, which depends on input parameters but is updated during search. Our experiments compare GAC, APOAC, PREPEAK + with POAC as an HLC.

Related Work

We organize the related work along the three axes shown in Figure 1 and combinations of these dimensions.

Where: The consistency level is chosen based on some property of the variables and/or constraints. One can exploit structural properties of the constraint network, such as the neighborhood of a variable or a constraint [START_REF] Freuder | [END_REF]Wallace, 2015;[START_REF] Woodward | [END_REF], or some configuration of constraints [Karakashian et al., 2010]. [START_REF] Freuder | [END_REF] enforce arc consistency on a subproblem within a given distance (i.e., where) from the instantiated variable. Balafrej et al. [2013] and [START_REF] Woodward | [END_REF] exploit the degree of support that constraints provide to variable-value pairs, which is a structural property.

When: The consistency selected depends on search performance. Borrett et al. [1996] switch between backtrack algorithms, level of consistency enforced, and ordering heuristics by a complex combination of domain sizes, number of variables, and backtrack levels. [START_REF] Epstein | [END_REF] consider several strengths of AC-based consistencies depending on the depth of the search tree. [START_REF] Balafrej | [END_REF] use a multiarmed bandit at each depth of search tree to select between MAC, maxRPC, or POAC.

How much: Propagation is terminated before reaching a fixpoint. Such approaches focus on the propagation queue of a consistency algorithm. They either order the propagation queue according to some heuristic [START_REF] Wallace | [END_REF] or interrupt the consistency algorithm when the pruning effect of propagation has subsided [START_REF] Balafrej | [END_REF] or the allocated time has elapsed [START_REF] Eén | Niklas Eén and Armin Biere. Effective Preprocessing in SAT Through Variable and Clause Elimination[END_REF][START_REF] Geschwender | [END_REF].

Where and when: Some authors propose heuristics to dynamically switch from GAC to a stronger property on a selection of constraints (i.e., where) based on the amount of activity of the constraints during search (i.e., when). For example, Stergiou [2008] switches between GAC and maxRPC for binary CSPs and [START_REF] Paparrizou | Anastasia Paparrizou and Kostas Stergiou. Evaluating Simple Fully Automated Heuristics for Adaptive Constraint Propagation[END_REF] between GAC and maxRPWC for nonbinary CSPs.

Where and how much: [START_REF] Paparrizou | Anastasia Paparrizou and Kostas Stergiou. On Neighborhood Singleton Consistencies[END_REF] propose a strategy for interrupting enforcing Neighborhood-SAC based on the amount of filtering it yields. For each singleton test on the considered variable, the filtering is interrupted (i.e., how much) unless the domain of any neighboring variable (i.e., where) becomes singleton.

When HLC: A Trigger-Based Strategy

We introduce our HLC-triggering strategy PREPEAK.

PREPEAK

The idea behind our reactive strategy is to monitor the 'progress' of search while maintaining some consistency property, such as GAC, in a d-way branching backtrack search. When search starts thrashing, we trigger some highlevel consistency (HLC), such as POAC, and keep enforcing it as long as it is beneficial. In order to determine that thrashing has reached a dangerous level, we propose to track the number of backtracks at each depth (or level) of the search tree. We advocate using the number of backtracks as a better indication of thrashing than the number of constraint checks (e.g., [START_REF] Epstein | [END_REF]) or the number of nodes visited because the former depends on the number of constraints that apply to a variable and the latter depends on the variable's domain size. To this end, we store the number of times each level of the search tree was backtracked to in a vector btcounts [•] indexed by the corresponding level. The size of the vector is n + 1 where n is the number of variables in the problem. When an entry in this vector reaches some threshold value θ, we set peak d , identified as the 'peak' depth of thrashing, to the search depth corresponding to that entry. When search backtracks to a shallower depth than peak d , we enforce HLC as long as HLC is effective, then we revert to enforcing GAC after resetting to 0 all the counts in btcounts [•]. We call this approach PREPEAK because (a) it is based on identifying the peak depth to which search backtracks and (b) HLC is enforced up to this depth. Our goal is to 'hit hard' the future subproblem with HLC and reduce its size before the search reaches the peak depth again.

We present PREPEAK as simple modifications of the functions UNLABEL (Algorithm 1) and LABEL (Algorithm 2) of Prosser's 'classical' backtrack search algorithm [1993]. These modifications are obtained by adding the lines highlighted in the pseudocode. Below, we discuss only the lines corresponding to our modifications. Further, we declare btcounts[•] and peak d as global variables to the search procedure. We initialize all the entries of btcounts[•] to 0 and set peak d to 0 indicating that there is no active peak.

In Line 5 of UNLABEL (Algorithm 1), we increment the value of btcounts[h] where h is the depth to which we backtrack. If btcounts[h] reaches the threshold value θ, we set peak d to h to reduce the chance of thrashing at i (Line 6). We discuss the selection of the initial value of θ in Section 4.3.

It is in the function LABEL (Algorithm 2) that we must decide whether or not to enforce HLC. At every assignment of the current variable x i , we first enforce GAC (Line 6). At Line 7, if we find that a peak was identified (peak d > 0) and the current depth is shallower than the peak's depth (i ≤ peak d ), we enforce HLC on the future subproblem recording the outcome of this call, for the given assignment, using the Boolean variables consistent and filtered (Line 8), where consistent indicates the consistency of the current path and filtered indicates whether or not HLC yielded any filtering. The Boolean variables HLCenforced and HLCfiltered indicate, for any tested assignment for the current variable, whether or not HLC was enforced (Line 9) and yielded filtering (Line 10), respectively. Note, once HLC is triggered, we Algorithm 1: UNLABEL(i,consistent) unlabels variable xi Input: i: depth of failed variable; consistent: state of current path Output: depth of current variable 1 Restore domains of current and future variables

2 h ← i -1 3 dom(x h ) ← dom(x h ) \ {ASSIGNEDVALUE(x h )} 4 consistent ← dom(x h ) = ∅ 5 btcounts[h] ← btcounts[h] + 1 6 if btcounts[h] = θ then peak d ← h 7 return h Algorithm 2: LABEL(i,consistent) instantiates variable xi Input: i: depth of current variable; consistent: state of current path Output: depth of current variable 1 consistent ← false 2 HLCenforced ← false 3 HLCfiltered ← false 4 foreach v i ∈ dom(x i ) while not consistent do 5 x i ← v i 6 consistent ← GAC(P)
11 if not consistent then dom(x i ) ← dom(x i ) \ {v i } 12 if HLCenforced then 13 if not consistent then θ ← r w • θ 14 else 15 ∀z btcounts[z] ← 0 16 peak d ← 0 17 if HLCfiltered then θ ← r f • θ 18 else θ ← r n • θ 19 if consistent then return i + 1 else return i
enforce it for all the tested values for the current variable x i .

We claim that, whenever we trigger HLC, it is timely to revise and update the triggering threshold, θ, given the recorded outcome of HLC. We distinguish three regimes:

1. Wipeout: HLC effectively depletes the domain of x i by yielding a wipeout at every instantiation. It forces search to backtrack. 2. Filtering: HLC yields some filtering, but finds a consistent assignment for x i and allows search to proceed to the next level. 3. Neither: HLC does not yield any filtering at all (beyond what GAC may have filtered). Search proceeds to the next level with a consistent instantiation for x i . We update the threshold value θ by multiplying its current value by a factor of r w (Line 13), r f (Line 17), or r n (Line 18), for each of the above regimes, respectively, as we argue below. We discuss these factors in Section 4.2.

The first regime (i.e., wipeout) 'reinforces' our belief in the usefulness of HLC and entices us to continue to enforce HLC as we backtrack by one or more levels. To this end, we do not reset the values of peak d or btcounts [•]. In the remaining two regimes, we are reserved about the usefulness of HLC and prevent it from triggering again too soon. Thus, we reset the values of both btcounts[•] and peak d (Lines 15 and 16). As a result, subsequent calls to the function LABEL do not enforce HLC until a new peak is detected.

Update Strategies for θ

The three identified regimes allow us to 'plug in' arbitrary strategies for updating θ, thus providing an opportunity to ad-just PREPEAK's reactivity to the relative cost of the consistency properties enforced. We propose to use geometric laws similar to the one used for cutoff-value update in restarting randomized search [Walsh, 1999] θ ← r • θ with different values of the common ratio r for each of the regimes.

1. Wipeout: We use r w = 1.2 -1 (Line 13). 1 2. Filtering: We use r f = 1.22 (Line 17).

3. Neither: We use r n = 1.23 (Line 18). The above strategies allow PREPEAK to adapt to the instance at hand by updating θ based on HLC's pruning effectiveness. Indeed, when it yields a domain wipeout (first regime), HLC is effectively reducing thrashing and its frequency is increased. Otherwise, the update strategies decrease HLC's triggering frequency more aggressively when HLC yields no filtering (third regime) than when it does (second regime).

Initializing the Threshold θ

Our reactive strategy enforces GAC until search starts thrashing, triggering HLC when backtracking 'reaches' the value of the threshold θ. If we choose too small an initial value for θ, HLC may trigger while GAC is still effective, which adds to the CPU cost. 2 If we choose too large a value, GAC may have run for too long in a barren subtree.

In PREPEAK, the distribution of the backtracks in the vector btcounts[•] varies depending on the problem instance, making the choice of the initial value of θ not straightforward. We investigated an alternative reactive strategy that triggers HLC based on the value of ). In other words, we identify the first peak and its depth by taking a snapshot of the backtrack profile after search executes n 2 backtracks. We tested different values, such as various powers of n, various factors of n, the sum of domain sizes, and the ratio of the CPU times for enforcing GAC and HLC computed in a pre-processing step. We empirically found that values that are quadratic in the number of variables (e.g., n 2 and sum of domain sizes) perform best, thus, we select n 2 .

How Much HLC: Monitoring Propagation

We propose two mechanisms to control the early termination of HLC, namely, the size of the propagation queue and the time bound for running HLC. First, while ordering the elements of the propagation queue of the HLC algorithm based on the activity of a variable or constraint (e.g., dom/wdeg [START_REF] Boussemart | [END_REF]), we allow only a fraction of the propagation queue to be processed. Second, we impose a bound on the duration of any call to HLC.

Let q be the number of elements in the propagation queue each time we trigger HLC. We terminate HLC as soon as either of the following two criteria is met:

1. q 2 elements of the propagation queue are processed or 2. HLC has consumed a total CPU time q 2 • TIME(GAC) where TIME(GAC) is the time spent on the last call to GAC prior to HLC (Line 6 of Algorithm 2). Our approach is inspired from [START_REF] Balafrej | [END_REF], who noticed that POAC is too costly to be used on its own. They advocated to (a) order the variables in the propagation queue by the dom/wdeg ordering heuristic and (b) terminate POAC when the amount of filtering by POAC significantly drops. They proposed an adaptive strategy APOAC, based on a "10% learning, 90% exploitation"-learning strategy, which assumes that POAC is enforced at every step during search. PREPEAK cannot accommodate such a learning process because HLC is enforced only reactively.

Other mechanisms to monitor propagation may exist. For example, we can watch propagation during a given window of the propagation queue while sliding this observation window as long as filtering is 'active.' Alternatively, we can consider a sliding window of time. We tested combinations of such criteria. While the results were positive in general, they were unstable across benchmarks. As a lesson, we conclude that a fixed amount for each mechanism (i.e., queue and time) is simpler to implement, more stable, and as effective.

Experiments

We denote PREPEAK + the combination of our when strategy (PREPEAK, Section 4) and our how-much strategy (Section 5). To validate our approach, we consider the problem of finding a single solution to a CSP using d-way branching backtrack search. We set up our experiments as follows. We choose POAC for the higher-consistency property and enforce it using the POAC-1 algorithm [START_REF] Balafrej | [END_REF], where we exclude variables with singleton domains from the singleton tests.

We use the benchmark problems available from Lecoutre's website. 3 We test all available binary and non-binary CSPs, including Boolean, patterned, random, quasi-random, academic, and real-world benchmarks. We include all benchmarks with at least one instance with a primal graph of density less than 50%. Indeed, on high density networks, the impact of an instantiation on a future variable is immediately propagated by GAC while HLC typically yields no further filtering but costs predictable data-setup overhead. This selection results in a total of 138 benchmarks (57 non-binary and 81 binary) consisting of 4,077 instances (1,716 non-binary and 2,361 binary). The selected benchmarks have a mixture of instances with densities ≥ 50% and < 50%, however, only 137 instances of the 4,077 instances included have densities ≥ 50%. We setup our reactive strategies to first compute the density of an instance. If the density is ≥ 50%, we enforce GAC. Otherwise, we execute the reactive strategy. Our results include this computation time. We use a time limit of 60 minutes per instance and 8GB of memory.

In our tables, we report the number of instances solved by a given algorithm (#solved), the number of nodes visited averaged over instances completed by all algorithms (avg. NV), and the total CPU time in seconds computed over instances completed by any of the compared algorithms ( CPU). When an algorithm does not terminate within the time allocated, we add 3,600 seconds to the CPU time and indicate with a > sign that the time reported is a lower bound. For techniques that run POAC, we report the average number of calls to POAC after enforcing GAC (#CallsPOAC). A value is in boldface when it is the best value in a given row.

We first show that PREPEAK + performs better than either of its components. Then, we compare PREPEAK + against GAC and APOAC using two different dynamic variableordering heuristics: dom/deg [START_REF] Bessière | Christian Bessière and Jean-Charles Régin. MAC and Combined Heuristics: Two Reasons to Forsake FC (and CBJ?) on Hard Problems[END_REF] and dom/wdeg [START_REF] Boussemart | [END_REF]. Finally, we introduce a visualization of the search process to provide a graphical interpretation of the good performance of our approach.

6.1 Putting Together 'When ' and 'How Much' In this experiment, we use the dom/wdeg variable-ordering heuristic. Table 1 shows the contributions of the two aspects 'when' (PREPEAK, Section 4) and 'how much' (interrupting propagation, Section 5) to the good performance of PREPEAK + . PREPEAK + solves more instances than either component taken individually, which shows the importance of combining the two orthogonal dimensions. The number of calls to POAC in PREPEAK + is mostly controlled by the triggering strategy (i.e., 'when'), which by itself is more expensive than PREPEAK + because POAC runs until a fixpoint. The right-most column enforces POAC with early termination (Section 5) at every node, yielding the smallest number of nodes visited but the largest CPU time. 'When' and 'how much' complete difference instances: only 2,131 instances are completed by both. Combining 'when' and 'how much' in PREPEAK + allows it to solve instances not solved by both.

PREPEAK + Versus GAC and APOAC

Table 2 compares the performance of GAC, APOAC, and PREPEAK + under the dom/deg ordering heuristic. 4 PRE-PEAK + solves the most instances and is the fastest algorithm. 4 Although dom/wdeg is generally more effective than dom/deg, the decisions made by dom/wdeg are considered too unstable to objectively allow comparing algorithms' performance. Researchers studying the performance of HLC during search typically use dom/deg in their experiments [START_REF] Balafrej | [END_REF][START_REF] Paparrizou | Anastasia Paparrizou and Kostas Stergiou. Strong Local Consistency Algorithms for Table Constraints[END_REF][START_REF] Paparrizou | Anastasia Paparrizou and Kostas Stergiou. On Neighborhood Singleton Consistencies[END_REF]. Predictably, in terms of average nodes visited, APOAC explores the fewest and PREPEAK + is closer to APOAC than to GAC despite the relatively few calls to POAC (686.1). We conclude that PREPEAK + triggers HLC at the right place and in the right amount, thus validating our approach.

Algorithm

Figure 2 shows the cumulative number of instances completed by GAC, APOAC, and PREPEAK + (on dom/deg) as time increases. Comparing GAC and APOAC, we see that GAC dominates APOAC on instances solved within 1,600 seconds, while APOAC dominates GAC after this point. This behavior motivates the need for HLC on difficult instances and illustrates its overhead on easier instances. By selectively triggering HLC, our strategy, PREPEAK + , dominates both GAC and APOAC.

Table 3 repeats the same experiment under dom/wdeg. The results are similar to those in Table 2: PREPEAK + outperforms GAC and APOAC in terms of both number of instances solved and CPU time. Note that it would be incorrect to conclude that the CPU time of APOAC deteriorates from Table 2 to Table 3 3).

Figure 3 shows the cumulative number of instances completed by GAC, APOAC, and PREPEAK + (on dom/wdeg) as CPU time increases. APOAC is clearly dominated by both GAC and PREPEAK + . For instances easily solved by GAC (i.e., solved in less than 300 seconds), PREPEAK + has calls to because is not thrashing. For the remaining harder instances, PREPEAK + dominates GAC. PREPEAK + remains competitive dom/wdeg, which is known to dwarf the benefits of HLC.

Table 4 provides a finer examination of the results with dom/wdeg for a range of representative benchmarks, showing the number of instances in each benchmark in parentheses.

Rows 1-3 show benchmarks where PREPEAK + significantly outperforms all others both in CPU time and the number of solved instances. For all remaining benchmarks, PRE-PEAK + solves as many instances as the best algorithm.

APOAC solves more instances than GAC in rows 4 and 5, showing that HLC is required for these benchmarks. PRE-PEAK + solves the same number of instances as APOAC, in faster CPU time, by selectively enforcing HLC. These benchmarks confirm the ability of our approach to mimic APOAC's performance when APOAC is needed.

In row 6 (QCP-15), GAC and APOAC are roughly equivalent, yet PREPEAK + outperforms both in CPU time. For rows 7 and 8, GAC solves more instances than APOAC, however, PREPEAK + 's few calls to POAC allow it to slightly improve on the CPU performance of GAC. For rows 9-11, GAC significantly outperforms APOAC both in instance completions and CPU time: HLC is too costly on these benchmarks. However, PREPEAK + is able to adapt to the situation with a CPU time similar to GAC's.

Visualizing Search Performance

For a deeper insight into the behavior of search, we visualize the search execution, using dom/wdeg, on a CSP instance as shown in Figure 4, which 'profiles' search with GAC, APOAC, and PREPEAK + . In each of the three plots, we report, on the horizontal axis, the depth of the search tree.

We plot the number of backtracks at each depth, accumulated throughout search (purple line), with the scale reported on the vertical axis to the left. We superimpose the cumulative number of calls to POAC (#Calls POAC) at each depth, with the scale reported on the vertical axis to the right. We split the number of calls to POAC into three cases: POAC yields wipeout (green line), POAC yields some filtering (blue line), and POAC yields no filtering at all (red line).

The backtrack curve (purple) shows that APOAC (middle) dramatically reduces the peak value reached by GAC (top) thanks to the large number of calls to POAC. Unfortunately, many of these calls are totally wasted (red curve) or likely of little impact (blue curve): In the middle plot, they compete with the wipeout calls (green curve). PREPEAK + (bottom) makes significantly fewer calls to POAC and those calls are mostly effective (many more calls in green than in blue or red), which establishes that HLC is wisely exploited.

Comparison to Other Techniques

We identify two general strategies similar to PREPEAK + in the sense that they are not designed for a particular HLC:

1. In SAT solving, [START_REF] Wotzlaw | [END_REF] We compare both techniques to PREPEAK + . 5 To level the playing field, we enhanced them both with our propagationmonitoring strategy (i.e., 'how-much HLC,' Section 5).

In our experiments on dom/wdeg (see Table 3), the fixed-ratio inprocessing approach solves 2,264 instances in 5 For the fixed-ratio inprocessing approach, we use POAC as HLC for 10% of the CPU time. For the MAB approach, we choose between GAC and POAC although the original paper also uses maxRPC, but it operates on only binary CSPs.

>413,634.6 seconds. It outperforms APOAC but performs worse than GAC. This strategy yields poor results because it is agnostic to 'where,' in the search space, an HLC is needed. Further, it is unable to react to the effectiveness of HLC (i.e., amount of pruning obtained by the HLC).

In our experiments on dom/wdeg (see Table 3), the MAB approach solves 2,253 instances in >529,767.9 seconds. It outperforms APOAC but performs worse than GAC. Because each MAB operates at a fixed level in search, using dom/wdeg adversarially affects the effectiveness and stability of a bandit's learning. Further, the MAB approach assesses the performance of a consistency call by the CPU cost of searching the subtree rooted at the call (regardless of which consistencies are used in the subtree). PREPEAK + largely outperforms the MAB-based strategy for both dom/deg and dom/wdeg because PREPEAK + uses the number of backtracks to assess search progress, which is a more precise measure of the HLC's effectiveness.

Conclusions

We introduce a simple, reactive, trigger-based strategy for advantageously enforcing a higher-level consistency during search and empirically validate our approach. Our experiments use POAC because it is perhaps the HLC that is the most readily portable to constraint solvers. However, preliminary results on other consistencies are extremely encouraging. The proposed visualization is an asset for in-vivo and post-mortem analysis and provides insight into the performance of search.

Figure 1 :

 1 Figure 1: Dimensions for enforcing consistency

  7 if consistent and peak d > 0 and i ≤ peak d then 8 (consistent, filtered ) ← HLC(P) 9 HLCenforced ← true 10 HLCfiltered ← HLCfiltered or filtered

n

  l=1 btcounts[l]. This study inspired the following initialization of θ for PREPEAK: we set θ to be the maximum value of btcounts[•] when n l=1 btcounts[l] = n 2 , thus, setting θ ← max n l=1 (btcounts[l]

Figure 4 :

 4 Figure 4: Search progress on pseudo-aim-200-1-6-4 using dom/wdeg: GAC (top), APOAC (middle), and PREPEAK + (bottom)

Table 1 :

 1 PREPEAK + versus 'when,' 'how much'

	Algorithm PREPEAK +	When	How Much
	#Instances: 4,077 total; 2,131 by all; 2,298 by at least one
	#solved	2,286	2,239	2,171
	CPU [sec] >356,778.1 >610,958.6	>915,738.6
	avg. NV	568,072.7	123,224.9	10,925.7
	#CallsPOAC	2,477.5	1,128.1	5,019.4

Table 2 :

 2 GAC, APOAC, and PREPEAK + on dom/deg

		GAC	APOAC	PREPEAK +
	#Instances: 4,077 total; 1,891 by all; 2,205 by at least one
	#solved	2,036	2,058	2,173
	CPU [sec] >1,044,380.1 >1,042,622.9 >455,189.2
	avg. NV	1,138,447.6	90,047.4	324,020.2
	#CallsPOAC	-	30,911.5	686.1

Table 3 :

 3 because this measurement accounts for the number GAC, APOAC, and PREPEAK + on dom/wdeg

	2,200	PrePeak+
	2,150	APOAC
		GAC
	2,100
	1,950 2,000 2,050	# Completed Instances
	1,900
	1,850
	1,800				CPU Time [sec]
	0	300	600	900	1,200 1,800 2,100 2,400 2,700 3,000 3,300 3,600
	Figure 2: Cumulative instances completed by CPU time on dom/deg
	Algorithm		GAC	APOAC	PREPEAK +
	#Instances: 4,077 total; 2,122 by all; 2,298 by at least one
	#solved			2,279	2,138	2,286
	CPU [sec] >372,433.4 >1,095,125.8 >356,778.1
	avg. NV		480,897.9	23,472.9	319,453.4
	#CallsPOAC		-	9,924.4	288.6

Table 4 :

 4 Representative benchmarks using dom/wdeg (time in [sec])

		Benchmark		GAC	APOAC PREPEAK +
	1	QCP-20 (15)	# solved CPU >5,328.7 >4,861.0 4 4	5 2,762.9
	2	nengfa (10)	# solved CPU >3,820.6 >4,235.9 4 4	5 2,321.0
	3	frb45-21 (10)	# solved CPU >17,642.0 >28,800.0 7 0	8 16,239.8
	4	k-insertion # solved (32) CPU >3,955.2 16	17 3,550.0	17 2,903.5
	5	pseudo-ii (41)	# solved CPU >18,619.8 9	14 2,481.9	14 2,088.4
	6	QCP-15 (15)	# solved CPU	15 1,310.0	15 1,248.4	15 1,213.5
	7	sgb-queen (50)	# solved CPU	14 5,712.9 >9,969.6 12	14 5,692.0
	8	super-os taillard5 (30)	# solved CPU 11,971.1 >28,924.3 9 1	9 11,969.8
	9	super-os taillard-4 (30) CPU # solved	28 7,647.2 >33,042.7 22	28 7,675.5
	10	geom (100)	# solved CPU	100 7,254.3 >28,365.6 98	100 7,372.8
	11	TSP-20 (15)	# solved CPU	15 276.5	15 1,426.9	15 298.6

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence

The value of 1.2 is a commonly used factor (e.g.,[Walsh, 1999]) and provides a 'gentle' evolution. Other values tested (e.g., 1.1, 1.4, and 1.6) yielded qualitatively similar results.

We empirically noticed that the three update rules (Section 4.2) allow us to recover from starting with smaller values by dynamically adjusting the value of θ to the instance at hand, thus providing some robustness to our approach.

www.cril.univ-artois.fr/ ∼ lecoutre/benchmarks.html Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence

Acknowledgments

This research is supported by NSF Grant No. RI-111795 and RI-1619344. Robert Woodward was supported by an NSF GRF Grant No. 1041000 and a Chateaubriand Fellowship. This work was completed utilizing the Holland Computing Center of the University of Nebraska, which receives support from the Nebraska Research Initiative. Christian Bessiere was partially supported by the ANR projects Demograph (ANR-16-CE40-0028) and Contredo (ANR-16-CE33-0024).