1 Introduction

Constraint check plays a central role in arc consistency (AC)[16]. Maintaining arc consistency (MAC) [15, 18] is widely used to solve binary constraint satisfaction problems (CSP). In non-binary CSPs, AC is replaced by generalized arc consistency (GAC) [4]. An efficient MGAC algorithm usually has two features: (1) the GAC algorithm it uses is efficient, (2) it maintains few data structure during search. GAC algorithms can be classified into the coarse-grained and the fine-grained. The coarse-grained algorithms, such as AC3 and its improvements, are based on constraint-oriented propagation schemes. The latter [1, 3, 17] are based on value-oriented propagation schemes. The fine-grained algorithms usually maintain elaborate data structures during search, so the coarse-grained GAC algorithms are more efficient and more popular when being used in search. The original AC3 (GAC3) algorithm has the worst-case time complexity O(ed3) (O (er3dr+1)). By recording last supports, AC3.1 algorithm avoids some repeated constraint checks and it has an optimal worst-case time complexity O(ed2) [5], but MAC3.1 is inefficient due to its heavy data structure. MAC3.2 [9] explores multi-directional supports, but it still maintains heavy data structures during search. MAC3r algorithm [14] explores residue supports which are not maintained during search, so it costs less time than MAC3 and MAC3.1. Making use of multi-directional residues, AC3rm algorithm [10] improves AC3r. MAC3rm is efficient to solve CSPs, although its worst-case complexity is O(ed3). This is because MAC3rm also maintains few data structure during search. Exploring multiple residues, MAC3rm2 [11] is more efficient than MAC3rm. All the coarse-grained AC algorithms can be extended to GAC versions.

In some problems, we may face tight constraints, such as the constraint C10 in mknap-1-3 has a tightness higher than 0.99 and the weightedSum constraints in magicSquareFootnote 1 problems have tightness higher than 0.95. The GAC algorithms usually execute much more constraint checks to enforce GAC on these tight constraints than dealing with loose constraints. For example, the mknap-1-3 instance contains eleven 20-arity constraints and only one of them, C10, has tightness higher than 0.99, the tightnesses of the other constraints are between 0.25 and 0.47. We use MGAC3rm2 to solve mknap-1-3 and observe that the number of constraint checks executed on C10 is 1,067,710, whereas the total number on all the other constraints is 40,744. The result indicates that we should pay more attention to GAC algorithms for tight constraints, especially for those processed by a generic GAC algorithm. Although saving constraint checks does not always save time [20], it is important to save constraint checks in MGAC when constraint checks are relatively expensive. Some constraint checks are repeated in coarse-grained MGAC and [14] we identify two types of repeated constraint checks:

  • Positive repeat: a constraint check for a tuple τ on a constraint c is performed and it is allowed by c. Later in the search, τ is still valid and it is checked again. Such repeated constraint checks are called positive repeats.

  • Negative repeat: a constraint check for a tuple τ on a constraint c is performed and it is disallowed by c. Later in the search, τ is still valid and it is checked again. Such repeated constraint checks are called negative repeats.

In this paper, we propose a new generic GAC algorithm, called growing tabular reduction (GTR), which avoids all positive repeats and some of the negative repeats. It ensures that a tuple on a constraint c will never be checked again if it has been checked to be allowed by c. For each constraint c, it maintains a dynamic list recording the tuples that have been checked to be allowed by c. It first iterates over all active tuples in the list and checks their validities. A tuple is valid iff all the values in the tuple are present in the domains of the corresponding variables. If a tuple in the list is valid, all the values in this tuple have supports on c. Secondly, it uses constraint checks to seek supports for those values that have not found a support. If a new tuple is found to be allowed by c, it will be added into the list of c. There is extensive redundant work if we check all tuples in the list, so we propose a method to avoid redundant validity checks in maintaining GTR during search. An improved version, GTR2, is also introduced. The experimental results show that, compared with the classical coarse-grained MGAC algorithms, MGTR algorithms are not efficient on binary instances, but they save both constraint checks and cpu time on the non-binary instances with larger arity constraint that are tight.

