A Fast Algorithm for Generalized Arc Consistency of the Alldifferent Constraint

Xizhe Zhang, Qian Li, Weixiong ZhangIJCAI 2018 · OpenReview

Abstract

The alldifferent constraint is a fundamental component of Constraint Satisfaction Problems (CSPs), requiring a set of variables to take unique values. Enforcing Generalized Arc Consistency (GAC) for this constraint is typically achieved by identifying and removing "redundant edges" in a value graph—edges that cannot belong to any maximum matching. Traditionally, this process involves computing strongly connected components (SCCs) in a residual graph, a computationally intensive task. This paper introduces a novel theorem that categorizes redundant edges into two types. We demonstrate that Type 1 redundant edges can be identified immediately following the maximum matching phase, significantly reducing the need for full SCC analysis. Our resulting algorithm demonstrates a 1- to 6-fold speedup over state-of-the-art methods across various synthetic and real-world benchmarks.

Introduction

In CSPs, the alldifferent constraint ensures that every variable in a given set is assigned a distinct value. To solve these problems efficiently, solvers use filtering algorithms to prune the search space by maintaining Generalized Arc Consistency (GAC). Since Régin’s seminal work in 1994, the standard approach has been to model the constraint as a bipartite value graph and find a maximum matching. Edges that do not participate in any maximum matching are "redundant" and can be safely removed. However, identifying these edges traditionally requires constructing a residual graph and finding its SCCs, which often becomes a performance bottleneck in large-scale applications.

Methods: Categorizing Redundant Edges

The core contribution of this work is a theoretical refinement of redundant edge identification. We classify redundant edges into two categories:

  1. Type 1 Redundant Edges: These edges are connected to nodes reachable via specific alternating paths from "free" (unmatched) nodes. Crucially, these can be identified "for free" using information already gathered during the maximum matching process.
  2. Type 2 Redundant Edges: These are the remaining redundant edges that still require SCC-based identification.

By immediately pruning Type 1 edges, our algorithm avoids building a full residual graph. Instead, it performs SCC analysis only on a significantly smaller subgraph to find any remaining Type 2 edges. This "divide and conquer" strategy minimizes the overhead associated with traditional filtering.

Figure 5: The fraction of Type 1 redundant edges increases with graph density in both Erdős–Rényi (left) and Scale-free (right) bipartite graphs.

Key Insights and Results

The algorithm's performance was evaluated on synthetic bipartite graphs (Erdős–Rényi and Scale-free models) and a suite of real-world benchmarks from CSPLib, including the Golomb ruler, Langford’s problem, and N-Queens.

A key insight from the synthetic tests is the relationship between graph density and edge types. As shown in Figure 5, as the average degree (number of possible values per variable) increases, the proportion of Type 1 redundant edges grows. In dense graphs, Type 1 edges constitute nearly all redundant edges, allowing our algorithm to bypass almost all SCC computations.

Experimental results confirm that the new algorithm consistently outperforms the state-of-the-art, achieving speedups of 1x to 6x. On many real-world benchmarks, such as the Golomb ruler and Langford’s problem, Type 1 edges represent the vast majority of redundant edges (see Figure 6), validating the practical impact of our theoretical classification.

Figure 6: Distribution of Type 1 (blue) and Type 2 (red) redundant edges across various real-world benchmark problems.

Conclusion

While the algorithm offers significant practical speedups, its worst-case time complexity remains $O(n^{0.5}m)$, identical to existing methods. This occurs in rare scenarios where Type 1 edges are absent. However, the empirical performance gains and memory efficiency—due to avoiding full residual graph construction—make it a superior choice for modern CSP solvers. Future research will explore applying this Type 1/Type 2 decomposition to other global constraints, potentially extending these efficiency gains to a broader class of automated reasoning problems.

Summary updated

Abstract

The alldifferent constraint is an essential ingredient of most Constraints Satisfaction Problems (CSPs). It has been known that the generalized arc consistency (GAC) of alldifferent constraints can be reduced to the maximum matching problem in a value graph. The redundant edges, which do not appear in any maximum matching of the value graph, can and should be removed from the graph. The existing methods attempt to identify these redundant edges by computing the strongly connected components after finding a maximum matching for the graph. Here, we present a novel theorem for identification of the redundant edges. We show that some of the redundant edges can be immediately detected after finding a maximum matching. Based on this theoretical result, we present an efficient algorithm for processing alldifferent constraints. Experimental results on real problems show that our new algorithm significantly outperforms the-state-of-art approaches.
BibTeX
@inproceedings{zhang2018fast,
  author = {Xizhe Zhang and Qian Li and Weixiong Zhang},
  title = {{A Fast Algorithm for Generalized Arc Consistency of the Alldifferent Constraint}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=rJ48YXfObB},
}

Loading related content...

Figure