Decomposition of the Factor Encoding for CSPs

1 Introduction

In order to solve a constraint satisfaction problem (CSP), local consistencies are commonly used to filter out inconsistent parts of the constraint network to reduce the search space during the solving process. Generalized arc consistency (GAC) is usually the local consistency of choice. With so many algorithms having been developed, GAC is invariably implemented in most solvers in one form or another. Stronger consistencies can further reduce the search space and may be more appropriate for hard problems, but implementing such algorithms to be competitive with the state-ofthe-art solvers employing GAC may be a challenge. They have been the subject of recent works [Bessi`ere et al., 2008; Karakashian et al., 2010; Schneider et al., 2014; Paparrizou and Stergiou, 2012; Lecoutre et al., 2013], which propose propagation algorithms for higher-order consistencies such as relational consistency, max-restricted pairwise consistency, and full pairwise consistency (FPWC). Some of the new algorithms are based on well-established GAC algorithms, e.g. the Simple Tabular Reduction algorithm [Ullmann, 2007;

Lecoutre, 2011] was extended to cover FPWC in [Lecoutre et al., 2013].

Due to the practical challenges in implementing higherorder consistency algorithms, an alternative approach for some higher consistencies is to convert a CSP into another CSP and apply existing GAC propagators on the result, so that it is equivalent to enforcing the stronger consistencies on the original CSP. The k-interleaved encoding (kIL) [Mairy et al., 2014] is one such approach. Enforcing GAC on the kIL is the same as enforcing k-wise consistency on the original problem. A recent transformation is the factor encoding (FE) [Likitvivatanavong et al., 2014], which extracts commonly shared variables between pairs of constraints and forms new variables called factor variables. The factor variables are then augmented to the original constraints. Similar to the kIL, enforcing GAC on the FE is the same as enforcing FPWC on the original problem. However, although the results for the FE transformation [Likitvivatanavong et al., 2014] show that the FE provides an efficient way of achieving FPWC, many new factor variables can be added which can substantially increase the total size of the transformed constraints and increase runtime overheads.

In this paper, we address this shortcoming of the FE and propose a new encoding based on the FE. The idea is to decompose constraints such that factor variables and their corresponding original variables are taken out to form new constraints. We show that this new variant preserves the main property of the FE. We then perform an experimental study on the FE and this new transformation using multiple search heuristics. We show that the transformations can benefit dynamic search heuristics, e.g. dom/ddeg and dom/wdeg, due to the change in constraint networks. This new encoding is competitive with the FE on majority of problem instances and can reduce the search space and speed up the solving on some structured problems by several orders of magnitude.

2 Preliminaries

A constraint network P is a pair (X, C) where X is a set of n variables {x1, . . . , xn} and C a set of e constraints {c1, . . . , ce}. D(x) is the domain of x ∈ X. We use (x, a) to denote the value a ∈ D(x) (or simply a when the context is clear). Each c ∈ C involves two components: a scope (scp(c)) which is an ordered subset of variables of X; and a relation over the scope (rel(c)). Given scp(c) =

{xi1 , . . . , xir }, rel(c) ⊆ ∏rj=1 D(xij ) represents the set of satisfying combinations of values for the variables in scp(c). We may also refer to c by c(xi1 , . . . , xir ). The dual graph of P is a graph in which vertices represent the constraints and edges connect two vertices whose constraints' scopes overlap. The arity of c is |scp(c)|. Given an ordered set S ⊆ scp(c) and τ ∈ rel(c), the projection of τ on S (τ[S]) is the tuple consisting of only the components of τ that correspond to the variables in S. A tuple τ = (aii , . . . , aik ) where aij ∈ D(xij ) is said to be a tuple over {xi1 , . . . , xik }. When elements in rel(c) are given explicitly, c is called a (positive) table constraint. A tuple τ ∈ rel(c) is valid iff τ[x] ∈ D(x) for each x ∈ scp(c). Otherwise τ is invalid. A tuple τ ∈ rel(c) is a support of (x, a) in c iff τ [x] = a.

Definition 1 (GAC) A value (x, a) is generalized arcconsistent (GAC) [Dechter, 2003] iff for any constraint c involving x, there exists at least one valid support τ for (x, a) in c. A variable x is GAC iff (x, a) is GAC for each a ∈ D(x). A CSP P is GAC iff all variables are GAC.

A solution to P is a valid tuple over X such that every constraint is satisfied. P is satisfiable iff a solution exists.

A compound variable X is a cross-product composition from {xi1 , . . . , xim } ⊆ X, called X's signature (σ(X)), where D(X) ⊆ ∏mj=1 D(xij ) and its values are referred to as compound values. Given a constraint c and an ordered set S = {xi1 , . . . , xim } ⊆ scp(c), we denote λc(S) to be the compound variable on S with respect to c whose domain D(λc(S)) is {τ[S] | τ ∈ rel(c)}. It follows that σ(λc(S)) = S. Note that compound variables and compound values are logical concepts. In practice, they are represented by the standard notion of variables and values (Example 2 will clarify this point.) We may drop the subscript and write λ(S) if there is no ambiguity. Non-compound variables are called ordinary variables. For uniformity, σ is defined for all variables, i.e. σ(x) = {x} for an ordinary variable x.

Definition 2 (maxRPWC) A value (x, a) is max-restricted pairwise consistent (maxRPWC) [Bessi`ere et al., 2008] iff for all ci ∈ C where x ∈ scp(ci), (x, a) has a valid support τi in rel(ci) such that for any other cj ∈ C there exists a valid tuple τj ∈ rel(cj ) and τi[scp(ci)∩scp(cj )] = τj [scp(ci)∩scp(cj )]. A CSP P is maxRPWC iff all values are maxRPWC.