This paper is organized as follows. Section 2 provides some technical background about CSP. The GTR algorithm and its improvement are introduced in Section 3. Section 4 presents the discussions and some related works. The experimental results and the analysis are in Section 5. Finally, conclusion and future work are in Section 6.

2 Background

A constraint satisfaction problem (CSP) P is a triple P = 〈X, D, C〉 where X is a set of n variables X = {x1, x2 ... xn}, D is a set of domains D = {dom(x1), dom(x2) ... dom(xn)} where dom(xi) is a finite set of possible values for variable xi, C is a set of e constraints C = {c1, c2 ... ce}. A constraint c consists of two parts, an ordered set of variables scp(c) = {xi1, xi2 ... xir} and a subset of the Cartesian product dom(xi1) × dom(xi2) × ... × dom(xir) that specifies the allowed (or disallowed) combinations of values for the variables {xi1, xi2 ... xir}. |scp(c)| is the arity of c. We use r to denote the arity of a constraint and d to denote the domain size of a variable. An element of dom(xi1) × dom(xi2) × ... × dom(xir) is called a tuple on scp(c), denoted by τ. τ[x] is the value of x in τ. The tightness of a constraint c is t/dr, where t is the number of disallowed tuples on scp(c) and dr is the number of all tuples on scp(c). Verifying if a given tuple is allowed by a constraint is called a constraint check and verifying if a given tuple is valid is called a validity check (x, a) denotes the value a for variable x.

Definition 1 (Generalized arc consistency 4)

Given a CSP P = 〈X, D, C〉, a constraint c ∈ C, and a variable x ∈ scp(c),

  • A value (x, a) is consistent with c iff there exists a valid tuple τ allowed by c and τ[x] = a. τ is called a support for (x, a) on c.

  • A constraint c is generalized arc consistent iff ∀x ∈ scp(c), dom(x) ≠ ∅ and ∀a ∈ dom(x), (x, a) is consistent with c.

  • P is generalized arc consistent iff all the constraints of C are generalized arc consistent.

To establish GAC on a constraint, GAC algorithms seek a support for every value (x, a) on the constraints involving x and remove those values without any support on these constraints. If the domain of a variable is empty, GAC fails. To seek a support for a value on a constraint, the GAC-valid scheme, iterating over valid tuples to find an allowed one, is a universal technique for all kinds of constraints. The MGAC algorithm, maintaining generalized arc consistency during backtracking search, is the most popular technique to solve hard CSPs. It builds up a search tree from level 0 to level n, where n is the number of variables. At each node of the search tree, a variable x and a value a in dom(x) are selected and a GAC algorithm is used to propagate the assignment. At level 0, GAC is usually enforced to preprocess the problem before searching starts. A dead-end is reached if the propagation fails, then a backtracking occurs.

The classical GAC3rm algorithm is recalled here. We present the constraint-oriented version of GAC3rm in algorithm 1 and algorithm 2. The changedVars stores all the variables in scp(c) whose domains are changed during current invocation of algorithm 2. The gacValues(x) records the values in dom(x), which have already found a support. Residue supports are used at line 6 in algorithm 2 and multi-directional residue is implemented at lines 14 to 16. The residue(x, a, c) is a residue support for (x, a) on c, which was found as the support for (x, a). If residue(x, a, c) is valid, (x , a) still has a support on c; otherwise, the findSupport procedure is called to find a new support for (x, a). findSupport iterates over all valid tuples involving (x, a) on c and check whether they are allowed by c. If an allowed one is found, it returns the tuple as the new support; otherwise, it returns NULL.

figure a
figure b

3 Growing tabular reduction: saving constraint checks during search

