Christophe Lecoutre
email: lecoutre@cril.fr

Sébastien Tabary
email: tabary@cril.fr

Symmetry-reinforced Nogood Recording from Restarts

Nogood recording from restarts is a form of lightweight learning that combines nogood recording with a restart strategy. At the end of each run, nogoods are extracted from the current (rightmost) branch of the search tree. These nogoods can be used to prevent parts of the search space from being explored more than once. In this paper, we propose to reinforce nogood recording (from restarts) by exploiting symmetries: every time the solver has to be restarted, not only the nogoods that are extracted from the current branch are recorded, but also some additional nogoods that can be computed by means of the previously identified problem symmetries. This mechanism of computing symmetric nogoods can be iterated until a fixed-point is reached, and controlled (if necessary) by limiting the number and/or the size of recorded nogoods.

Introduction

The runtime distribution of a randomized search algorithm is sometimes characterized by an extremely long tail with some infinite moment (e.g., see [START_REF] Gomes | Heavy-tailed phenomena in satisfiability and constraint satisfaction problems[END_REF]). For some constraint satisfaction (optimization) problems, it has been found worthwhile to employ restarts with a randomized search heuristic. However, if restarts are employed without learning, the average performance of the solver can be damaged on some problem instances because the same parts of the search space may be explored several times. At the opposite, nogood recording without restarts has not yet been shown to be entirely convincing for constraint satisfaction; when uncontrolled, nogood recording can lead to exponential space complexity. Although restarts without nogood recording, and also nogood recording without restarts, may be of limited use, a combination of both of these techniques happen to be more useful. For example, in [START_REF] Lecoutre | Recording and minimizing nogoods from restarts[END_REF], it has been shown that so-called reduced nld-nogoods can be extracted (to be recorded in a nogood base) from the current (rightmost) branch of the search tree at the end of each run. These nogoods can be used to prevent parts of the search space from being explored more than once. Thus we can then benefit from restarts and learning capabilities without sacrificing solver performance or space complexity.

On the other hand, symmetry breaking is an important research topic in constraint programming. The use of symmetries in search problems is conceptually simple. If two distinct nodes in a search tree are related by a symmetry, there is no need to explore both of them because symmetries preserve satisfiability. When a node is an internal dead-end, the nodes that are symmetrical to it are guaranteed to be internal dead-ends as well. When a node is the root of a fruitful subtree (i.e., a subtree containing solutions), symmetrical solutions can be computed automatically, i.e. without exploring symmetrical nodes. Breaking symmetries can facilitate determining the satisfiability of an instance or counting/computing the full set of solutions.

Symmetry breaking involves two distinct issues. First, symmetries must be identified. Either the user is asked to perform this (often difficult) task, or otherwise an automatic procedure identifies symmetries. Second, the symmetries must be exploited. For this, there are two main categories of approaches (apart from reformulation techniques). One approach posts symmetry-breaking constraints during a preprocessing stage, to speed up subsequent search. The other main strategy is to use symmetries dynamically during search to prevent exploration of irrelevant nodes. For the exploitation of symmetries, published methods include symmetry-breaking constraints [START_REF] Crawford | Symmetry-breaking predicates for search problems[END_REF][START_REF] Flener | Breaking row and column symmetries in matrix models[END_REF][START_REF] Walsh | General symmetry breaking constraints[END_REF], symmetry-breaking heuristics [START_REF] Meseguer | Exploiting symmetries within constraint satisfaction search[END_REF], symmetry breaking during search (SBDS) [START_REF] Backofen | Excluding symmetries in constraint based search[END_REF][START_REF] Gent | Symmetry breaking during search[END_REF][START_REF] Gent | Groups and constraints: Symmetry breaking during search[END_REF], symmetry breaking via dominance detection (SBDD) [START_REF] Fahle | Symmetry breaking[END_REF][START_REF] Focacci | Global cut framework for removing symmetries[END_REF][START_REF] Puget | Symmetry breaking revisited[END_REF][START_REF] Sellmann | Structural symmetry breaking[END_REF], amongst others.

In this paper, we propose to reinforce nogood recording (from restarts) by exploiting problem symmetries. The principle is quite simple: every time the solver has to be restarted, not only the nogoods that are extracted from the current branch are recorded, but also some additional nogoods that can be computed by means of the problem symmetries. Interestingly, this mechanism of computing symmetric nogoods can be iterated until a fixed-point is reached. Of course, if necessary, one can control this form of reinforced learning by limiting the number of recorded nogoods and/or their size.

Technical Background

A constraint network (CN) P is composed of a finite set of n variables, denoted by vars(P ), and a finite set of e constraints, denoted by cons(P ). Each variable x has a domain which is the finite set of values that can be assigned to x. The initial domain of a variable x is denoted by dom init (x) whereas the current domain of x (in the context of P ) is denoted by dom P (x), or more simply dom(x); we always have dom(x) ⊆ dom init (x). The maximum domain size for a given CN will be denoted by d. A v-value is a variable-value pair (x, a) where x is a variable and a ∈ dom init (x). A v-value of a CN P is a v-value (x, a) such that x ∈ vars(P ) and a ∈ dom P (x) and v-vals(P ) denotes the set of v-values of P Each constraint c involves an ordered set of variables, called the scope of c and denoted by scp(c), and is defined by a relation which is the set of tuples allowed for the variables involved in c. A unary (resp., binary) constraint involves 1 (resp., 2) variable(s), and a non-binary one strictly more than 2 variables.