Definition 3 (PWC) A CSP P = (X, C) is pairwise consistent (PWC) [Janssen et al., 1989] iff for any constraint ci and any valid tuple τi ∈ rel(ci), for any other constraint cj, there exists at least one valid tuple τj ∈ rel(cj) such that τi[scp(ci) ∩ scp(cj )] = τj [scp(ci) ∩ scp(cj )].

Definition 4 (FPWC) A CSP P is full pairwise consistency (FPWC) [Lecoutre et al., 2013] iff it is GAC and PWC.

FPWC is also equivalent to PWC together with maxRPWC. The following example illustrates the filtering power of GAC and FPWC.

Example 1 Consider the CSP P = (X, C) in Fig. 1(a), where X = {x, y, u, v, w}, D(x) = D(y) = {0, 1}, D(u) = D(v) = D(w) = {0}, and C = {c1, c2, c3}. It is trivial to check that P is GAC. Let us consider FPWC. Only the first tuple of each constraint can be extended to other constraints.

The second and the third tuples of each constraint are thus inconsistent with respect to FPWC. As a result (x, 1) and (y, 1) are no longer FPWC and can be pruned from D(x) and D(y).

3 The factor encoding

The factor encoding (FE) [Likitvivatanavong et al., 2014] converts a constraint network P into another network P ∗ such that enforcing GAC on P ∗ is equivalent to enforcing FPWC on P. This section provides background on the FE.

Given P= (X, C) the factor encoding (FE) of P is the network P ∗ = (X ∪W∗ , C ∗ ) where,

W∗ = {λ(S) | D(λ(S)) = ⋃k D(λck (S)) for all k such that λck (S) ∈W}, and

and for each c∗i ∈ C ∗ , 1 ≤ i ≤ e,

• scp(c∗i ) = scp(ci)∪{λ(S) | λ(S) ∈ W∗ ∧S ⊆ scp(ci)}
• for any τ ∈ rel(ci), let ext(c∗i , τ) be a tuple extended from τ such that

• for any λ(S) ∈ scp(c∗i ), ext(c∗i , τ)[λ(S)] = ext(c∗i , τ )[S](= τ [S])

then, rel(c∗i ) = {ext(c∗i , τ) | τ ∈ rel(ci)}.

We call the compound variables in W∗ factor variables. P ∗ is also referred to as fe(P). A pair of constraints is factorable if it generates a factor variable in the FE; a constraint network is factorable if it contains at least one such pair.

