Nogood Recording from Restarts

1 Introduction

Nogood recording (or learning) has been suggested as a technique to enhance CSP (Constraint Satisfaction Problem) solving in [Dechter, 1990]. 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 [Dechter, 1990; Frost and Dechter, 1994; Schiex and Verfaillie, 1994].

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 [Moskewicz et al., 2001]. Indeed, the interest of clause learning has arisen with the availability of large instances (encoding practical applications) which contain some structure and exhibit heavy-tailed phenomenon. Learning in SAT is a typical successful technique obtained from the cross fertilization between CSP and SAT: nogood recording [Dechter, 1990] and conflict directed backjumping [Prosser, 1993] have been introduced for CSP and later imported into SAT solvers [Bayardo and Shrag, 1997; Marques-Silva and Sakallah, 1996].

Recently, a generalization of nogoods, as well as an elegant learning method, have been proposed in [Katsirelos and Bacchus, 2003; 2005] 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 [Bayardo and Shrag, 1997]), 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.

In this paper, nogood recording is investigated within the randomization and restart framework. The principle of our approach is to learn nogoods from the last branch of the search tree before a restart, discarding already explored parts of the search tree in subsequent runs. Roughly speaking, we manage nogoods by introducing a global constraint with a dedicated filtering algorithm which exploits watched literals [Moskewicz et al., 2001]. The worst-case time complexity of this propagation algorithm is O(n2γ) where n is the number of variables and γ the number of recorded nogoods. Besides, we know that γ is at most ndρ where d is the greatest domain size and ρ is the number of restarts already performed. Remark that a related approach has been proposed in [Baptista et al., 2001] for SAT in order to obtain a complete restart strategy while reducing the number of recorded nogoods.

2 Technical Background

A Constraint Network (CN) P is a pair (X , C ) where X is a set of n variables and C a set of e 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).

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 iff 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 [Dechter, 2003].

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 [Dechter, 2003]. Today, MAC [Sabin and Freuder, 1994] is the (look-ahead) 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 [Hwang and Mitchell, 2005]. With binary branching, at each step of search, a pair (X,v) is selected where X is an unassigned variable and v a value in dom(X), and two cases are considered: the assignment X = v and the refutation X ̸= v. 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. [Bessiere et al., 2005]) extends AC to non binary constraints, and MGAC is the search algorithm that maintains GAC.

Although sophisticated look-back algorithms such as CBJ (Conflict Directed Backjumping) [Prosser, 1993] and DBT (Dynamic Backtracking) [Ginsberg, 1993] exist, it has been shown [Bessiere and R´egin, 1996; Boussemart et al., 2004; Lecoutre et al., 2004] that MAC combined with a good variable ordering heuristic often outperforms such techniques.

3 Reduced nld-Nogoods

From now on, we will consider a search tree built by a backtracking search algorithm based on the 2-way branching scheme (e.g. MAC), positive decisions being performed first. 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,v) be a pair such that X ∈ X and v ∈ dom(X). The assignment X = v is called a positive decision whereas the refutation X ̸= v is called a negative decision. ¬(X = v) denotes X ̸= v and ¬(X ̸= v) denotes X = v.

Definition 2 Let Σ = 〈δ1, . . . , δi, . . . , δm〉 be a sequence of decisions where δi is a negative decision. The sequence 〈δ1, . . . , δi〉 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 s.t., for any positive decision (X = v) ∈ Δ, dom(X) is restricted to {v}, and, for any negative decision (X ̸= v) ∈ Δ, v 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, a nogood can be extracted from each negative decision. This is stated by the following proposition:

Proposition 1 Let P be a CN and Σ be the sequence of decisions taken along a branch of the search tree. For any nldsubsequence 〈δ1, . . . , δi〉 of Σ, the set Δ = {δ1, . . . , ¬δi} is a nogood of P (called nld-nogood) 1 .

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. ✷

These nogoods contain both positive and negative decisions and then correspond to the definition of generalized nogoods [Focacci and Milano, 2001; Katsirelos and Bacchus, 2005]. In the following, we show that nld-nogoods can be reduced in size by considering positive decisions only. Hence, we benefit from both an improvement in space complexity and a more powerful pruning capability.

By construction, CSP nogoods do not contain two opposite decisions i.e. both x = v and x ̸= v. Propositional resolution allows to deduce the clause r = (α∨β) from the clauses x∨α and ¬x ∨ β. Nogoods can be represented as propositional clauses (disjunction of literals), where literals correspond to positive and negative decisions. Consequently, we can extend resolution to deal directly with CSP nogoods (e.g. [Mitchell, 2003]), called Constraint Resolution (C-Res for short). It can be defined as follows:

Definition 5 Let P be a CN, and Δ1 = Γ ∪ {xi = vi} and Δ2 = Λ ∪ {xi ̸= vi} 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 nldsubsequence Σ′ = 〈δ1, . . . , δi〉 of Σ, the set Δ = pos(Σ′ ) ∪ {¬δi} is a nogood of P (called reduced nld-nogood).

Proof. We suppose that Σ contains k ≥ 1 negative decisions, denoted by δg1 , . . . , δgk , in the order that they appear in Σ. The nld-subsequence of Σ with k negative decisions is Σ′1 = 〈δ1, . . . , δg1 , . . . , δgk 〉. Its corresponding nld-nogood is Δ1 = {δ1, . . . , δg1 , . . . , δgk-1 , . . . , ¬δgk }, δgk-1 being now the last negative decision. The nld-subsequence of Σ with k - 1 negative decisions is Σ′2 = 〈δ1, . . . , δg1 , . . . , δgk-1 〉. Its corresponding nld-nogood is Δ2 = {δ1, . . . , δg1 , . . . ,¬δgk-1 }. We now apply C-Res between Δ1 and Δ2 and we obtain Δ′1 = C-Res(Δ1, Δ2) = {δ1, . . . , δg1 , . . . , δgk-2 , . . . , δgk-1-1, δgk-1+1, . . . , ¬δgk }. The last negative decision is now δgk-2 , which will be eliminated with the nld-nogood containing k - 2 negative decisions. All the remaining negative decisions are then eliminated by applying the same process. ✷

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.

1 The notation {δ1, . . . , ¬δi} corresponds to {δj ∈ Σ | j < i} ∪ {¬δi}, reduced to {¬δ1} when i = 1.

Proposition 3 Let P be a CN and Σ be the sequence of decisions taken along a branch of the search tree. The space complexity to record all nld-nogoods of Σ is O(n2d2 ) while the space complexity to record all reduced nld-nogoods of Σ is O(n2d).

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(n2d2 ) (resp. O(n2d)). ✷

4 Nogood Recording fromRestarts

In [Gomes et al., 2000], 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 random restarts, i.e. by restarting search several times while randomizing the employed search heuristic. For constraint satisfaction, restarts have been shown productive. 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 6).

Nogood recording has not yet been shown to be quite convincing for CSP (one noticeable exception is [Katsirelos and Bacchus, 2005]) 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 recorded from the last (and current) branch of the search tree between 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. Search has been stopped after refuting δ11 and taking the decision ¬δ11. The nld-nogoods of P are the following: Δ1 = {δ1, ¬δ2, ¬δ6, δ8, ¬δ9, δ11}, Δ2 = {δ1, ¬δ2, ¬δ6, δ8, δ9}, Δ3 = {δ1, ¬δ2, δ6}, Δ4 = {δ1, δ2}. The first reduced nld-nogood is obtained as follows:

Applying the same process 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 decisions of the current branch do not contain all decisions of one nogood. Moreover, the negation of the last unperformed decision of any nogood can be inferred as described in the next section. For example, whenever the decision δ1 is taken, 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 nldnogoods that could be extracted from any branch previously explored.

5 Managing Nogoods

In this section, we now show how to efficiently exploit reduced nld-nogoods by combining watched literals with propagation. We then obtain an efficient propagation algorithm enforcing GAC on all learned nogoods that can be collectively considered as a global constraint.

5.1 Recording Nogoods

Nogoods derived from the current branch of the search tree (i.e. reduced nld-nogoods) when the current run is stopped can be recorded by calling the storeNogoods function (see Algorithm 1). The parameter of this function is the sequence of literals labelling the current branch. 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, it is recorded in the set Δ (line 4), and when a negative decision is encountered, we record a nogood from the negation of this decision and all recorded positive ones (line 9). If the nogood is of size 1 (i.e. Δ = ∅), it can be directly exploited by reducing the domain of the involved variable (see line 7). Otherwise, it is recorded, by calling the addNogood function (not described here), in a structure exploiting watched literals [Moskewicz et al., 2001].

We can show that the worst-case time complexity of storeNogoods is O(λpλn) where λp and λn are the number of positive and negative decisions on the current branch, respectively.

1: Δ← ∅ 2: for i ∈ [1,m] do 3: if δi is a positive decision then 4: Δ←Δ∪ {δi} 5: else 6: if Δ = ∅ then 7: with δi = (X, v), remove v from dom(X) 8: else 9: addNogood(Δ ∪ {¬δi}) 10: end if 11: end if 12: end for

5.2 Exploiting Nogoods

Inferences can be performed using nogoods while establishing (maintaining) Generalized Arc Consistency. We show it with a coarse-grained GAC algorithm based on a variableoriented propagation scheme [McGregor, 1979]. The 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 {v} (lines 4 to 7), we can exploit recorded nogoods by checking the consistency of the nogood base. This is performed by the function checkWatches (not described here) by iterating all nogoods involving X = v as watched literal. For each such nogood, either another literal not yet watched can be found, or an inference is performed (and the set Q is updated).