Before introducing the GTR algorithm, we give an example of positive repeats and negative repeats in MGAC3rm. Given a constraint c, x ∈ scp(c) and a ∈ dom(x), τ1, τ2, τ3, τ4, and τ5 are tuples involving (x, a) on scp(c), where τ3 and τ5 satisfy c. At the beginning, all the five tuples are valid. After checking τ1, τ2, and τ3, GAC3rm finds τ3 as the support for (x, a) and records it as the residue support. (x, a) has a support as long as τ3 is still valid. Later in the search, assuming τ3 loses its validity due to some assignment and τ1, τ2, τ4, and τ5 are still valid, so during the search for another support, τ1 and τ2 are checked again. These constraint checks on τ1 and τ2 are negative repeats. After searching, τ5 is found as a new support and it is recorded as new residue support for (x, a). The old residue support τ3 is discarded. Later in the search, a backtracking occurs, assuming τ5 loses its validity and τ3 becomes valid again. Now, GAC3rm will seek a new support for (x, a) because τ5 is no longer valid. It will check all valid tuples, so τ3 is checked again. This constraint check on τ3 is a positive repeat. Before this positive repeat on τ3, if τ1 and τ2 are still valid, then there are another two negative repeats. If we did not discard the old residue support τ3 when it became invalid and restore it after it becomes valid again, then this positive repeat will be avoided and the corresponding two negative repeats are also avoided.

In this section, we propose a new coarse-grained GAC algorithm avoiding all positive repeats, named growing tabular reduction (GTR). The GTR algorithm maintains a dynamic list of the tuples for each constraint c, which have been checked to be allowed by c. The algorithm contains two parts. In the first part, it iterates over all the recorded tuples in the list and check their validities. The values appearing in a valid one have supports on c. In the second part, it uses constraint checks to search for supports for only those values that have not found a support. This part is similar to what GAC3 does. If a new tuple is found as a new support of a value, it will be added into the dynamic list. Obviously, it may execute a great number of validity checks if we use this simple strategy during search. To solve this problem, we propose a method to avoid redundant validity checks. For each constraint, it records the tuples deleted at each level and restores them after a backtracking occurs. This method ensures that the tuples that have been verified to be invalid at level i will not be rechecked at level j (j > i). If a backtracking occurs, restoring tuples for each constraint can be done in constant time. In the following data structures, the tuples mean only the tuples that have been checked to satisfy constraint c, not all tuples satisfying c.

  • tupleList(c) is a dynamic array of tuples. It records all the tuples that have been checked to be allowed by c. New tuples will be added at the end of the array. The tuples in tupleList(c), which have not been verified to be invalid, are called active tuples.

  • firstActive(c) is the position of the first active tuple in tupleList(c). It is initialized to 0. All active tuples in tupleList(c) are indexed from tupleList(c).length-1 to firstActive(c). The tuples before firstActive(c) are deleted.

  • levelLast(c) is an array of size n + 1 where n is the number of variables. levelLast(c)[p] is the position of the last invalid tuple of tupleList(c) removed when the search was at level p. Level 0 corresponds to the preprocessing step. levelLast(c)[p] = −1 if no tuple was removed at level p. It is used to record and restore firstActive(c) at each level during search.

The GTR algorithm for a constraint is present in algorithm 3 and it is called at line 5 in algorithm 1. When MGTR is propagating at level i, all the tuples in tupleList(c) before firstActive(c) have been verified to be invalid at previous levels, so they will not be checked. The first part of GTR is implemented at lines 3 to 11 and the second part is from lines 13 to 24. In part1, all the values with residue supports are identified. In part2, a GAC3 scheme is employed to find a support for the rest values. If a support is found, it is added to the end of tupleList(c) at line 22. If lines 3 to 11 and lines 22 to 24 are removed, algorithm 3 degenerates into a constraint-oriented GAC3 algorithm.

figure c

Algorithm 4 removes the tuple indexed at i by switching it with the first active tuple indexed by firstActive(c) and increasing firstActive(c) by 1. In this way, all the deleted tuples are moved to the position before firstActive(c), so they will not be rechecked if no backtracking occurs. If a backtracking occurs at level i, the restore procedure in algorithm 5 restores the tuples deleted at level i by simply recovering firstActive(c). After the restoring, the order of the active tuples may be different. This is not a problem, because all tuples after firstActive(c) will be checked in next invocation. This mechanism also ensures that the new added tuples will not be missed.

