A Fast Algorithm for Generalized Arc Consistency of the Alldifferent Constraint

1 Introduction

Constraint Programming is a powerful tool for problem solving and has been widely used in various real-world applications. Constraint Satisfaction Problem (CSP) defines a set of variables whose values must satisfy some specified constraints. One of the most useful and important constraints is the alldifferent constraint [Lauriere 1978], which requires that all variables of the constraint must have different values. The alldifferent constraint can be found in wide varieties of combinational problems [Wallace 1996], including various puzzles, graph coloring, and assignment problems.

A typical approach to solve a CSP is to search from all possible variable values. To accelerate this search process, various consistency techniques have been introduced to remove values from the domain of a variable which does not belong to any solution to the problem. A classic filtering algorithm for Generalized Arc Consistency (GAC) for alldifferent constraints is proposed by Régin [Régin 1994]. The algorithm utilizes a theorem of C. Berge [Berge and Minieka 1973] from graph theory and prunes redundant edges that do not appear in any maximum matching of the value graph of alldifferent constraints. For weaker forms of the consistency of alldifferent constraints, Leconte [Leconte 1996] provides an algorithm for the range consistency based on identifying Hall intervals. Puget [Puget 1998] proposes an algorithm for the bounds consistency, which is weaker than the range consistency. To our knowledge, Régin's algorithm is still the-state-of-art filtering method for GAC of the alldifferent constraint. Gent [Gent, Miguel et al. 2008] discuss several implementation details of Régin's algorithm, especially the computation of the Strongly Connected Components (SCC) of the residual graph. A survey for the alldifferent constraint can be found in [van Hoeve 2001]. Recently, as a powerful tool, alldifferent constraints are extensively used to solve difficult constraint optimization problems, such as subgraph isomorphism [Solnon 2010] and constraint clustering [Duong and Vrain 2017].

In this paper, we developed a simple and fast algorithm for the alldifferent constraint. Our new algorithm is based a novel theorem for identifying redundant edges of the value graph of alldifferent constraints. We classified the redundant edges into two types: one type of redundant edges can be obtained immediately by finding a maximum matching, and the second type of redundant edges can be found by computing SCCs in a small sub-graph. Based on this theorem, we designed an efficient algorithm for the alldifferent constraint. The major improvement of our algorithm comes from identification of type 1 redundant edges, which allow us to remove a substantial number of redundant edges without any additional computation. Compared with the-state-of-art approach, our new algorithm does not need to construct a residual graph, which has more edges than the original value graph. Therefore, the SCCs computation in our algorithm is also faster than the previous algorithm. We evaluated the performance of our new algorithm on many benchmark instances by using Minion 1.8 software [Gent, Jefferson et al.], and the result showed that our algorithm outperformed Régin's algorithm on all problem instances.

The paper is organized as follows. We present in Section 2 the definitions related to constraint satisfaction problems and graph theory. We present and prove in Section 3 the novel theorem for identifying the redundant edges of a value graph, and present a fast algorithm for the alldifferent constraint. We evaluate the performance of our algorithm on several real problems in Section 4, and conclude with discussions in Section 5.

2 Background and Preliminaries

Constraint programming. A constraint satisfaction problem (CSP) is a triple (X, D, C), where X is a set of variables, {x1, x2, ... , xn}, D is a set of domains {D1, D2, . . ., Dn}, where Di is the set of possible values for variable xi, and C is a set of constraints between variables. A constraint c∈C is defined as a subset of the Cartesian product of the domains of the variables that are in C. A solution to a CSP (X, D, C) is a set of values (d1,...,dn) ∈ D1×···×Dn, where for every constraint c∈C on the variables xi1,...,xim, we have (di1, ..., dim)∈c. A constraint is generalized arc consistent (GAC) iff every value of the variables can be extended to all the other variables of the constraint in such a way the constraint is satisfied.

An alldifferent constraint c(x1,...,xn) is a constraint that specifies that xi≠xj for any i < j. For an alldifferent constraint c, a bipartite graph B(c) = (Xc, Dc, E) is called a value graph of c, where (xi, d) ∈ E iff d ∈ Di. To achieve the GAC on an alldifferent constraint, we need to introduce some concepts from graph theory, especially about maximum matching.