An instantiation I of a set X = {x 1 , . . . , x k } of variables is a set {(x 1 , a 1 ), . . . , (x k , a k )} such that ∀i ∈ 1..k, a i ∈ dom init (x i ); X is denoted by vars(I) and each a i is denoted by I[x i ]. An instantiation I on a CN P is an instantiation of a set X ⊆ vars(P ) ; it is complete if vars(I) = vars(P ). I is valid on P iff ∀(x, a) ∈ I, a ∈ dom(x). I covers a constraint c iff scp(c) ⊆ vars(I), and I satisfies a constraint c with scp(c) = {x 1 , . . . , x r } iff (i) I covers c and (ii) the tuple (I[x 1 ], . . . , I[x r ]) ∈ rel(c). An instantiation I on a CN P is locally consistent iff (i) I is valid on P and (ii) every constraint of P covered by I is satisfied by I. A solution of P is a complete locally consistent instantiation on P ; sols(P ) denotes the set of solutions of P . An instantiation I on a CN P is globally inconsistent, or a nogood, iff it cannot be extended to a solution of P .

A positive decision δ is a restriction on a variable x of the form x = a whereas a negative decision is a restriction of the form x = a, where a ∈ dom init (x). When decisions are taken on a CN, we obtain a new CN defined as follows. Let P be a CN and ∆ be a set of decisions on P , P | ∆ is the CN obtained (derived) from P such that, for each positive decision x = a ∈ ∆, each value b ∈ dom(x) with b = a is removed from dom(x), and, for each negative decision x = a ∈ ∆, a is removed from dom(x). For any set ∆ of decisions, vars(∆) denotes the set of variables occurring in decisions of ∆. A nogood is defined as a globally inconsistent instantiation. Such nogoods are sometimes said to be standard and they correspond to the definition proposed by Dechter in [START_REF] Dechter | Constraint processing[END_REF]. An alternative definition for standard nogoods is: a standard nogood of P is a set ∆ of positive decisions on P such that P | ∆ is unsatisfiable. Consideration of positive and negative decisions as in [START_REF] Focacci | Global cut framework for removing symmetries[END_REF][START_REF] Katsirelos | Generalized nogoods in CSPs[END_REF] leads to a generalization of standard nogoods, called generalized nogoods: A set of decisions ∆ on a CN P is a generalized nogood of P iff P | ∆ is unsatisfiable. Clearly, a (standard) nogood is generalized but the opposite is not necessarily true. For example, ∆ = {x = a, y = b} such that P | ∆ is unsatisfiable is a standard nogood of P , and consequently by definition a generalized nogood of P . But ∆ = {x = a, z = c}, such that P | ∆ is unsatisfiable, is a generalized nogood of P which is not standard. In fact a generalized nogood can represent an exponential number of standard ones [START_REF] Katsirelos | Generalized nogoods in CSPs[END_REF].

The search space of a CN can be reduced by a filtering process (called constraint propagation) based on some properties (called consistencies) that allow us to identify and record explicit nogoods in CNs; e.g., identified nogoods of size 1 correspond to inconsistent values that can be safely removed from variable domains. The most famous consistency is GAC (Generalized Arc Consistency) defined as follows. A value (x, a) of P is GAC-consistent iff for each constraint c of P involving x there exists a valid instantiation I of scp(c) such that I satisfies c and I[x] = a. P is GAC-consistent iff every value of P is GAC-consistent. For binary constraints, GAC is often referred to as AC (Arc Consistency).

Nogood recording from restarts

Henceforward, we consider a backtrack search algorithm using binary branching, taking positive decisions first, maintaining a consistency at each step, and using a restart strategy. For any branch of the search tree (built during a run of the backtrack search algorithm), a set of relevant standard nogoods (instantiations that cannot lead to a solution) can be identified directly. Nogood recording from restarts [START_REF] Lecoutre | Recording and minimizing nogoods from restarts[END_REF] means recording these nogoods but only for the last (rightmost) branch of the search tree just before the restart.

Each branch of the search tree is a sequence of positive and negative decisions. For each branch starting from the root, a generalized nogood can be extracted from each negative decision [START_REF] Puget | Symmetry breaking revisited[END_REF][START_REF] Lecoutre | Recording and minimizing nogoods from restarts[END_REF], as follows. Let Σ = δ 1 , . . . , δ m be a sequence of decisions, if δ i is a negative decision, with 1 ≤ i ≤ m, then the subsequence δ 1 , . . . , δ i of Σ comprising the i first decisions of Σ is called a nldsubsequence (negative last decision subsequence) of Σ. Let P be a a constraint network and Σ be the sequence of decisions taken along a branch (starting from the root) of the search tree built for P . For any nld-subsequence δ 1 , . . . , δ i of Σ, the set For example, the sequence of decisions taken along the rightmost branch in Figure 1 is v = a, w = b, y = b, x = c, w = a, z = b . The nld-subsequences and nld-nogoods that can be extracted from this branch are as follows:

∆ = {δ j ∈ Σ | 1 ≤ j < i} ∪ {¬δ i } is a generalized nogood of P , called nld-nogood. x = a z = a ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ v = a w = b x = a w = b z = b y = c y = b y = b z = b z = a y = c x = c ⊥ ⊥ ⊥ w = a y = c y = c z = b z = b w = a
nld-subsequences nld-nogoods

v = a, w = b {v = a, w = b} v = a, w = b, y = b {v = a, w = b, y = b} v = a, w = b, y = b, x = c, w = a {v = a, w = b, y = b, x = c, w = a} v = a, w = b, y = b, x = c, w = a, z = b {v = a, w = b, y = b, x = c, w = a, z = b}
Although Σ is a sequence we use set notations (δ j ∈ Σ) because there is no ambiguity; no decision occurs more than once in Σ. In our particular context, nld-nogoods can be systematically reduced in size by omitting negative decisions, thus reducing space requirements and improving pruning capability. Let P be a constraint network and Σ be the sequence of decisions taken along a branch of the search tree (starting from the root). For any nld-subsequence Σ ′ = δ 1 , . . . , δ i of Σ, the set ∆ = pos(Σ ′ ) ∪ {¬δ i } is a (standard) nogood of P , called a reduced nld-nogood, where pos(Σ ′ ) denotes the set of positive decisions of Σ ′ .

For example, for the rightmost branch in Figure 1 the nld-nogoods and reduced nld-nogoods are: nld-nogoods reduced nld-nogoods

{v = a, w = b} {v = a, w = b} {v = a, w = b, y = b} {v = a, y = b} {v = a, w = b, y = b, x = c, w = a} {v = a, x = c, w = a} {v = a, w = b, y = b, x = c, w = a, z = b} {v = a, x = c, z = b}
The worst-case space complexity to record all reduced nld-nogoods of Σ is O(n 2 d). Each nld-nogood is subsumed by its reduced nld-nogood, which has greater pruning capability. Besides, reduced nld-nogood are easier to manage because they are standard nogoods. Indeed, standard nogoods, which are sets (conjunctions) of positive decisions, can be recorded in an equivalent form as sets (disjunctions) of negative decisions. Using this representation, an efficient propagation algorithm can enforce generalized arc consistency on these nogood constraints by means of the SAT technique of watched literals [START_REF] Moskewicz | Chaff: Engineering an Efficient SAT Solver[END_REF][START_REF] Zhang | The quest for efficient Boolean satisfiability solvers[END_REF]. All nogoods are collected in a so-called nogood base denoted here by B.

Symmetries on Constraint Networks

The first part of this section provides a brief introduction to group theory. A group is a pair (G, ⋆) composed of a set G and a binary operation ⋆ defined on G, such that the following requirements are satisfied:

-Closure: ∀f ∈ G, ∀g ∈ G, f ⋆ g ∈ G -Identity element: ∃e ∈ G | ∀f ∈ G, e ⋆ f = f ⋆ e = f -Inverse element: ∀f ∈ G, ∃g ∈ G | f ⋆ g = g ⋆ f = e; g is noted f -1 -Associativity: ∀f ∈ G, ∀g ∈ G, ∀h ∈ G, (f ⋆ g) ⋆ h = f ⋆ (g ⋆ h)
For example, (Z, +) is a group, where Z denotes the set of integers, and + denotes ordinary addition. A subgroup of a group (G, ⋆) is a group (H, ⋆) such that H ⊆ G. The order of a group (G, ⋆) is the number |G| of elements in G. A group can be represented by means of a subset of its elements, called generating set. A generating set of a group (G, ⋆) is a subset H of G such that each element of G can be expressed by composition (using ⋆) of elements of H, called generators, and their inverses. We write G =< H >. A generating set is irredundant iff no generator can be expressed by composition of the other generators. Generating sets allow compact representations of groups since for any group (G, ⋆), there exists a generating set of size log 2 (|G|) or smaller.

We are interested in permutation groups because we will be concerned with the symmetries that are permutations. A permutation on a set D is a bijection σ defined from D onto D. The image of an element a ∈ D by σ is denoted by a σ . For example, let D = {1, 2, 3, 4} be a set of four integers. A possible permutation σ on D is: 1 σ = 2, 2 σ = 3, 3 σ = 1 and 4 σ = 4. A permutation can be represented by a set of cycles of the form (a 1 , a 2 , . . . , a k ) which means that a i is mapped to a i+1 for i ∈ 1..k -1 and a k is mapped to a 1 . The set of cycles for our permutation σ is {(1, 2, 3), (4)}, but in practice, cycles of length one can be omitted because such cycles have no effect, thereby we obtain {(1, 2, 3)}. Let D be a set and let σ 1 , σ 2 be two permutations on D. The composition σ 3 = σ 1 • σ 2 of σ 1 and σ 2 is defined as follows: ∀a ∈ D, a σ3 = a σ1•σ2 = (a σ2 ) σ1 . For the previous example, if σ ′ = {(2, 4), (1, 3)} is a second permutation on D, then