figure d
figure e

The example in Fig. 1 illustrates how the data structures of GTR work. A constraint c defined by a predicate x + y = z, dom(x) = dom(y) = {1, 2, 3} and dom(z) = {3, 4, 5}. At the beginning, tupleList(c) is empty, firstActive(c) is 0 and the elements in levelLast(c) are −1.

  • (a) The first invocation skips part1. It finds the supports for all values and adds the tuples into tupleList(c) at part2.

  • (b) At level 1, (x, 1) is removed by other constraint. At part1, the algorithm checks tuples indexed from 4 to 0 and (1, 2, 3), (1, 3, 4) are removed. At part2, (2, 2, 4) is found as the support for (y, 2) and it is added to the end of tupleList(c).

  • (c) At level 2, (y, 3) is removed. At part1, the algorithm checks tuples indexed from 5 to 2 and (2, 3, 5) is removed. As the new support for (z, 5), (3, 2, 5) is added to the end.

  • (d) Assuming that c is never checked again until the searching backtracks to level 1. After the backtracking, both (x, 1) and (y, 3) are restored. In order to restore the deleted tuples, firstActive(c) is set to levelLast(c)[1] in Fig. 1b. Then, levelLast(c)[1] is set to -1. In the 4th invocation, all the 7 tuples will be checked at part1.

Fig. 1
figure 1

Data structures of GTR

Full size image

Proposition 1

The worst-case time complexity of GTR to establish GAC at the preprocessing step isO(er3dr+1)with space complexity O (er2d).

Proof

At the preprocessing step, the tuples in tupleList(c) which are verified to be invalid can be discarded. In the worst case, each tuple in tupleList(c) supports only one value, so there are at most rd tuples in tupleList(c) at the preprocessing step. Therefore, the part1 of algorithm 3 costs r2d time, because each validity check costs r time. The part2 cost r2dr time, because there are r variables in scp(c), d values in the domain of each variable, findSupport(x, a, c) may iterate over at most dr−1 tuples and each constraint check costs r time. So the worst-case time complexity of algorithm 3 is O(r2dr). For each constraint c, algorithm 3 will be called at most rd times and there are e constraints; therefore, the worst-case time complexity to establish GAC is O(er3dr+1). As for space, there are at most rd tuples in tupleList(c), each tuple needs r space and there are e constraints, so the worst-case space complexity is O(er2d). □

Proposition 2

The worst-case space complexity of maintaining GTR during search is O(erdr).

Proposition 2 is straightforward, because the total number of tuples recorded in tupleList(c) is at most dr when GTR is maintained during search.

Proposition 3

The GTR algorithm avoids all positive repeats when it is maintained during search.

Proof

For each constraint c, all the tuples that are checked to be allowed are stored in tupleList(c), so a positive repeat occurs iff a tuple in tupleList(c) is checked. During each invocation, all the tuples before firstActive(c) are invalid, so they will not be checked. The tuples after firstActive(c) are valid and all the values appearing in these tuples are identified as having supports. In part2, the algorithm seeks supports for only those values that have not been identified as having supports and each of the tuples after firstActive(c) contains at least one value that has been identified as having supports, so these tuples will not be checked. Therefore, no positive repeat occurs when maintaining GTR during search.

Property 1

For each constraint c, there is no duplicate tuple in tupleList(c).

The property is true, because maintaining GTR during search has no positive repeat, so a tuple allowed by c will be checked and added into tupleList(c) at most once. □

Besides naive GTR, the algorithm can be improved by the methods used in STR2. The improved version, GTR2, is shown in algorithm 6. GTR2 does not improve the worst-case time complexity, but it avoids some unnecessary operations. The additional data structures used in GTR2 is same as those used in STR2. The Ssup records the variables that at least one value has not found a support. If all values in dom(x) have already found a support, we remove x from Ssup, then efficiency is gained by iterating over only variables in Ssup at lines 15, 24, and 34. The Sval records the variables whose domain was changed between last invocation and this invocation. The lastSize(c)[x] records the domain size of x after each invocation of constraint c and is used to determine whether the domain of a variable was changed recently. To check the validities of the tuples, we do not check the values of variable x if dom(x) was not changed between last invocation and this invocation. Therefore, at line 14 of algorithm 6, the procedure is Valid(τ, Sval) checks only the variables in Sval to verify if τ is valid.