Example 2 Consider P in Example 1. Fig. 1(b) shows fe(P), which involves a factor variable f where σ(f) = {x, y} and D(f) = {(0, 0), (0, 1), (1, 1), (1, 0)}. For simplicity, D(f) is normalized to {0, 1, 2, 3}.

The factor encoding employs auxiliary variables to represent the intersection between constraints. These additional variables are then grafted onto the constraints where they originate from. The FE, therefore, achieves higher-order consistency at a cost of enlarged tables.

Theorem 1 ([Likitvivatanavong et al., 2014]) fe(P) is GAC if and only if P is FPWC.

Consider fe(P) in Fig. 1(b) for example. Enforcing GAC on fe(P) reduces D(f) to {0}. This makes the second and the third tuples of c∗1 , c∗2 , and c∗3 invalid and leaves (x, 1) and (y, 1) with no valid support. The effect is the same as enforcing FPWC on P.

cf

4 Factor-decomposition encoding

In this paper, we propose a new encoding that addresses the FE's disadvantage. It is basically a variation of the FE and the idea behind it is to compress the FE by extracting factor variables and their signatures to form new constraints. The goal is to reduce the arity of the factor-encoded constraints in the FE where constraint arity can be much larger than the original arity. Specifically, a constraint that is augmented with factor variables by the FE is decomposed into multiple smaller constraints. A new constraint is created for each factor variable such that the scope includes the factor variable itself and the variables in its signature. The original constraint is then modified so that any ordinary variable that is a member of some factor variable's signature is removed. We call this new transformation factor-decomposition encoding (FDE).

We explain the process as follows. Given network P,

1. Construct fe(P)
2. (Decomposition) For each factor variable f ∈ scp(c∗ ),
3. (a) subtract σ(f) from scp(c∗ ).
4. (b) add a new constraint cf such that scp(cf) = {f} ∪ σ(f), and rel(cf) = {(t, ai1 , . . . , ai|σ(f)| ) | t ∈ D(f) ∧ t = (ai1 , . . . , ai|σ(f)| )}.

The resulting constraint network is denoted by fde(P).

Example 3 Given P in Example 1, fde(P) in shown in Fig. 2. Constraints c1, c2, c3 in P are reduced to binary constraints c′1 , c′2 , c′3 due to the removal of {x, y}. A new constraint cf (f, x, y) that maintains the connection between f and x, y is introduced. Note that the table relations of fde(P) (30 cells) are smaller than those of fe(P) (36 cells).

Sketch of Proof: Given variable x ∈ scp(c) removed by step 2(a), we will show that the FDE keeps the restriction between c and any other constraint c′ in the FE whose scope includes x. There are three cases.

1. x ∈ σ(f) where f is a factor variable such that f ∈ scp(c) ∩ scp(c′ ). The new constraint cf added in step 2(b) produces a cycle c-c′-cf in the dual graph that maintains the effect of x between the pair (c, c′ ).
2. x ∈ σ(f) for some factor variable f ∈ scp(c) and there exists no factor variable f ′ ∈ scp(c′ ) such that x ∈ σ(f ′ ). The connection between c and c′ in the original dual graph is provided by x. Removing x does not take away this connection since it is replaced by the connection between c and cf (through f) and between cf and c′ (through x).

(3) x ∈ σ(f) ∩ σ(f ′ ) where f and f ′ are factor variables such that f ∈ scp(c) and f ′ ∈ scp(c′ ). Step 2(b) ensures that Figure 3: The dual graph of a network P (left), fde(P) (middle), and fde(fde(P)) (right), where f1 = xyu, f2 = xyz, f3 = xyw, and f4 = xy.

there are constraints cf and cf ′ such that scp(cf) ⊇ {f, x} and scp(cf ′ ) ⊇ {f ′ , x}. That means although x is removed, the effect of x on the pair (c, c′ ) is replicated through the path (c, cf ), (cf , cf ′ ), (cf ′ , c′ ) in the dual graph. ✷

The FDE retains the main property of the FE (Theorem 1 [Likitvivatanavong et al., 2014]). We have the following corollary.