σ ′′ = σ ′ • σ is: 1 σ ′′ = 4, 2 σ ′′ = 1, 3 σ ′′ = 3 and 4 σ ′′ = 2, which gives {(1, 4, 2)} in cyclic form.
For constraint networks, two definitions of symmetries have been recognized [START_REF] Cohen | Symmetry definitions for constraint satisfaction problems[END_REF] as particularly relevant because they are sufficiently general to encompass most of the previous definitions in the literature. Generality comes from the set on which symmetries are defined: this is the set of v-values (variable-value pairs). The first definition, which is used for example in [START_REF] Kelsey | New developments in symmetry breaking in search using computational group theory[END_REF][START_REF] Puget | Automatic detection of variable and value symmetries[END_REF], introduces solution symmetries that only preserve sets of solutions. The second definition introduces constraint symmetries (or problem symmetries) that preserve the set of constraints. The second definition is less general than the first but is more applicable in practice. A constraint symmetry is a syntactical symmetry [START_REF] Benhamou | Study of symmetry in constraint satisfaction problems[END_REF] that is not limited by necessarily choosing values in the same domain.

A simple mechanism to define symmetries, including solution and constraint symmetries, is to refer to instantiations. Sets of valid instantiations play the role of structure: Definition 1. Let P be a constraint network and R be a set of valid instantiations on P . A symmetry on P for R is a permutation σ of v-vals(P ) such that R σ = R.

Sometimes symmetries are restricted so that only variables or values are permuted. A variable symmetry does not change values whereas a value symmetry does not change variables. Let P be a constraint network and R be a set of valid instantiations on P , a variable symmetry on P for R is a symmetry σ on P for R such that for every (x, a) ∈ v-vals(P ), (x, a) σ = (x σvars , a) where σ vars is a permutation of vars(P ). Clearly, a variable symmetry is defined (equivalently) by a permutation on vars(P ). We shall mainly use this simpler permutation.

To illustrate symmetries on constraint networks, let us consider the 4-queens instance: can we put 4 queens on a board of size 4 × 4 such that no two queens attack each other? We can model this problem using one variable per queen (column) such that the domains contain values that denote row numbers. Denoting the variables by x a , x b , x c and x d , to clarify the correspondence with columns, Figure 2 shows the two solutions for this instance. The first is {(x a , 2), (x b , 4), (x c , 1), (x d , 3)} and the second is {(x a , 3), (x b , 1), (x c , 4), (x d , 2)}. This instance has exactly eight constraint symmetries. Among these eight symmetries, if we disregard the identity permutation, only f h (reflection through the horizontal middle line) is a variable symmetry and only f v (reflection through the vertical middle line) is a is value symmetry. Using a simplified notation for f h where only variables are swapped, we obtain in cyclic form {(x a , x d ), (x b , x c )}, which means that x a is swapped with x d and x b is swapped with x c . 5 Symmetry-reinforced Nogood Recording

In this section, we present our approach to reinforce nogood recording from restarts by means of symmetries. First we introduce symmetries on instantiations and nogoods together with symmetry rules that can be connected to earlier works (e.g., [START_REF] Szeider | The complexity of resolution with generalized symmetry rules[END_REF]), and then we describe an original algorithm to compute symmetrical nogoods. As a related work, the authors of [START_REF] Chu | Symmetries and lazy clause generation[END_REF] [START_REF] Lecoutre | Recording and minimizing nogoods from restarts[END_REF] would allow us to further improve the quality of nogoods partially in the spirit of the explanations used to compute 1UIPs. The idea of handling symmetric nogoods in the context of restarted solvers has also been studied in [START_REF] Heller | Dynamic symmetry breaking restarted[END_REF].

Symmetries on Nogoods

Because symmetries preserve the structure of constraint networks, we can reason from instantiations and nogoods as explained below. We first need to introduce the notion of admissible instantiations [START_REF] Walsh | General symmetry breaking constraints[END_REF].

Definition 2 (Admissibility). Let P be a constraint network, σ be a symmetry on P and I be a valid instantiation on P . I is admissible for σ iff I σ is an instantiation on P .

For example, consider the instantiation I = {(x a , 1), (x b , 2)} for the 4-queens instance. For the symmetry r 90 (rotation by 90 • right), we obtain I r 90 = {(x a , 4), (x b , 3)}, which is an instantiation. Thus I is admissible for r 90 . Now if I ′ = {(x a , 1), (x b , 1)}, by r 90 , we obtain I ′r 90 = {(x a , 4), (x a , 3)}, which is not an instantiation, so I ′ is not admissible for r 90 . By definition, an instantiation cannot contain two v-values involving the same variable.