figure f

4 Discussion and related works

GTR avoids all positive repeats and the corresponding negative repeats executed before each positive repeat. However, the negative repeats for proving a value having no support cannot be avoided by GTR. When GTR is maintained during search, the part1 iterates over O((1-t) dr) allowed tuples where t is constraint tightness. For each value, the part2 tries O(tdr−1) disallowed tuples before finding a support. If the constraint is tight, (1-t) dr is a relatively small number and it is relatively harder to find a support for a value; therefore, GTR should be efficient when being used on tight constraints. On the contrary, if the constraint is loose, it is relatively easier to find a support and (1-t) dr may be a large number, so GTR may be inefficient for loose constraints.

The part1 of GTR is similar to the simple tabular reduction (STR) algorithm [8, 13, 19, 21] which operates on extensional constraints listing all allowed tuples in a table. Both them identify the values which have supports by iterating over the allowed tuples. One difference is that STR iterates over a static table of allowed tuples of a constraint, whereas GTR iterates over a dynamic list of tuples that are checked to be allowed. When a backtracking occurs, STR has a mechanism to restore tuples with few time cost, which is suitable for only static tables. GTR employs a similar mechanism to restore deleted tuples with the same time cost, which works on dynamic lists. Another difference is that STR determines if a value has supports after iterating the table, because all allowed tuples are already in the table, whereas GTR usually identifies some of the values with supports after iterating the dynamic list, for the rest values, it uses constraint checks to determine if they have supports. We prefer STR to GTR on extensional constraints, because STR is a specialised algorithm for these constraints. However, GTR is a generic GAC algorithm that works on all kinds of constraints.

GTR is also similar to the GIC4 algorithm proposed in [1], but they enforce different consistencies. Another difference between them is that GTR records the results of constraint checks for each constraint, whereas GIC4 maintains only one list of global solutions. GIC4 enforces global consistency, so maintaining GIC4 during search in backtrack-free and it does not restore deleted solutions. The major advancement of GTR over GIC4 is that GTR has a mechanism to cope with backtracking and the deleted tuples can be restored with low cost.

Exploring multiple residue supports, the GAC3rm_k algorithms [11], where k is the maximum number of residues, enforces less positive repeats than GAC3rm. When searching for a support for a value, GAC3rm_k first checks the validities of the k residues. If none of the residues is valid, it starts to search for a new support by constraint checks. If k is set to infinity, no residue support is discarded, so GAC3rm_infinity also avoids all positive repeats and the worst-case space complexity of GAC3rm_infinity is the same as that of GTR. However, compared with GTR, GAC3rm_infinity cannot avoid redundant validity checks. It may execute much more validity checks than GTR. The dynamic list of GTR may be adopted in MGAC3rm_infinity to avoid redundant validity checks, but each value on each constraint needs a dynamic list, so it maintains rd dynamic lists for each constraint, which is much more than that of GTR.

The MAC3cache algorithm [14] caches the results of all possible constraint checks. This method was proposed to work on binary CSPs, because caching the results of all possible constraint checks will cost dr space for each r-arity constraint. When a constraint check is repeated, MAC3cache can get the result with low cost. GTR also caches the results of some constraint checks, but only the allowed results, not all possible constraint checks. Actually, we would prefer the STR algorithm to a classical GAC algorithm after all allowed tuples are cached.

5 Experiments