The rest of the algorithm (lines 8 to 12) 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 coarsegrained 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. The algorithm loops until a fixed point is reached.

The worst-case time complexity of checkWatches is O(nγ) where γ is the number of reduced nld-nogoods stored in the base and n is the number of variables 2 . Indeed, in the worst case, each nogood is watched by the literal given in parameter, and the time complexity of dealing with a reduced nld-nogood in order to find another watched literal or make an inference is O(n). Then, the worst-case time complexity of propagate is O(er2dr +n2γ) where r is the greatest constraint arity. More precisely, the cost of establishing GAC (using a generic approach) is O(er2dr ) when an algorithm such as GAC2001 [Bessiere et al., 2005] is used and the cost

2 In practice, the size of reduced nld-nogoods can be far smaller than n (cf. Section 6).

1: Q←S 2: while Q ̸= ∅ do 3: pick and delete X fromQ 4: if | dom(X) | = 1 then 5: let v be the unique value in dom(X) 6: if checkWatches(X = v) = false then return false 7: end if 8: for each C | X ∈ vars(C) do 9: for each Y ∈ V ars(C) | X ̸= Y do 10: if revise(C,Y ) then 11: if dom(Y ) = ∅ then return false 12: else Q ← Q ∪ {Y } 13: end while 14: return true

of exploiting nogoods to enforce GAC is O(n2γ). Indeed, checkWatches is O(nγ) and it can be called only once per variable.

The space complexity of the structures introduced to manage reduced nld-nogoods in a backtracking search algorithm is O(n(d+γ)). Indeed, we need to store γ nogoods of size at most n and we need to store watched literals which is O(nd).

6 Experiments

In order to show the practical interest of the approach described in this paper, we have conducted an extensive experimentation (on a PC Pentium IV 2.4GHz 512Mo under Linux). We have used the Abscon solver to run M(G)AC2001 (denoted by MAC) and studied the impact of exploiting restarts (denoted by MAC+RST) and nogood recording from restarts (denoted by MAC+RST+NG). 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). We used three different variable ordering heuristics: the classical brelaz [Brelaz, 1979] and dom/ddeg [Bessiere and R´egin, 1996] as well as the adaptive dom/wdeg that has been recently shown to be the most efficient generic heuristic [Boussemart et al., 2004; Lecoutre et al., 2004; Hulubei and O'Sullivan, 2005; van Dongen, 2005]. 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 three algorithms on the full set of 1064 instances used as benchmarks for the first competition of CSP solvers [van Dongen, 2005]. The time limit to solve an instance was fixed to 30 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 three methods. Figures 2 and 3 represent scatter plots displaying pairwise comparisons for dom/ddeg and dom/wdeg. Finally, Table 2 focuses on the most difficult real-world instances of the Radio Link Frequency Assignment Problem (RLFAP). Performance is measured in terms of the cpu time in seconds (no timeout)

and the number of visited nodes. An analysis of all these results reveals three main points.

Restarts (without learning) yields mitigated results. First, we observe an increased average cpu time for all heuristics and fewer solved instances for classical ones. However, a close look at the different series reveals that MAC+RST combined with brelaz (resp. dom/ddeg) solved 27 (resp. 32) less instances than MAC on the series ehi. These instances correspond to random instances embedding a small unsatisfiable kernel. As classical heuristics do not guide search towards this kernel, restarting search tends to be nothing but an expense. Without these series, MAC+RST would have solved more instances than MAC (but, still, with worse performance). Also, remark that dom/wdeg renders MAC+RST more robust than MAC (even on the ehi series).

Nogood recording from restarts improves MAC performance. 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.

Nogood recording from restarts applied to real-world instances pays off. When focusing to the hardest instances [van Dongen, 2005] built from the real-world RLFAP instance scen-11, we can observe in Table 2 that using a restart policy allows to be more efficient by almost one order of magnitude. When we further exploit nogood recording, the gain is about 10%.

Finally, we noticed that the number and the size of the reduced nld-nogoods recorded during search were always very limited. As an illustration, let us consider the hardest RLFAP instance scen11 - f1 which involves 680 variables and a greatest domain size of 43 values. MAC+RST+NG solved this instance in 36 runs while only 712 nogoods of average size 8.5 and maximum size 33 were recorded.

7 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 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. 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.

Our experimental results show the effectiveness of our approach since the state-of-the-art generic algorithm MACdom/wdeg is improved. Our approach not only allows to solve more instances than the classical approach within a given timeout, but also is, on the average, faster on instances solved by both approaches.

Acknowledgments

This paper has been supported by the CNRS and the ANR "Planevo" project noJC05 41940.