Note that valid instantiations are always admissible for variable symmetries and for value symmetries.

Symmetries preserve solutions. The following proposition is related to Proposition 2.1 in [START_REF] Crawford | Symmetry-breaking predicates for search problems[END_REF].

Proposition 1. Let P be a constraint network, σ be a symmetry on P and I be a complete valid instantiation on P . I is a solution of P iff I σ is a solution of P .

Proof. If I ∈ sols(P ) then necessarily I σ ∈ sols(P ) since sols(P ) σ = sols(P ). The other direction holds because σ -1 is also a solution symmetry.

For example, for the 4-queens instance, {(x a , 2), (x b , 4), (x c , 1), (x d , 3)} f h gives {(x d , 2), (x c , 4), (x b , 1), (x a , 3)} which is the second solution. Interestingly, this result can be refined as follows.

Proposition 2. Let P be a constraint network, σ be a symmetry on P and I be a valid instantiation on P . I is a good (globally consistent instantiation) on P iff I σ is a good on P .

Proof. If I is a good, this means that there exists at least a solution I ′ of P that extends I. We know from Proposition 1 that I ′σ is also a solution of P . Necessarily, I ′σ extends I σ , so I σ is a good.

Corollary 1. Let P be a constraint network, σ be a symmetry on P and I be a valid instantiation on P . I is a nogood (globally inconsistent instantiation) on P iff either I is not admissible for σ or I σ is a nogood on P .

Proof. From Proposition 2, we know that I is a good on P iff I σ is a good on P . This is equivalent to: I is not a good on P iff I σ is not a good on P . Because I is by hypothesis a valid instantiation, I is necessarily a nogood. However, nothing can be said precisely about I σ . I σ is not a good, which means that either I is not admissible for σ or I σ is a nogood.

An Algorithm to Reinforce Nogood Recording from Restarts

Following [START_REF] Lecoutre | Recording and minimizing nogoods from restarts[END_REF], when the current run is stopped, the function extractNogoods, Algorithm 1, derives reduced nld-nogoods from the current branch of the search tree. This function admits as a parameter the sequence of decisions taken along the current rightmost branch and returns a set of standard nogoods. Each negative decision in this sequence yields a standard nogood. From the root to the last decision of the current branch, we record successive positive decisions (in a set denoted by positiveDecisions). For each negative decision encountered, the algorithm constructs a standard nogood ∆ from the negation of this decision and all previous positive decisions recorded (line 7). Computed nogoods are collected in a set Γ . Additionally, for each nogood ∆ identified from the sequence of decisions, the procedure computeSymmetricNogoodsOf (Algorithm 2) is called at line 8 to compute a set of symmetrical nogoods from ∆ that can be added to Γ . Nogoods in the set Γ computed by extractNogoods will be later added to the global nogood base B, and exploited in subsequent runs. The function computeSymmetricNogoodsOf admits as a parameter a nogood ∆ and returns a set of standard nogoods that are all symmetric to ∆. Note that this function uses three global data: B, Ψ and updateQueue. B is the global nogood base. Ψ is a set of symmetries identified for the CN to be solved. For example, this set may only contain in practice the symmetries corresponding to the generators returned by a graph automorphism software. updateQueue is a Boolean that indicates whether a fixed point has to be reached or not, that is to say, whether all symmetrical nogoods have to be computed or not.

Algorithm 2: computeSymmetricNogoodsOf(∆: nogood): set of nogoods

Global: a nogood base B Global: a set of symmetries Ψ of the CN to be solved Global: a Boolean updateQueue Input:

a nogood ∆ Output: a set of nogoods Γ Γ ← ∅ 1 Q ← {∆} 2 while Q = ∅ do 3 pick and delete ∆ ′ from Q 4 foreach symmetry σ of Ψ do 5 ∆ ′′ ← ∆ ′σ 6 if ∆ ′ is admissible for σ and ∆ ′′ / ∈ B then 7 Γ ← Γ ∪ {∆ ′′ } 8 if updateQueue then 9 Q ← Q ∪ {∆ ′′ } 10 return Γ
A set Q is used to store nogoods from which symmetrical variants have to be sought. Initially, Q is initialized with the nogood ∆ given as a parameter. Each nogood ∆ ′ is successively picked and deleted from Q and symmetrical nogoods are computed. More precisely, a nogood ∆ ′′ is computed from ∆ ′ for each symmetry σ in Ψ . If ∆ ′ is not admissible for σ (this may be checked from ∆ ′′ , for example) and if ∆ ′′ is not already present in B (because already obtained using another symmetry, for example) then ∆ ′′ is added to Γ . If a fixed point has to be reached (updateQueue set to true), ∆ ′′ is added to Q in order to keep computing symmetrical nogoods from ∆ ′′ in a next step. Notice that ∆ ′ is necessarily admissible when Ψ only contains variable symmetries.