The FDE keeps all ordinary variables but remove some columns from original table relations. In extreme cases, original non-binary constraints are turned into binary constraints. These happen when variables in the original constraint are replaced with two factor variables, or when there is one ordinary and one factor variable. Note that although the new constraint created by step 2(b) cannot have larger arity than the original pair that produces the factor variable, it is possible for a group of large-arity constraints to generate a large number of new constraints with only slightly smaller arity, so that on the whole, the average arity increases.

Proposition 1 Compared to fe(P), the average constraint arity may increase in fde(P).

Although the average arity may increase, we expect the FDE to reduce average arity. This is borne out in the experiments which show that the average constraint arity is reduced in practice. Also the maximum constraint arity of the FDE and the original CSP is always smaller than that of the FE. Since the speed of various GAC algorithms and implementations can depend strongly on the arity, the FDE can be faster than the FE in many cases (experiments in Section 5 show that the arity reduction allows special purpose binary AC algorithms to replace GAC).

We remark that fde(P) may still be factorable even though it includes the FE as part of the process. While it is true that step 1 and 2(a) replace shared variables with factor variables, only the original constraints are affected. For this reason, only the scopes of the original constraints are guaranteed to intersect on fewer than two variables. The new constraints created in step 2(b), however, may contain a factorable pair. In this case, we can re-apply the FDE possibly multiple times until there are no more factorable pairs, a fixpoint.

Example 4 Fig. 3 shows an example of fde(fde(P)). The diagram on the left is the dual graph for some constraint network P, the middle shows the dual graph for one application of the FDE, and the right shows two successive applications of the FDE, reaching a fixpoint afterward.

The number of times for the FDE to reach a fixpoint is dependent on the network. An example of a network that needs arbitrary applications of the FDE to reach a fixpoint follows.

Example 5 We will construct a network Pi such that it takes i applications of the FDE to reach a fixpoint. A recursive definition of Pi is given as follows. P0 = ({x, y}, {c(x, y)}) (P0 has a single constraint involving two variables). Given Pi=(Xi, Ci) with Ci = {c1, . . . , cm}, then Pi+1 := (Xi+1, Ci+1) where Ci+1 = {cj,k | 1 ≤ j ≤ m ∧ 1 ≤ k ≤ 2 ∧ scp(cj,k) = scp(cj ) ∪ {zij,k }} and Xi+1 = Xi ∪ {zij,k | 1 ≤ j ≤ m ∧ 1 ≤ k ≤ 2}.

Proposition 2 Let fdek (P) denote fde(fde(. . . fde(P) . . .)) (the FDE is applied k times in a row). An upperbound of k is max {|σ(f)| -1 | f is a factor variable of fe(P)}

Applying the FDE more than once may affect the structure of the network in a positive way since more redundancy is eliminated. In contrast, applying the FE more than once is pointless since it only increases arity and redundancy. Moreover, similar to the FE, multiple applications of the FDE does not affect the level consistency when GAC is enforced.

In the fixpoint of the FDE, no two constraints share more than one variable. The same cannot be said for the FE or fdek which has not reached fixpoint.

Proposition 3 fdek (P) is GAC iff fde(P) is GAC.

Corollary 2 fdek (P) is GAC iff P is FPWC.

5 Experiments

We present extensive experiments that evaluate the new FDE encoding compared with the FE and the original network. All extensional benchmarks from the CSP solver competition 1 that are non-binary and factorable are used. We also convert some intensional structure benchmarks to extensional. In total, we use 633 problem instances from 22 problem series. However, only some instances allow fdek for k > 1 (of all structured problems tested, only fpga and ii-8 do). With insufficient benchmarks, experiments involve only one-pass FDE. The experiments were run on a 3.20GHz Intel i7-960 with 64bit Linux. The converters take an input in the XCSP format and output the result as another text file, also in XCSP. For the FDE, the converter generates the encoding directly (the description of the FDE process in Section 4 in which the FE is generated as a first step is only an exposition). We used AbsCon [Merchez et al., 2001] as the solver 2 where the default GAC algorithm is STR2 [Lecoutre, 2011] and the default arc consistency algorithm is the bitwise AC3 algorithm [Lecoutre and Vion, 2008]. CPU time is limited to 1800 seconds while memory is limited to 8GB.

1 Available at http://www.cril.univ-artois.fr/CSC09. We exclude the bdd benchmarks which have very large extensional tables. With the FE and the FDE, the tables are larger than 1GB which is too big to solve with AbsCon.