The experiments were run on a PC with Intel(R) Core(TM) i5-3210M CPU @2.5GHz, 4GB RAM, JDK 1.7. The performance of maintaining each GAC (or AC for binary instances) algorithm for finding the first solution or proving unsatisfiable is measured by CPU time (cpu) in seconds, number of constraint checks (cc), and number of validity checks (vc). The numbers of cc and vc are present by kilo (K), million (M), and billion (B). Timeout (out) is 1200 s and maximum memory is set to 1000M. In the average results, the cpu time of timeout instances are counted as 1200 s. The results of those instances where all solvers are timeout are eliminated from the average results. The variable ordering heuristic is dom/wdeg [6] equipped with a random restart strategy [7, 22]. The GAC3rm_k algorithms are implemented with a static FIFO policy and the later added residues are checked earlier.

Firstly, we compared GTR with GAC3rm, GAC3rm_2, GAC3rm_infinity, GAC3.1, and GAC3.2 on some non-binary instances containing intensional constraints. GTR and the GAC3rm algorithms are light when being used in search, whereas GTR2 maintains the data structure lastSize. GAC3.1 and GAC3.2 maintain the data structure last during search. As we mentioned at Section 4, the gain in efficiency that GTR brings is related to constraint tightness, so we tested five problems contain some tight constraints (Multi-Knapsack Instances (mknap), magicSquare, Balanced Incomplete Block Designs (BIBD), CostasArray, Radar Surveillance (radar)) and three problems contain only loose constraints (ChessboardColoration, Two-Dimensional Strip Packing Problems (tdsp) and Golomb Ruler). All these benchmark instances are downloaded from http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html.

Table 1 presents the results of some problems containing tight constraints. The integers in the brackets under instance names are the number of tested instances in that series. On the mknap, magicSquare, and BIBD instances, we can see that GTR algorithms trade a relatively small number of validity checks (compared to the number of constraint checks) for some constraint checks. Consequently, they save some cpu time. More specifically, the gain on each mknap instance is from the only tight constraint and the gains on magicSquare and BIBD instances are from the weightedSum constraints in these instances. On the CostasArray instances, GTR algorithms save a little time from the trading, it reduces the sum of validity checks and constraint checks. The radar-8-30-3-0-15 instance is the only representative which needs 729 search tree nodes to solve (others are easier). GAC3.2 enforces less constraint checks than GTR on the mknap instances, because it maintains the data structure last during search, which avoids some negative repeats.

Table 1 Results on non-binary instances with tight constraints
Full size table

Table 2 presents the results of some problems containing only loose constraints. The results of Chessboardcoloration, tdsp, and Golomb ruler show that it is not recommended to trade constraint checks for validity checks on loose constraints. The GTR algorithms are not efficient on these instances, but they are still better than GAC3rm_infinity, because GAC3rm_infinity needs much more validity checks. The GTR2 algorithm maintains additional data structures during search, so it costs more cpu time than the GTR algorithm on the instances containing a large number of constraints, e.g., the Chessboardcoloration instances, but it improves GTR in general.

Table 2 Results on non-binary instances without tight constraints
Full size table

Secondly, we compared GTR with AC3rm on binary instances including real-world, patterned, and academic binary instances. The results in Table 3 show that GTR is not efficient on these binary instances even on those instances containing tight constraints [12]. The main reason is that GTR is built in a GAC scheme which is less efficient than an AC scheme. Both GTR and an AC scheme check the validity of residue supports. The GTR needs two operations to check the validity on binary constraints, whereas an AC scheme needs only one operation. Each valid residue support supports only one value in both schemes. For an r-ary constraint, GTR needs r operations to check the validity of a residue support and the residue support supports r values.

Table 3 Results on binary real-world, patterned, and academic problems
Full size table

In summary, the GTR algorithms have few improvement on binary instances, but they bring some improvements on non-binary tight constraints.

6 Conclusion and future work

In this paper, we propose a new generalized arc consistency algorithms GTR and its improved version GTR2, which avoid all positive repeats. The experimental results show that the GTR algorithms save a number of constraint checks. It is not suggested to use GTR on binary instances, but it works well on those tight constraints with larger arity. If we adopt the dynamic list of supports in some higher level local consistencies where the cost of finding a support is much more expensive, potentially, it may bring more improvement on cpu time.