Graph Theory. Consider a bipartite graph B(U,V,E), in which U, V are two disjoint sets of nodes and every edge in E connects a node in U to one in V. A matching is a set of edges that share no common node. A node is called a matched node if it is connected to an edge in the matching, or a free node, otherwise. A matching with the maximum number of edges is called a maximum matching. An alternating path is a path whose edges are alternate in and out of the matching. An augmenting path is an alternating path whose two end nodes are free nodes.

A bipartite graph may have more than one maximum matching, so that maximum matching is usually not unique. There may exist many maximum matchings with the same size for a graph. An allowed edge is an edge belonging to some, but not all, of maximum matchings. A redundant edge is an edge that does not appear in any maximum matchings. Similarly, an allowed node is a node covered by some, but not all, of maximum matchings.

Régin's filtering Algorithm. An alldifferent constraint is GAC iff every edge of its value graph belong to some matchings that cover Xc in B(c) [Régin 1994]. Therefore, to achieve GAC, we need to remove the redundant edges of its value graph. Régin [Régin 1994] present a filtering algorithm based on the following property:

Property 1 (Berge 1970) An edge is allowed, iff, for an arbitrary maximum matching M, it belongs to either an even alternating path begins at a free node or an even alternating cycle.

Therefore, to identify all of the redundant edges of the value graph, the algorithm first computes a maximum matching, and then finds all alternating paths beginning at free nodes and all even alternating cycle based on SCCs. The last two steps can be combined by finding SCCs in a directed residual graph. The residual graph is constructed by adding one virtual node and |Dc| edges to the original value graph. Therefore, the residual graph is always larger than value graph. The unmatched edges between independent SCCs of the residual graph are redundant edges. An example is shown in Figure.1.

3 Identify Redundant Edges

For an alldifferent constraint c, the variable-value pairs corresponding to the edges that never appear in any maximum matching should be pruned. Therefore, in the rest of the paper, we focus on how to efficiently identify all of the redundant edges of a value graph.

Consider an alldifferent constraint c(Xc, Dc) and its value graph B(c) = (Xc, Dc, E). Let A be the set of allowed nodes of B(c), and Γ(A) be the set of the neighbor nodes of A. It is obvious that if there exists a solution to the constraint, all nodes of Xc must be matched. Therefore, the allowed nodes can only be found in set Dc. The node set of the value graph can be divided into four sets: A, Γ(A), Dc-A, Xc-Γ(A). The allowed nodes can be easily identified by our previous work [Zhang, Han et al. 2017], which was originally used to identify the input node of a network.

Property 2 [Zhang, Han et al. 2017] A node is allowed, iff for an arbitrary maximum matching M, it can be reached by an even alternating path that begins at a free node.

Based on Property 2 and using our node set partition, we now present a new theorem for identifying redundant edges:

Theorem: For an arbitrary maximum matching, an unmatched edge emn is redundant, iff

1. m∈Γ(A) and n∈Dc-A , or
2. m∈Xc-Γ(A), n∈Dc-A and emn does not belong to any alternating cycle.

Proof: Based on the definitions of A, Γ(A), Dc-A and XcΓ(A), the edges of a value graph can be divided into three sets: E(Γ(A),A), E(Γ(A),Dc-A) and E(Xc-Γ(A),Dc-A) (Figure.2). Note that based on the definition of Γ(A), all neighbor nodes of A should be in Γ(A). Therefore, there is no edge between A and Xc-Γ(A).

We first prove that all edges of E(Γ(A), A) are allowed edges. Consider an unmatched edge eba∉M, where a∈A and b∈Γ(A). Because a is an allowed node, based on property 2, there must exist an even alternating path P connecting node a and a free node. Consider the path P+eba, if we swap the matched and unmatched edges of the path, we have a new maximum matching M', where eba∈M. Therefore, all edges of E(Γ(A), A) are allowed edges and can be in the new maximum matching M'.

Next, we prove that all edges of E(Γ(A), Dc-A) are redundant. Because Γ(A) is part of the set of variables, any node of Γ(A) should be matched. Otherwise, there is no solution to the constraint. Suppose emn is an allowed edge, where m∈Γ(A) and n∈Dc-A. Because Γ(A) is the neighbor set of A and any node of A is allowed, there must exist an alternating path P starting at a free node connected to node m. Therefore, the path P+emn is an alternating path. Based on Property 2, node n is an allowed node. That contradicts with the definition of node n. Therefore, all edges of E(Γ(A), DcA) are redundant edges.

