{'fraction_non_alphanumeric': 0.041754169240271775, 'fraction_numerical': 0.008449660284126003, 'mean_word_length': 4.286833855799373, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Recording and Minimizing Nogoods from Restarts

In this paper, nogood recording is investigated for CSP within the randomization and restart framework. Our goal is to avoid the same situations to occur from one run to the next ones. More precisely, nogoods are recorded when the current cutoff value is reached, i.e. before restarting the search algorithm. Such a set of nogoods is extracted from the last branch of the current search tree and exploited using the structure of watched literals originally proposed for SAT. We prove that the worst-case time complexity of extracting such nogoods at the end of each run is only O(n^2 d) where n is the number of variables of the constraint network and d the size of the greatest domain, whereas for any node of the search tree, the worst-case time complexity of exploiting these nogoods to enforce Generalized Arc Consistency (GAC) is O(n|B|) where |B| denotes the number of recorded nogoods. As the number of nogoods recorded before each new run is bounded by the length of the last branch, the total number of recorded nogoods is polynomial in the number of restarts.  Interestingly, we show that when the minimization of the nogoods is envisioned with respect to an inference operator φ, it is possible to directly identify some nogoods that cannot be minimized. For φ = AC (i.e. for MAC), the worst-case time complexity of extracting minimal nogoods is slightly increased to O(en2 d3 ) where e is the number of constraints of the network. Experimentation over a wide range of CSP instances using a generic state-of-the-art CSP solver demonstrates the effectiveness of this approach. Recording nogoods (and in particular, minimal nogoods) from restarts significantly improves the robustness of the solver.


Introduction
Nogood recording (or learning) has been suggested as a technique to enhance CSP (Constraint Satisfaction Problem) solving in [10]. The principle is to record a nogood whenever a conflict occurs during a backtracking search. Such nogoods can then be exploited later to prevent the exploration of useless parts of the search tree. The first experimental results obtained with learning were given in the early 90's [10,14,37].
Contrary to CSP, the recent impressive progress in SAT (Boolean Satisfiability Problem) has been achieved using nogood recording (clause learning) under a randomization and restart policy enhanced with a very efficient lazy data structure [32]. Indeed, the interest of clause learning has arisen with the availability of large instances (encoding practical applications) which contain some structures and exhibit heavy-tailed phenomenon. Learning in SAT is a typical successful technique obtained from the cross fertilization between CSP and SAT: nogood recording [10] and conflict directed backjumping [34] have been introduced for CSP and later imported into SAT solvers [2,28].
Recently, a generalization of nogoods, as well as an elegant learning method, have been proposed in [23,24] for CSP. While standard nogoods correspond to variable assignments, generalized nogoods also involve value refutations. These generalized nogoods benefit from nice features. For example, they can compactly capture large sets of standard nogoods and are proved to be more powerful than standard ones to prune the search space.
As the set of nogoods that can be recorded might be of exponential size, one needs to achieve some restrictions. For example, in SAT, learned nogoods are not minimal and are limited in number using the First Unique Implication Point (First UIP) concept. Different variants have been proposed (e.g. relevance bounded learning [2]), all of them attempt to find the best trade-off between the overhead of learning and performance improvements. Consequently, the recorded nogoods cannot lead to a complete elimination of redundancy in search trees. An original alternative [41] to combine search scattering and redundancy avoidance involves performing random jumps in the search space. It is particularly relevant when an allotted time is given.
In this paper, nogood recording is investigated for CSP within the randomization and restart framework. The principle of our approach is to learn nogoods from the last branch of the search tree before each restart, discarding already explored parts of the search tree in subsequent runs. Remark that a related approach has been proposed in [1,15] for SAT in order to obtain a complete restart strategy while reducing the number of recorded nogoods. Roughly speaking, in our approach, we manage nogoods by introducing a global constraint with a dedicated filtering algorithm which exploits watched literals [32]. Interestingly, this algorithm that allows to enforce Generalized Arc Consistency (GAC) on the base of recorded nogoods can be easily integrated to any constraint propagation engine (e.g. see [38]) but also to any generic GAC algorithm. The simplicity and the good worst-case time complexity (only O(n|B|) where n denotes the number of variables of the constraint network and |B| the number of nogoods in the base B) render this approach attractive. As the number of nogoods recorded before each new run is bounded by the length of the last branch of the search tree, the total number of recorded nogoods is polynomial in the number of restarts. Besides, we show that it is possible to directly identify some nogoods that cannot be subject to minimization with respect to an inference operator φ.
The paper is organized as follows. After some technical background, we introduce socalled reduced nld-nogoods and the principle of nogood recording from restarts. Then we present a detailed description of how such nogoods are extracted and exploited in the context of a backtrack search algorithm. Next, we address the issue of minimizing reduced nld-nogoods. Finally, we give the results of a vast experimentation that we have conducted before concluding.

Technical Background
A Constraint Network (CN) P is a pair (X , C ) where X is a set of variables and C a set of constraints. Each variable X ∈ X has an associated domain, denoted dom(X), which contains the set of values allowed for X. Each constraint C ∈ C involves a subset of variables of X , denoted vars(C), and has an associated relation, denoted rel(C), which contains the set of tuples allowed for vars(C). The number of variables of a CN will be denoted by n, the number of constraints by e, the greatest domain size by d and the greatest constraint arity by r. Also, for any given set E, |E| will denote the number of elements in E.
A solution to a CN is an assignment of values to all the variables such that all the constraints are satisfied. A CN is said to be satisfiable if and only if it admits at least one solution. The Constraint Satisfaction Problem (CSP) is the NP-complete task of determining whether a given CN is satisfiable. A CSP instance is then defined by a CN, and solving it involves either finding one (or more) solution or determining its unsatisfiability. To solve a CSP instance, one can modify the CN by using inference or search methods [11].
The backtracking algorithm (BT) is a central algorithm for solving CSP instances. It performs a depth-first search in order to instantiate variables and a backtrack mechanism when dead-ends occur. Many works have been devoted to improve its forward and backward phases by introducing look-ahead and look-back schemes [11]. Today, MAC [36] is the (lookahead) algorithm considered as the most efficient generic approach to solve CSP instances. It maintains a property called Arc Consistency (AC) during search. When mentioning MAC, it is important to indicate which branching scheme is employed. Indeed, it is possible to consider binary (2-way) branching or non binary (d-way) branching. These two schemes are not equivalent as it has been shown that binary branching is more powerful (to refute unsatisfiable instances) than non-binary branching [20]. With binary branching, at each step of search, a pair (X,a) is selected where X is an unassigned variable and a a value in dom(X), and two cases are considered: the assignment X = a and the refutation X = a. The MAC algorithm (using binary branching) can then be seen as building a binary tree. Classically, MAC always starts by assigning variables before refuting values. Generalized Arc Consistency (GAC) (e.g. [4]) extends AC to non binary constraints, and MGAC is the search algorithm that maintains GAC.

Reduced nld-Nogoods
From now on, we will consider a search tree built by a backtracking search algorithm (e.g. MGAC) that is based on the 2-way branching scheme, positive decisions being performed first, and that maintains a consistency (e.g. Generalized Arc Consistency) at each node.
Each branch of the search tree can then be seen as a sequence of positive and negative decisions, defined as follows: Definition 1. Let P = (X , C ) be a CN and (X,a) be a pair such that X ∈ X and a ∈ dom(X). The assignment X = a is called a positive decision whereas the refutation X = a is called a negative decision. ¬(X = a) is equivalent to X = a and ¬(X = a) is equivalent to X = a. Definition 2. Let Σ = δ 1 , . . . , δ i , . . . , δ m be a sequence of decisions. The sequence δ 1 , . . . , δ i , where δ i is a negative decision, is called a nld-subsequence (negative last decision subsequence) of Σ. The set of positive and negative decisions of Σ are denoted by pos(Σ) and neg(Σ), respectively. Definition 3. Let P be a CN and ∆ be a set of decisions. P | ∆ is the CN obtained from P such that, for any positive decision (X = a) ∈ ∆, dom(X) is restricted to {a}, and, for any negative decision (X = a) ∈ ∆, a is removed from dom(X).
Definition 4. Let P be a CN and ∆ be a set of decisions. ∆ is a nogood of P iff P | ∆ is unsatisfiable.
From any branch of the search tree, from the root to a leaf, a nogood can be extracted from each negative decision (also mentioned in [35]). This is stated by the following property: Proposition 1. Let P be a CN and Σ be the sequence of decisions taken along a branch of the search tree. For any nld-subsequence δ 1 , . . . , δ i of Σ, the set ∆ = {δ 1 , . . . , ¬δ i } is a nogood of P (called nld-nogood) 2. . Proof. As positive decisions are taken first, when the negative decision δ i is encountered, the subtree corresponding to the opposite decision ¬δ i has been refuted.
2 These nogoods contain both positive and negative decisions and then correspond to the definition of generalized nogoods [13,24]. In the following, we will show that nld-nogoods can be reduced in size by considering positive decisions only.
Propositional resolution can be extended to directly deal with CSP nogoods, e.g. in [31] where it is called Constraint Resolution (C-Res for short). Note that we can safely use C-Res since, in the search tree, two opposite decisions, e.g. both X = a and X = a, cannot occur in the same branch and consequently, cannot occur in any nogood. It can be defined as follows: Definition 5. Let P be a CN, and ∆ 1 = Γ ∪ {X = a} and ∆ 2 = Λ ∪ {X = a} be two nogoods of P . We define Constraint Resolution as C-Res(∆ 1 , ∆ 2 ) = Γ ∪ Λ.
It is immediate that C-Res(∆ 1 , ∆ 2 ) is a nogood of P .
Proposition 2. Let P be a CN and Σ be the sequence of decisions taken along a branch of the search tree. For any nld-subsequence Σ = δ 1 , . . . , δ i of Σ, the set ∆ = pos(Σ ) ∪ {¬δ i } is a nogood of P (called reduced nld-nogood).
Proof. Σ = δ 1 , . . . , δ i is a nld-subsequence, so it contains k ≥ 1 negative decisions, denoted by δ g 1 , . . . , δ g k , in the order that they appear in Σ. Remark that we have δ g k = δ i . Let us show by recurrence that ∀j ∈ [1, k], the following hypothesis h(j) is true : ∆ j = pos(Σ ) ∪ {δ g 1 , . . . , δ g j−1 } ∪ {¬δ i } is a nogood of P . First, we show that h(k) holds. From Proposition 1, we know that ∆ k = pos(Σ ) ∪ {δ g 1 , . . . , δ g k−1 } ∪ {¬δ i } is a nogood since ∆ k is the nogood corresponding to the nldsubsequence Σ . Next, we show that if h(j + 1) holds, then h(j) holds too. By hypothesis, ∆ j+1 is a nogood of P . Let Σ j be the nld-subsequence corresponding to the prefix of Σ such that δ g j is its last (negative) decision (we have pos(Σ j ) ⊆ pos(Σ ) and neg(Σ j ) = {δ g 1 , . . . , δ g j }), and ∆ j be its corresponding nogood according to Proposition 1. By applying Constraint Resolution, we have: is then proved to be a nogood of P . As a consequence, we have just proved that h(j) holds. For j = 1, we obtain that ∆ = pos(Σ ) ∪ {¬δ i } is a nogood of P . 2 As an illustration, let Σ = W = a, X = b, Y = c, Z = d be a sequence of decisions taken along a branch of the search tree. We have then: One interesting aspect is that the space required to store all nogoods corresponding to any branch of the search tree is polynomial with respect to the number of variables and the greatest domain size.
Proposition 3. Let P be a CN and Σ be the sequence of decisions taken along a branch of the search tree. The worst-case space complexity to record all nld-nogoods of Σ is O(n 2 d 2 ) while the worst-case space complexity to record all reduced nld-nogoods of Σ is O(n 2 d).
Proof. First, the number of negative decisions in any branch is O(nd). For each negative decision, we can extract a (reduced) nld-nogood. As the size of any (resp. reduced) nldnogood is O(nd) (resp. O(n) since it only contains positive decisions), we obtain an overall space complexity of O(n 2 d 2 ) (resp. O(n 2 d)).
2 It is important to note that reduced nld-nogoods extracted from a branch admit a better pruning capability than nld-nogoods extracted from the same branch since for each nld-subsequence, the corresponding nld-nogood is subsumed by the reduced nld-nogood.

Nogood Recording from Restarts
In [17], it has been shown that the runtime distribution produced by a randomized search algorithm is sometimes characterized by an extremely long tail with some infinite moment. For some instances, this heavy-tailed phenomenon can be avoided by using randomization and restarts, i.e. by restarting search several times while randomizing the employed search heuristic. For constraint satisfaction, restarts have been shown productive on some problems. However, when learning is not exploited (as it is currently the case for most of the academic and commercial solvers), the average performance of the solver is damaged (cf. Section 7).
Nogood recording has not yet been shown to be quite convincing for CSP and further, it is a technique that leads, when uncontrolled, to an exponential space complexity. We propose to address this issue by combining nogood recording and restarts in the following way: reduced nld-nogoods are extracted (to be recorded in a nogood base) from the current branch of the search tree at the end of each run. Our aim is to benefit from both restarts and learning capabilities without sacrificing solver performance and space complexity. Figure 1 depicts the partial search tree explored when the solver is about to restart. Positive decisions being taken first, a δ i (resp. ¬δ i ) corresponds to a positive (resp. negative) decision. Here, search has been stopped after refuting δ 11 and taking the decision ¬δ 11 . The nld-nogoods of P are the following: The first reduced nld-nogood is obtained as follows: Applying the same principle to the other nld-nogoods, we obtain: In order to avoid exploring the same parts of the search space during subsequent runs, recorded nogoods can be exploited. Indeed, it suffices to control that the set of decisions of the current branch does not contain all the decisions of any recorded nogood. Moreover, the negation of the last undetermined decision of any nogood can be inferred as described in the next section. For example, whenever the decision δ 1 becomes true, we can infer ¬δ 2 from nogood ∆ 4 and ¬δ 6 from nogood ∆ 3 .
Finally, we want to emphasize that reduced nld-nogoods extracted from the last branch subsume all reduced nld-nogoods that could be extracted from any branch previously explored. This follows from the fact that each subtree completely explored (and, thus, all nld-nogoods that could be built from all branches of this subtree) is prefixed by at least one nld-nogood of the last branch.

Managing Nogoods
In this section, we show how to efficiently exploit reduced nld-nogoods by using the SAT technique of watched literals [32,42,12]. Reduced nld-nogoods, which correspond to sets (conjunctions) of positive decisions, will be recorded as disjunctions of negative decisions which can be seen as new constraints to be satisfied. We then present an efficient propagation algorithm enforcing GAC on all learned reduced nld-nogoods that can be collectively considered as a global constraint.

Nogood Base and Watched Literals
Reduced nld-nogoods that are extracted from the last branch only contain positive decisions and can be recorded in a base of nogoods B. To exploit them, it suffices, each time a decision is taken during search, to check if the set of current decisions is compatible with all nogoods of B.
In order to provide an efficient access to these nogoods we use the lazy data structure of watched literals [32,42,12] depicted by Figure 2. The principle is to select two decisions per nogood in order to ensure that the nogood is not violated (one watched decision would be sufficient) and no inference can be performed (using the second watched decision). These decisions are called watched literals (referenced by w 1 and w 2 in Figure 2). As long as both watched literals are not falsified, inference is not possible. Note that, in our case, watched literals correspond to negative decisions since reduced nld-nogoods only contain positive decisions and we represent each nogood as a disjunction of negative decisions. When a decision X = a is performed, we have then to check for each nogood which contains X = a as watched literal, if another valid decision can be found. If this is the case, this decision becomes the new watched one (replacing X = a), and otherwise, we have to infer the second watched decision in order to satisfy the nogood.
In practice, when a decision X = a is performed, only nogoods where X = a appears as watched are checked. We maintain for each negative decision the list of nogoods which includes this decision as watched literal. The required data structures can be defined as follows. First, we need an array of nd entries. Each entry corresponds to a negative decision δ and represents the head of a linked list allowing the access to the nogoods of B which contain δ as watched literal. We can access to such a list, denoted B δ , in constant time. Each nogood which is an array of (at most n) negative decisions is associated with two watched literals. In Figure 2, one can observe a nogood base with two recorded nogoods. The first is watched by X = a and Z = c whereas the second one is watched by X = a and W = d.

Recording Nogoods
Reduced nld-nogoods derived from the current branch of the search tree when the current run is stopped can be recorded by calling the storeN ogoods function (see Algorithm 1). The parameters of this function are the sequence of decisions labelling the current branch taken from the root to the leaf and the current nogood base. As observed in Section 3, a reduced nld-nogood can be recorded from each negative decision occurring in this sequence. From the root to the leaf of the current branch, when a positive decision is encountered, its negation is recorded, and when a negative decision is encountered, we build a nogood ∆ from this decision and all previously recorded ones in the set ∆ (line 9). As a nogood is stored as a disjunction of negative decisions, we record the negation of the (positive) decision (line 4). If the nogood is of size 1, it can be directly exploited by reducing the domain of the involved variable (line 7). Otherwise, it is recorded into the nogood base B (line 10).
Two decisions are watched each time a nogood is recorded. Note that any decision of ∆ can be watched since the search algorithm is about to restart. It means that the two end if 13: end for selected decisions will be valid at the beginning of the next run. For each selected decision, a new entry (for the new nogood) is inserted in the list of nogoods watched by this decision.

Exploiting Nogoods
Inferences can be performed using reduced nld-nogoods while establishing (maintaining) Generalized Arc Consistency. We show it with a coarse-grained GAC algorithm based on a variable-oriented propagation scheme [30,8,6]. Algorithm 2 can be applied to any CN (involving constraints of any arity) in order to establish GAC. At preprocessing, propagate must be called with the set S of variables of the network whereas during search, S only contains the variable involved in the last positive or negative decision. At any time, the principle is to have in Q all variables whose domains have been reduced by propagation.
Initially, Q contains all variables of the given set S (line 1). Then, iteratively, each variable X of Q is selected (line 3). If dom(X) corresponds to a singleton {a} (lines 4 to 11), we can exploit recorded nogoods by checking the consistency of the nogood base. This is performed by the function inf erences (described below) which iterates all nogoods involving X = a as watched literal and returns a set of inferences deduced from such nogoods. This set of inferences is then taken into account: for each identified inference Y = b ∈ inf erences(X = a), if b belongs to dom(Y ), then we can remove it, which can yield an inconsistency or an update of the set Q.
The rest of the algorithm (lines 12 to 19) corresponds to the body of a classical generic coarse-grained GAC algorithm. For each constraint C binding X, we perform the revision of all arcs (C, Y ) with Y = X. A revision is performed by a call to the function revise, specific to the chosen coarse-grained arc consistency algorithm, and entails removing values that became inconsistent with respect to C. When the revision of an arc (C, Y ) involves the removal of some values in dom(Y ), revise returns true and the variable Y is added to Q. For more information about this algorithm and some optimizations, see [6]. The algorithm loops until a fixed point is reached.
The principle of Algorithm 3 is to iterate the list of nogoods involving as watched literal the decision given in parameter. For each such nogood, denoted by ∆ at each turn of the for each C | X ∈ vars(C) do 13: for each Y ∈ V ars(C) | X = Y do 14: if revise(C,Y ) then return true 5: end if 6: end for 7: return f alse main loop, we have to look for another watched literal when the second decision watched in ∆ is not true, i.e. b has been removed from dom(Y ) (line 4). This is done by calling the function canF indAnotherW atch. If we cannot find a new watched decision (see line 5), then the second watched decision (Y = b) is inferred.
Finally, the function canF indAnotherW atch (see Algorithm 4) examines all decisions (not currently watched) of the given nogood in order to find the next decision to watch (line 3). Such a decision is either already satisfied or unassigned (line 2).
Even if not described here, note that when a new watched literal has been found, we have to remove the entry (corresponding to the nogood ∆) from the list of nogoods involving X = a as watched literal. Next we have to update (i.e. add an entry) the list of nogoods involving Y = b as new watched literal.

Complexity Analysis
Now, we present the complexities of the different algorithms proposed to store and exploit nogoods. For what follows, remember that B denotes the nogood base and |B| the number of nogoods in B. Proof sketch. First, it is important to note that when a decision X = a (potentially watched) is not valid anymore (i.e. a is the only value remaining in the domain of X), then it cannot be watched again (during a same call to propagate). Also, when looking for a decision to be watched in a reduced nld-nogood (i.e. a set of negative decisions), we can iterate its decisions in any order. To obtain the mentioned complexity, we need a refinement (not presented for the sake of simplicity) of the function canF indAnotherW atch described in this paper.
Considering that the set of decisions of each nogood is represented using an array, we assume here that before calling the propagate algorithm, the two first decisions of each array are swapped with those currently watched. This operation can be performed in O(|B|). Then, whenever we need to find a new watched literal using the canF indAnotherW atch function, we just have to iterate the decisions of the nogood ∆ (given in parameter) by starting from the index that follows the greatest position of both decisions currently watched up to the last decision in the array. As a consequence, for one call to the propagate algorithm, whatever the number of canF indAnotherW atch (and so inf erences) calls is, we will check up to |∆| decisions per nogood ∆. Consequently, the cumulated worst-case complexity of managing any nogood ∆ is then O(|∆|) which is O(n). Overall, the cumulated worst-case time complexity of inf erences in propagate is then O(n|B|). 2 Remark that the worst-case time complexity of exploiting reduced nld-nogoods for each branch of the search tree, from the root to a leaf, is O(n 2 |B|) since the event "variable whose domain becomes singleton" can only happen once per variable and per branch. Corollary 1. The worst-case time complexity of propagate is O(er 2 d r + n|B|) where r is the greatest constraint arity.
Proof. The cost of establishing GAC is O(er 2 d r ) when a generic algorithm such as GAC2001 [4] is used and the cost of exploiting nogoods has just been shown to be O(n|B|). 2 Proposition 6. The worst-case space complexity of storing reduced nld-nogoods is O(n(d + |B|)).
Proof. We know that |B| nogoods of size at most n are recorded. Further, the number of cells introduced to access nogoods is O(|B|) and the size of the array associated to each negative decision is O(nd). We then obtain O(n(d + |B|)). 2

Minimal Reduced nld-Nogoods
In Section 3, we proved that nld-nogoods can be reduced in size by considering positive decisions only. Pursuing the same goal, we introduce in this section the concept of minimal reduced nld-nogood with respect to an inference operator φ. We can then obtain more powerful nogoods.

Minimal φ-Nogoods
In the context of a backtrack search algorithm, the φ operator can be employed at any step of a tree search, using a binary branching scheme. For example, MGAC corresponds to using an operator that enforces (Generalized) Arc Consistency at each node of the search tree.
Definition 6. Let P be a CN , φ(P ) is the CN obtained after applying the operator φ on P .
If there exists a variable with an empty domain in φ(P ) then P is clearly unsatisfiable, denoted φ(P ) = ⊥.
Obviously, φ-nogoods are nogoods, but the opposite is not necessarily true. It is easy to minimize a φ-nogood using a polynomial algorithm such as QuickXplain or one of its variants [21]. In our context, we know that at the end of each run, we can extract nld-nogoods from the current branch and reduce them. One interesting thing is that nld-nogoods which are not φ-nogoods can be directly identified and discarded. This is the case when the last decision δ m of the nld-subsequence from which a nld-nogood ∆ has been extracted, did not directly lead to a dead-end when applying φ. It means that we had to explore a non trivial subtree from that decision. On the other hand, when δ m directly leads to a deadend, we know that this decision necessarily belongs to any φ-nogood included in ∆. As a direct dead−ends  Figure 3. Identification of (reduced) nld-nogoods susceptible to be minimized consequence, δ m can be directly selected as the first transition decision of the minimization algorithm defined in the next subsection. Figure 3 depicts a tree search for a run stopped after refuting δ 10 , where an inference operator φ is maintained at each node. Among the four nld-nogoods that can be extracted, only two yield a direct dead-end: ∆ 1 = {δ 1 , ¬δ 2 , δ 6 } and ∆ 2 = {δ 1 , ¬δ 2 , ¬δ 6 , δ 7 , ¬δ 8 , δ 10 }. ∆ 1 and ∆ 2 are clearly φ-nogoods, as the application of φ after each decision directly leads to an inconsistency. The reduced nld-nogoods that will be considered for minimization are then ∆ 1 = {δ 1 , δ 6 } and ∆ 2 = {δ 1 , δ 7 , δ 10 }. Remark that a reduced nld-nogood obtained from a nld-nogood which is a φ-nogood is not necessarily a φ-nogood itself. Indeed, some negative decisions removed when reducing a nld-nogood may be involved in the conflict.
When reduced nld-nogoods can be highly minimized, the impact on subsequent runs can be quite important. In the best case, one can expect to isolate minimal φ-nogoods of size 1. They correspond to singleton φ-inconsistent values. For example, let us consider the queens-knights problem as proposed in [5] and the algorithm MAC to solve it. As any knight variable is singleton arc inconsistent, if such a variable is involved in the last decision of a reduced nld-nogood, then a singleton arc inconsistent value will be proved by the minimization algorithm. Some results that confirm this behaviour are given in Table 3 of Section 7.

Minimization Techniques
Some works concerning the identification of minimal φ-nogoods (also called conflict-sets) have already been proposed [21,33]. As extracting a minimal φ-nogood is an activity limited to a branch of a search tree, the proposed algorithms involve (at least, partially) a constructive schema in order to keep some incrementality of the propagation process. On the other hand, the last version of QuickXplain [22] exploits a divide and conquer approach (as in [29]) but is defined in a more general context. For example, it can be used to extract Minimal Unsatisfiable Cores (MUCs) of constraint networks which has been recently studied both theoretically and experimentally in [18].
To summarize, in order to find a minimal φ-nogood, it is necessary to iteratively identify the decisions that are involved in it. More precisely, we know that, given a φ-nogood ∆ = {δ 1 , δ 2 , . . . , δ m } of a CN P and a total ordering of the decisions (to simplify, we shall consider the natural order δ 1 , δ 2 , . . . , δ m of the decisions), there exists a decision δ i such that φ(P | {δ 1 ,...,δ i−1 } ) = ⊥ and φ(P | {δ 1 ,...,δ i } ) = ⊥. This decision which clearly belongs to a minimal φ-nogood will be called the transition decision of ∆ (according to the given ordering). Note also that any decision δ j with j > i can be safely removed. This notion of transition decision is analogous to that of transition constraint defined in [18].
To identify a transition decision, it is possible to use a constructive approach, a destructive approach or a dichotomic one. The principle of the constructive approach is to successively add the decisions of ∆ (according to the given ordering) to the CN until an inconsistency is detected when applying φ. The principle of the destructive approach is to initally add all decisions of ∆ to the CN and successively remove them one by one until no more inconsistency is detected when applying φ. As a third alternative, the transition decision can be identified by using a dichotomic search.
To extract a minimal φ-nogood, it suffices to adopt one of the approaches described above. After finding a first 3. transition decision δ i in ∆, one can search a second one after having removed all decisions δ j with j > i of ∆ (since unsatisfiability is preserved) and considering a new order of the decisions such that all found transition decisions are the smallest ones (the background of [22]). This process can be repeated until all decisions of the current nogood correspond to transition decisions that have been successively found. The principle of this iterative process has been described in [9,21,33,18].
In the context of identifying a minimal nogood, we can relate the constructive, destructive and dichotomic approaches succinctly described above to the algorithms called RobustXplain, ReplayXplain and QuickXplain [21]. However, here, we will assume the incrementality of the inference operator φ. It simply means that the worst-case time complexities of applying φ on a given CN from two respective sets of decisions ∆ and ∆ such that ∆ ⊂ ∆ are equivalent. For example, all (known) generic algorithms that enforce φ = (G)AC are incremental. As a consequence, using a constructive approach to identify a transition decision is well-adapted to our purpose. This algorithm will be used for our experimentation and its complexity is discussed in the next subsection.

Complexity Analysis
Proposition 7. The worst-case time complexity of extracting a minimal GAC-nogood from a reduced nld-nogood is O(enr 2 d r ).
Proof. We know that a generic algorithm such as GAC2001 to enforce GAC on a CN is incremental. As a consequence, using a constructive approach to identify a transition decision is O(er 2 d r ), that is to say the worst-case time complexity of establising GAC only once. If the extracted nogood is composed of k decisions, then we obtain an overall complexity in O(ker 2 d r ). As k is O(n), we obtain O(enr 2 d r ) 2 3. If ∆ is a φ-nogood, then we can directly consider δm as the first transition decision.
Corollary 2. In the binary case (i.e. for r = 2), the worst-case time complexity of extracting a minimal AC-nogood from a reduced nld-nogood is O(end 2 ).
Proposition 8. The worst-case time complexity of extracting minimal reduced GAC-nldnogoods (at the end of each run) is O(en 2 r 2 d r+1 ).
Proof. Extracting a GAC-nogood from a reduced nld-nogood is O(enr 2 d r ) and we know that there is at most O(nd) reduced nld-nogoods to be minimized.

Experiments
In order to show the practical interest of the approach described in this paper, we have conducted an extensive experimentation (on a Xeon processor cadenced at 3 GHz and 1GiB RAM). We have used the CSP solver Abscon whose kernel is a MGAC algorithm (embedding GAC3 rm [26]). Abscon can be considered as a state-of-the-art generic CSP solver, considering the results it obtained at the 2005 [39] and 2006 CSP solver competition 4. . We have studied the impact of exploiting restarts (denoted by MGAC+RST), nogood recording from restarts (denoted by MGAC+RST+NG) and the same technique with minimization (denoted by MGAC+RST+NGm). Concerning the restart policy, the initial number of allowed backtracks for the first run has been set to 10 and the increasing factor to 1.5 (i.e. at each new run, the number of allowed backtracks increases by a 1.5 factor). This is a geometric restart policy as introduced in [40]. Note that we have tested other restart policies, but the relative behaviour of the algorithms described in this paper, remained relatively the same. In any case, an in-depth study of the impact of different restart policies on these algorithms is beyond the scope of this paper. For search, we used three different variable ordering heuristics: the classical brelaz [7] and dom/ddeg [3] as well as the adaptive dom/wdeg that has been recently shown to be the most efficient generic heuristic [5,25,19,39]. Importantly, when restarts are performed, randomization is introduced in brelaz and dom/ddeg to break ties. For dom/wdeg, the weight of constraints are preserved from each run to the next one, which makes randomization useless (weights are sufficiently discriminant).
In our first experimentation, we have tested the four algorithms on the full set of 3, 621 instances used as benchmarks for the first round of the 2006 CSP solver competition. The time limit to solve an instance was fixed to 20 minutes. Table 1 provides an overview of the results in terms of the number of instances unsolved within the time limit (#timeouts) and the average cpu time in seconds (avg time) computed from instances solved by all four methods.
First, on random instances, for all the heuristics, it appears that restarting search is penalysing. This is not surprising since there is no structure to exploit from one run to the next one. This result confirms those observed on random SAT instances which do not exhibit any heavy-tailed phenomenon. However, by recording nogoods, we approximately obtain the same results than MGAC without restarts. Second, on structured instances, as expected, recording nogoods from restarts is benefiting. Also, minimizing nogoods has a significant impact, in particular when classical heuristics are used. In an overall analysis, while restarting without learning yields mitigated results, nogood recording from restarts significantly improves the robustness of the solver. Indeed, both the number of unsolved instances and the average cpu time are reduced. This is due to the fact that the solver never explores several times the same portion of the search space while benefiting from restarts. Another view on results in given by Figures 4, 5 and 6 which represent scatter plots displaying pairwise comparisons for dom/ddeg, brelaz and dom/wdeg. Note the presence of many dots on the right-hand side of these figures which represent instances unsolved by the methods whose name label the x-axis.
When focusing to the hardest instances (which involve 680 variables and a greatest domain size of about 50 values) built from the real-world Radio Link Frequency Assignment Problem (RLFAP), we have observed (see Table 2) that using a restart policy allows to be more efficient by almost one order of magnitude. Here, performance is measured in terms of cpu time (in seconds), amount of used memory (in bytes) and number of visited nodes. When we further exploit nogood recording, the gain is about 10%. What is interesting to note here is that (w.r.t. our restart policy) recording nogoods from restarts does not require a lot of memory. Also, we noticed that the number and the size of the reduced nld-nogoods recorded during search were always very limited. As an illustration, MAC+RST+NG solved the instance scen11-f 1 in 36 runs (and 3, 750 seconds) while only 712 nogoods of average size 8.5 and maximum size 33 were recorded.    Finally, we present in Table 3 the results obtained for some instances of the queensknights problem using dom/wdeg. As indicated in Section 6, minimizing nogoods is quite relevant on this kind of instances since singleton arc inconsistent values can be detected. Note that with the dom/wdeg heuristic, results are less impressive. Indeed, it is explained by the fact that this heuristic has a good capability of preventing thrashing.

Conclusion
In this paper, we have studied the interest of recording nogoods in conjunction with a restart strategy. The benefit of restarting search is that the heavy-tailed phenomenon observed on some structured instances can be avoided. The drawback is that we can explore several times the same parts of the search tree. We have shown that it is quite easy to eliminate this drawback by recording a set of nogoods at the end of each run (that can be related to the search signature technique proposed [1] for SAT). For efficiency reasons, nogoods are recorded in a base (and so do not correspond to new constraints) and propagation is performed using the 2-literal watching technique introduced for SAT. One can consider the base of nogoods as a unique global constraint with an efficient associated propagation algorithm. Interestingly, this filtering algorithm can be embedded as a new propagator to any constraint propagation engine but it can also be easily integrated to any generic GAC algorithm as we have shown in this paper. In our approach, reduced nld-nogoods correspond to positive decisions only, and so, can be classified as standard nogoods. One advantage is that the complexity of managing the base of nogoods is small since the only event we need to intercept is when a variable becomes fixed (its domain becoming a singleton). In [24], it has been shown that generalized nogoods are more powerful than standard nogoods. However, it is not immediate if this remains true when a binary branching scheme is used [20]. In any case, it appears that one perspective to the approach proposed in this paper is to compute generalized nogoods, that is to say to extract minimal (not reduced) nld-nogoods from the last branch. The theoretical and practical aspects of this alternative deserve to be studied.