To illustrate symmetry-reinforced nogood recording from restarts, let us consider the 4-queens instance, and suppose that Ψ only contains the variable symmetry f h . Figure 3 depicts the search tree built by FC (Forward Checking : a backtrack search algorithm maintaining a partial form of arc consistency at each node) after three decisions. Suppose that after the current decisions x a = 1 and x b = 2, the current run is stopped (due to the restart strategy). One can extract a nld-subsequence from the current branch :

x a = 1, x b = 2 and derive a nld- nogood ∆ : {x a = 1, x b = 2}. When f h is applied on ∆, the symmetrical nogood ∆ ′ = {x d = 1, x c = 2}
is obtained (after swapping x a with x d and x b with x c ). Suppose now that Ψ contains a second symmetry f i . This means that f h and f i can be composed to generate more symmetrical nogoods (if updateQueue is set to true). For example, one can compute:

(∆) f h , (∆) f i , ((∆) f i ) f h , ((∆) f h ) f i , . . .
until a fixed point is reached because no new symmetrical nogood can be generated.

x a = 1

x b = 2 nld-subsequence : x a = 1, x b = 2 nld-nogood : ∆ = {x a = 1, x b = 2} ∆ ′ = (∆) f h = {x d = 1, x c = 2} f h = {(x a , x d ), (x b , x c )} x a = 1 x b = 2 ⊥ ⊥ x b = 2
Restart Fig. 3. Simple illustration of symmetry-reinforced nogood recording from restarts.

Classically, computing compositions of generators is not performed due to space and time explosion. Above, we have proposed to revisit indirectly compositions (when updateQueue is set to true) by iteratively computing symmetrical nogoods until a fixed point is reached. In our context, as the number of extracted nld-nogoods after each run is quite reasonable (polynomial wrt the number of variables and the greatest domain size), one can expect that the overhead will not be prohibitive.

To show the practical value of symmetry-reinforced nogood recording from restarts, we have conducted an experimentation using a cluster of Xeon 3.0GHz with 1 GB of RAM under Linux. We have measured performance in terms of CPU time (in seconds) and the number of visited nodes. We have tested MAC (the backtrack search algorithm that maintains generalized arc consistency during search) with three variants of (symmetry-reinforced) nogood recording from restarts. The first variant, denoted by NG, is the classical nogood recording from restarts technique. The second variant, denoted by NG+Sym 1 , is the technique of symmetry-reinforced nogood recording from restarts, Algorithm 1, when the Boolean updateQueue is set to f alse. That means that when a run is stopped, NG+Sym 1 exactly computes a single symmetrical nogood for each extracted nldnogood and for each symmetry in Ψ . The third variant, denoted by NG+Sym * , is the technique of symmetry-reinforced nogood recording from restarts, Algorithm 1, when the Boolean updateQueue is set to true. That means that all possible symmetrical nogoods are computed from extracted nld-nogoods and symmetries in Ψ (i.e., the process is run until a fixed point is reached). We have also tested different variable ordering heuristics, namely dom/ddeg and dom/wdeg [START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF], and the time-out has been set to 20 minutes per instance. Finally, note that we have employed a geometric restart policy in which the number of backtracks is increased by a factor 1.5. To identify automatically symmetries, we have used the lightweight detection technique of variable symmetries presented in [START_REF] Lecoutre | Lightweight detection of variable symmetries for constraint satisfaction[END_REF]. For each instance, the generators (of the symmetry group) returned by Saucy [START_REF] Darga | Exploiting structure in symmetry generation for CNF[END_REF] have been collected and recorded in the set Ψ . Note that the time spent by Saucy to compute these generators is quite negligible.

Instance

We have tested the three variants of MAC on 2, 657 instances coming from www.cril.fr/ ~lecoutre/benchmarks.html after having selected all problems that contain variable symmetries (and that can be identified by our automatic lightweight detection technique). Table 1 provides an overview of the results in terms of the number of solved instances within the time limit. The average CPU time is computed from instances solved by the three methods. Note that the number of instances solved by the three methods is given into round brackets. Whatever variable ordering heuristic is used, the number of solved instances increases when symmetry-reinforced nogood recording is used. Also, the variant NG+Sym * outperforms NG+Sym 1 both in terms of solved instances and CPU time. It is interesting to note that there is no significant overhead when NG+Sym * is used (in other words, this is not really penalizing to compute indirectly "composition" of symmetries). This is due to the fact that the number of extracted nld-nogoods is limited and a fixed point can be reached quickly in practice.

Instance

Table 2 focuses on some illustrative instances when the heuristic dom/wdeg is used. Clearly, for the hardest RLFAP instances, the symmetry-reinforced methods allow greater efficiency. For example, the two NG+Sym approaches solve the scen11-f1 instance while this instance remains unsolved by NG. The gap between NG+Sym 1 and NG+Sym * is less significant on some other series such as series. On well-known symmetrical problems such as haystack or pigeons (modeled as a clique of binary difference constraints), NG+Sym * outperforms (unsurprisingly) the other variants.