Finally, we prove the edges of E(Xc-Γ(A), Dc-A) are redundant edges iff they are not matched and do not belong to any alternating cycle. Note that it is a corollary of Property 1. Therefore, the proof is completed.

Figure 2 gives a simple example of above theorem. After finding a maximum matching (red edges) of the value graph, node 5 is the only free node. The set of allowed nodes are A={3,4,5} because the nodes 3 and 4 can be reached by alternating path start from node 5. The neighbor set of A is Γ(A)={x3,x4}. Based on our theorem, the edges between set Γ(A) and Dc-A can be removed from the value graph. Therefore, we only need to find the unmatched edges between sets {x1, x2} and {1,2} and not in any alternating cycle, which is the edge e(x2,1).

This theorem offers us an efficient way to find redundant edges in a bipartite graph. Based on this theorem, the edges between node sets Γ(A) and Dc-A are denoted by type 1 redundant edges, and the other redundant edges by type 2 redundant edges. The type 1 redundant edges can be easily obtained after finding the set of allowed nodes. The allowed nodes can be found by finding a maximum matching based on Property 2. The basic idea of a maximum matching algorithm, such as Hopcroft-Karp algorithm [Hopcroft and Karp 1973] or Hungarian Algorithm [Kuhn 1955], is to iteratively find all augmenting paths corresponding to the matching M at hand, and then to derive a larger matching M'. A maximum matching is obtained when no augmenting path can be found. The last step of the algorithm is exactly to find all alternating paths starting at the free nodes of the maximum matching. Therefore, all allowed nodes and their neighbors can be obtained in the last step of a maximum matching algorithm, which provides the first part of redundant edges. For the rest of redundant edges, we only need to find SCCs in a smaller sub-graph B'(Xc-Γ(A), Dc-A, E'), where E'⊂E is the edge\ set connecting Xc-Γ(A) and Dc-A.

The above idea and steps are formulated in Algorithm 1 for filtering value graph B of alldifferent constraints.

ALGORITHM1: Fast filtering alldifferent constraint

1. Input: Value graph B(c) = (Xc, Dc, E), initial matching M;
2. Repeat
3. Find all alternating paths AP from all free node based on current matching M;
4. Put the nodes in Dc of AP into set A, and their neighbor nodes in Xc into set Γ(A);
5. If AP contains the augmenting paths then
6. expand the augmenting paths and obtain a new matching M';
7. Let M=M'; clear set A and Γ(A);
8. If size(M)=size(Xc) then
9. prune all edges between set Γ(A) and set Dc-A;
10. Until no augmenting path is found;
11. If size(M)<size(Xc) return false;
12. // Above is the first parts of the redundant edges of value graph
13. Find all strong connected component (SCC) of bipartite graph B'(Xc-Γ(A), Dc-A, E');

13. Prune all edges that are unmatched and connect nodes between two SCCs;