2 We focus on encodings and their relative effectiveness in the experiments. The choice of solver is less important as long as it is valid and robust. We chose AbsCon for its versatility as a blackbox solver: many algorithms and heuristics are implemented and selectable. Compared to another solver such as Mistral, AbsCon handles large tables better, (e.g. AbsCon is 20X faster than Mistral on average to solve dagrand (arity=15, 150000 tuples/table), so it is suitable for testing the FE which increases arities. We used the latest version AbsCon1.41 (not publicly available).

The encodings alter the problem's structure in a way that may lead variable ordering heuristics to choose variables differently compared with the original problem. Thus, even though the consistency level is the same, the number of nodes visited could be different. For the FE, new variables are added to the network as well as constraint scopes, increasing constraint arity in the process. For the FDE, although the set of variables is the same as the FE's the topology of the network is affected even more profoundly given that variables are extracted from one constraint to form an entirely new constraint. Because structural features of a network are often taken into account in search heuristics, the same heuristic could possibly pick different variables for the original CSP, the FE and the FDE. In order to test the performance of these encodings realistically, it would be better to let the heuristics choose freely rather than foisting the same ordering on all of them. 3 For this reason, we employed four well-known and commonly used variable selection heuristics in our experiments, dom/ddeg, dom/wdeg [Boussemart et al., 2004], impact [Refalo, 2004], activity [Michel and Hentenryck, 2012], and test them on the original problem as well as the FE and the FDE encodings. We used lex value ordering in all cases.

Table 1 shows the mean results on unstructured problems, calculated from instances that are solved within the time limit by all the combinations of three constraint networks (one original and two encodings) and four heuristics. The first column displays the name of the benchmarks while the number below indicates the number of instances. The second column denotes the encodings, where "-" indicates no encoding (original P). The third column gives the mean constraint arity. The next four columns (eight sub-columns) display the mean number of nodes visited 4 during search and the mean CPU time (in seconds) for the four heuristics (unless too many instances are not solved within the time limit, in which case, the number of time-out instances is reported instead). Encoding times for the FE and the FDE are not included in the CPU time and are not reported in the table due to space restriction (we remark that for over 80% of all problem instances, the conversion time is negligible compared to the solving time, taking only a fraction of a second to generate the XCSP XML). Numbers in bold indicate best results. Graphs in Fig. 4 (in color) show overall performance of different techniques when all random problem instances are taken into account. Each point (x, y) indicates that the corresponding technique is able to solve y instances within x seconds (note that x represents the runtime of each of the y instances, not the total runtime of all y instances).

The FDE shows significant improvement in runtime across all heuristics for most of the series rand-3-*. The main reason for the good performance is that the FDE converts most ternary constraints into binary, so a GAC algorithm is not needed and AbsCon employs a bitwise-based AC [Lecoutre and Vion, 2008]. For the FDE of rand-3-20-20, on average 73.9% of original ternary constraints are transformed into binary where most have two factor variables; the FDE of rand3-20-20 has 41.6% binary constraints and 58.4% ternary constraints on average, which results in 46% runtime savings. For dagrand and rand-10-20-10, FPWC proves the problems unsatisfiable without search and that is why there is little difference across heuristics within the same encoding. Runtimes are dominated by GAC processing which depends on table size. Tables in the FDE can be larger than those in the FE, as is the case with dagrand and rand-10-20-10. For dagrand, there are 120 factor variables compared to 23 ordinary variables, which translates to 120 extra tables for the FDE. Overall, the graphs in Fig. 4 show that the FDE solves more problems within the specified time on all four heuristics.

3 Using the same ordering simply gives the same search space.

4 In AbsCon, instantiating a variable is counted as one search node even if there is only a single value in the domain.

Table 2 shows the mean results for structured problems. Again, the conversion times for the FE and FDE are negligible for almost all instances and so are not reported for space reason. As there are fewer structured benchmarks in extensional form, we have added some structured benchmarks which are given in intensional form in the CSP solver competition benchmarks (separated by double line in the table). The series fpga, allInterval, Schur's lemma, jnh, Chessboard coloration, ii-8, and socialGolfers are converted 5 from intensional to extensional constraints. Graphs in Fig. 5 show overall performance of different techniques when all structured problem instances are taken into account.

From the graphs, the FDE shows significant improvement for dom/ddeg and dom/wdeg, some improvement for impact, and on par with the FE for activity. In particular, the FDE provides huge speedup for dom/ddeg and dom/wdeg on allInterval and fpga. At the same time, it has an adverse effect on ii-8. Detailed results for fpga are shown 6 in Table 3.

5 We focus on studying the FE on extensional constraints but also tested the intensional benchmarks on AbsCon. Interestingly, we found that table constraints with the FE variants can be faster than intensional, e.g. allinterval can be 60% faster.

One of the reasons for the striking results on allInterval and fpga can be attributed to scope reduction by the FDE. For allInterval, the original problems contain only binary and ternary constraints. The FDE converts all original ternary constraints into binary. The reduction in fpga is even more notable. Take fpga-12-12 for example. In this instance there are 180 constraints of arity 6, 7, and 12 - all in the same proportion. The FDE of this instance has 192 constraints in which 144 are binary. By contrast, the poor performance of dom/ddeg and dom/wdeg on the FDE of ii-8 appears to be idiosyncratic. We found that choosing variables randomly instead always brings down the runtime to the same level as the FE's on the ii-8 instances. We also tried random heuristic on the allInterval and fpga series but improvement is limited.

The FDE works well on unstructured benchmarks which are generally harder, solving more than the FE and untransformed CSPs. For structured problems, running impact on the original CSPs is the best (213 instances solved), followed by impact on the FDE (211). However, structured benchmarks have many easy instances. Altogether, dom/wdeg on the FDE

6 Conversion costs are given in this table. The converter is external to the solver and reads and writes XCSP XML files, so there are I/O costs for large files when the tables are large.

solves the most number of instances (445).

6 Related work

Transformation of one CSP to another is well studied. The early and most well-known work is the transformation of nonbinary constraints to binary, which includes the dual and the hidden encoding [Bacchus et al., 2002; Samaras and Stergiou, 2005]. The k-interleaved encoding [Mairy et al., 2014] is another way to incorporate k-wise consistency into the network by adding extra k-ary constraints that are basically the index of all feasible combination of tuples. It was shown in [Likitvivatanavong et al., 2014] that the FE consistently outperforms the k-interleaved encoding when k is two. [Bessi`ere et al., 2008] gives an extensive coverage of filtering consistencies for non-binary constraints. Other works on consistency algorithms that are stronger than GAC are [Paparrizou and Stergiou, 2012] (maxRPWC) and [Lecoutre et al., 2013; Karakashian et al., 2010; Schneider et al., 2014; Woodward et al., 2014] (FPWC and k-wise consistency). The FE has proved to be faster than eSTR2 [Lecoutre et al., 2013], an algorithm that enforces FPWC. In [Woodward et al., 2014], an adaptive algorithm that is a compromise between GAC and FPWC was studied, its speed ranging between GAC's and FPWC's for the most part.

7 Conclusion

We have introduced a variation of the FE for non-binary constraint networks. Unlike the FE, which merely augments table constraints with factor variables, the FDE also takes further advantage of the factor variables by extracting and replacing original variables with new constraints. Experiments show that the FDE has an edge over the FE on random problems while it can vastly outperform the FE on structured problems with the dom/ddeg and dom/wdeg heuristics.

The focus on network transformation in the literature has been on concrete, theoretical properties associated with the transformation, e.g. transforming non-binary constraints to binary [Bacchus et al., 2002]. The FE encodes PWC while the FDE decomposition changes the network. These tangible properties are undoubtedly useful, but our experiments suggest that coming up with transformations that can influence variable heuristics down the right path can have a greater effect. Such transformations may not have any identifiable property associated with them, as their sole function is to steer variable heuristics by exposing some hidden features of the network, and would be designed together with the heuristic to be used. The FDE provides a glimpse in this direction.

Acknowledgments

We thank Christophe Lecoutre for the permission to use AbsCon in our experiment. This work has been supported by grant MOE2012-T2-1-155.