Finally, Figure 4 represents scatter plots displaying pairwise comparisons for NG, NG+Sym 1 and NG+Sym * when the heuristics dom/ddeg (subfigures on the left) and dom/wdeg (subfigures on the right) are used. Note the presence of many dots located under the diagonal line of subfigures 4(c) and 4(d), which represent instances solved quicker by the methods whose name labels the y-axis. Clearly, NG+Sym 1 and NG+Sym * outperform NG. When NG+Sym 1 and NG+Sym * are compared, it appears that NG+Sym * is slightly better.

Conclusion

In this paper, we have introduced the principle of symmetry-reinforced nogood recording from restarts. An original method is NG+Sym * that allows us to benefit indirectly from the composition of symmetries by iteratively computing symmetrical nogoods (until a fixed point is reached). It is worthwhile to recall that classically, only a small set of symmetries is used in practice (e.g., the generators of a symmetry group identified by a graph automorphism software), and no composition is computed. As a first perspective, we would like to study the practical interest of NG+Sym * with other kinds of symmetries such as value symmetries and variable-value symmetries. A second perspective is to compare our approach with classical symmetry-breaking methods.

Fig. 1 .

 1 Fig. 1. A partial search tree built by a backtrack search algorithm.

Fig. 2 .

 2 Fig. 2. The two solutions of the 4-queens instance.

Algorithm 1 : 1 positiveDecisions ← ∅ 2 for i ranging from 1 to m do 3 if δi is a positive decision then 4 positiveDecisions ← positiveDecisions ∪ {δi} 5 else 6 ∆ ← positiveDecisions ∪ {¬δi} 7 Γ

 11234567 extractNogoods(Σ: sequence of decisions): set of nogoodsInput: Σ = δ1, . . . , δm Output: a set Γ of nogoods, computed from Σ Γ ← ∅ ← Γ ∪ {∆} ∪ computeSymmetricN ogoodsOf (∆)

Fig. 4 .

 4 Fig. 4. Pairwise comparisons (cpu time) on a benchmark composed of 2, 657 instances.

Table 1 .

 1 Number of solved instances and average cpu time on a benchmark composed of 2, 657 instances, given 20 minutes.

			NG	NG+Sym 1	NG+Sym *
	dom/ddeg	#solved	1, 604	1, 610	1,618
		cpu (1, 602)	39.4	36.1	35.2
	dom/wdeg	#solved	1, 893	1, 898	1,909
		cpu (1, 889)	37.1	32.1	31.4

Table 2 .

 2 Illustrative results obtained on some problem instances.

			NG	NG+Sym 1	NG+Sym *
	2-insertions-3-3 cpu	4.36	2.33	1.25
	#gen=2	nodes	48, 975	20, 238	7, 375
	3-insertions-3-3 cpu	387	231	66.9
	#gen=2	nodes	5, 744K	3, 191K	929K
	3-insertions-4-3 cpu	844	507	124
	#gen=2	nodes	10M	5, 913K	1, 397K
	fpga-10-10	cpu	908	197	196
	#gen=26	nodes	5, 788K	1, 251K	1, 251K
	fpga-10-9	cpu	151	255	262
	#gen=23	nodes	1, 187K	2, 075K	2, 075K
	fpga-12-10	cpu	time-out	736	738
	#gen=28	nodes	-	4, 751K	4, 751K
	graceful-K4-P2 cpu	1.13	0.91	1.37
	#gen=4	nodes	1, 924	708	503
	graceful-K5-P2 cpu	599	630	150
	#gen=4	nodes	2, 566K	2, 573K	526K
	haystacks-04 cpu	0.48	0.38	0.48
	#gen=8	nodes	328	149	114
	haystacks-05 cpu	24.5	6.99	0.89
	#gen=15	nodes	305K	74, 951	2, 451
	haystacks-06 cpu	time-out	time-out	869
	#gen=24	nodes	-	-	10M
	pigeons-10	cpu	33.2	13.6	1.78
	#gen=9	nodes	456K	168K	10, 018
	pigeons-11	cpu	348	131	11.2
	#gen=10	nodes	4, 641K	1, 716K	125K
	pigeons-12	cpu	time-out	time-out	190
	#gen=11	nodes	-	-	1, 731K
	scen11-f1	cpu	time-out	951	634
	#gen=38	nodes	-	5, 728K	3, 729K
	scen11-f2	cpu	708	332	243
	#gen=38	nodes	4, 154K	2, 010K	1, 352K
	scen11-f3	cpu	207	103	63.0
	#gen=38	nodes	1, 269K	597K	353K
	series-14	cpu	63.4	20.0	21.5
	#gen=1	nodes	424K	130K	130K
	series-15	cpu	199	73.9	78.6
	#gen=1	nodes	1, 210K	461K	461K
	series-16	cpu	time-out	432	428
	#gen=1	nodes	-	2, 696K	2, 696K
	val17-42	cpu	753	193	57.3
	#gen=2	nodes	1, 944K	473K	134K
	val18-42	cpu	118	69.0	12.9
	#gen=4	nodes	247K	139K	20, 745
	val18-44	cpu	75.0	75.1	74.7
	#gen=4	nodes	371K	371K	371K


É Grégoire
email: gregoire@cril.fr