The first part of our algorithm is to find a maximum matching, and this can be done in O(|Xc| 0.5 |E|) by the Hopcroft-Karp algorithm. The second part is to find SCC of the bipartite graph B'(Xc-Γ(A),Dc-A,E'), and this can be accomplished in O(|Xc-Γ(A)|+|Dc-A|+|E'|) by the Tarjan algorithm [Tarjan 1972]. Although our algorithm has the same worst-case complexity as the previous works, it has a better performance in practice. This is because many redundant edges can be immediately removed after finding a maximum matching and we only need to find SCCs in a smaller graph B'(Xc-Γ(A), Dc-A, E') rather than the original value graph.

The first part of Algorithm 1 (steps 1-10) is basically to find a maximum matching. Therefore, it can be integrated with many maximum matching algorithms, such as the Hopcroft-Karp algorithm or the Hungarian Algorithm. Furthermore, the improvement of our algorithm is the identification of type 1 redundant edges in the matching process, therefore, it can be combined with many optimization technics for alldifferent constraints, such as incremental matching, domain counting, priority queue, staged propagation or computing SCCs independently [Gent, Miguel et al. 2008].

4 Experimental Results

We evaluated the performance of our new algorithm. We first analyzed the fraction of type 1 redundant edges among all redundant edges. We then compared the performance of our algorithm with the-state-of-art approaches on a large collection of benchmark instances for alldifferent constraints. Our algorithm was implemented based on Minion constraint solver 1.8 [Gent, Jefferson et al.]. All experiments were run on a Windows 7 workstation with a quad-core Intel i7-3770 processor of 3.9 GHz and 32GB DDR3 1600MHz RAM.

In our experiment, we first generated a series of synthetic bipartite graphs by using the scale-free network model of [Shen-Orr, Milo et al. 2002] and the ER random network model of [Bollobás 2013], where we set |Xc|=|Dc|=1000. Type 1 redundant edges can be obtained right after maximum matching. Therefore, our algorithm will be more efficient if there are more type 1 edges. When the average node degree increases, most of the redundant edges are type 1 and the size of B'(Xc-Γ(A), Dc-A, E') is relatively small (Figure 3). This means that after finding a maximum matching, most of the redundant edges can be found, and the remaining redundant edges can be obtained in a small value graph B'(Xc-Γ(A), DcA, E'). It will greatly increase the efficiency of our algorithm in practice. We also assessed the fraction of type 1 redundant edges in some real problems (Figure 4). We counted the total number of redundant edges during the searching process and computed the fraction of type 1 and type 2 redundant edges. It is evident that many problems also have a large portion of type 1 redundant edges.

Next, we implemented our new algorithm by using the Minion software, Version 1.8 [Gent, Jefferson et al.]. This software already has an implementation of Régin's [Régin 1994] Filtering algorithm, and other optimization techniques, such as incremental matching [Régin 1994], BFS matching [Cormen 2009] and staged propagation [Schulte and Stuckey 2004]. For the implementation of our algorithm, we use Hopcroft-Karp algorithm to obtain maximum matching and Tarjan algorithm to compute SCCs. We also use incremental matching technique, which is same as [Régin 1994]. We compared our algorithm with the following implementations: 1) Régin's Filtering algorithm with incremental matching (IncMatch); 2) IncMatch using the FF-BFS matching algorithm instead of Hopcroft-Karp algorithm (IncMatchBFS); 3) IncMatch-BFS with staged propagation (IncMatchBFS-Staged). The searching strategy we used to solve the problems is the depth-first chronological backtracking. The benchmark instances were chosen from [Gent, Miguel et al. 2008], including Langford's number problem (prob024 in CSPLib [Gent and Walsh 1999]), golomb ruler problem (prob006 in CSPLib), balanced quasigroup with holes (QWH) [Kautz, Ruan et al. 2001], quasigroup existence (prob003 in CSPLib), social golfers (prob010 in CSPLib), graceful graphs (prob053 in CSPLib), N-Queens (prob054 in CSPLib) and sports scheduling.

We compared our algorithm with the three existing methods mentioned above on these instances of constraint satisfaction problems. In the experiments, we limited time to 4 hours and nodes to 10 6 . For those problems which the solution can be found within the time limit, we compared the raw runtime (Figure 5 and Table 1). For those problems which exceed the time limit, we counted the number of nodes searched per second (Figure 6). As shown in Table 1 and Figure 5-6, our algorithm is never slower than the other algorithm compared and can typically run 1-6 times faster than these methods. To reiterate, the gain on efficiency for our algorithm comes from the identifying and removing type 1 constraints with little computation. On those problems that do not have type 1 redundant edges, our algorithm also has a better performance because it finds SCCs in the value graphs rather than the residual graphs, which have more edges than the original value graphs.

5 Conclusion

We developed a fast filtering algorithm for realization of generalized arc consistency for the alldifferent constraint. We presented a novel theorem for identifying redundant edges in a constraint graph which need to be removed. We showed that our algorithm significantly outperformed the best GAC algorithms on all of benchmark problems that we tested, significantly reduced computation time on these real problems. Our algorithm can be used to improve the performance of solving constraint satisfaction problems that contain alldifferent constraints.

Acknowledgments

This research was supported by the Natural Science Foundation of China under grant number 91546110, and China Scholarship Council under grant number 201606085011.