J.-M Lagniez
email: jmlagniez@gmail.com

B Mazure
email: mazure@cril.fr

A data structure boosting the performance of local search for CSP solving

This paper is concerned with local search techniques (LS) for solving CSPs (Constraint Satisfaction Problems). An efficient data structure is presented that allows the performance of LS to be boosted. Experimentations on benchmarks from the last international CSP competitions illustrate its very positive impact. It has been implemented in wcsp δ : an efficient open-ended and open-source local search platform for CSP that can accommodate various meta-heuristics.

CSPs

Let us recall what a (discrete) CSP (Constraint Satisfaction Problem) is. A CSP is pair (V, C) where 1. V is a finite set of n variables s.t. each variable x ∈ V has an associated finite instantiation domain, denoted dom(x), which contains the set of values allowed for x, 2. C is a set of constraints s.t. each constraint c ∈ C involves a subset of variables of V, called scope and denoted vars(c), and has an associated relation rel(c), which contains the set of tuples allowed for the variables of its scope.

Solving a CSP P = (V, C) consists in checking whether P admits at least one solution, i.e. an assignment of values for all variables of V s.t. all constraints of C are met. When P admits at least one solution, P is said to be satisfiable, otherwise P is said unsatisfiable. This decision problem is naturally generalized into an optimization one, called MAX-CSP, which consists in searching for one largest possible subset of constraints that can be satisfied at the same time.

Local search for CSP: an enhanced data structure

The use of LS for CSP solving has been the subject of many studies these last decades [START_REF] Minton | Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method[END_REF][START_REF] Galinier | A general approach for constraint solving by local search[END_REF][START_REF] Hentenryck | Constraint-Based Local Search[END_REF]. It is well-known that smart data structures can play a key role in the performance of the various possible LS algorithms. In this specific context, we considered the data structure first proposed in [START_REF] Galinier | A general approach for constraint solving by local search[END_REF], which is now quite standard in LS for CSPs. The key idea of the structure is to record, for each constraint c, for each possible value val of each variable v occurring in c, the corresponding number of unsatisfied constraints to which the variable v would belong if the next move from the current interpretation consists in adopting the value val for the variable v. Indeed, as most moves will involve adopting the value of a variable that would decrease the number of falsified constraints, such a recorded information allows this selection to be made efficiently. Moreover, updating the data structure only concerns the constraints affected by this last move. Accordingly, this data structure allows many repetitive checks and computations to be avoided during the successive iterative steps of LS.

Although this data structure records information about the impact that the change of value of a variable entails, it does not record whether or not the constraints containing the variables would see their satisfiability status affected by this change, although this is already computed. Accordingly, we enhanced the data structure by recording for each value val for each variable in each constraint c, whether a move to this value val would allow the constraint c to be satisfied or not. Interestingly, this information can be computed and recorded in constant additional time while initializing and updating the data structure of [START_REF] Galinier | A general approach for constraint solving by local search[END_REF]. Moreover, this simplifies the updating process of the initial data structure since the satisfiability status of a constraint does not have to be computed but is simply consulted in the enhanced data structure.

Experimentations

Not surprisingly, this enhancement of the data structures has a very positive impact on the LS performance. It has been experimented extensively on all benchmarks from the CSP'2008 international competition (on Intel Xeon 3.2. GHZ 2G RAM under Linux 2.6) through wcsp δ , which is our generic, open-ended and open-source LS platform for CSP. As a case study, we considered the seminal WalkSAT [START_REF] Selman | Noise strategies for improving local search[END_REF] LS algorithm and its variants involving the Novelty and RNovelty [START_REF] Mcallester | Evidence for invariants in local search[END_REF] paradigms. Table 1 shows that adopting the enhanced data structure allowed more instances to be solved within a preset 1200 seconds CPU time limit. Figure 1 also show the very positive impact of the enhanced data structure on the required CPU time to solve instances (x-axes and y-axes give computing time for each instance, with or without the enhancement of the data structure, respectively). The performance of wcsp δ has also been demonstrated as a building block of an hybrid CSP solver based on this LS platform [START_REF] Grégoire | A CSP solver focusing on FAC variables[END_REF].

Fig. 1 .

 1 Scatter plot comparing the runtimes of wcsps (x-axis) and wcsp δ (y-axis).

Table 1 .

 1 Comparaison between wcsp δ and wcsps.

		2-EXT	2-INT	N-EXT	N-INT
	Method	sat uns tot sat uns tot sat uns tot sat uns tot
	wcsps(WalkSat) 239 0	239 160 0	160 179 0	179 271 0	271
	wcsp δ (WalkSat) 248 0 248 167 0 167 181 0 181 283 0 283
	wcsps(novelty) 308 0	308 159 0	159 222 0	222 338 0	338
	wcsp δ (novelty) 315 0 315 165 0 165 223 0 223 350 0 350
	wcsps(rnovelty) 319 0	319 161 0	161 208 0	208 321 0	321
	wcsp δ (rnovelty) 325 0 325 173 0 173 209 0 209 325 0 325