A Bitwise GAC Algorithm for Alldifferent Constraints

Zhe Li, Yaohua Wang, Zhanshan Li

In the field of Constraint Programming (CP), the alldifferent constraint is a fundamental building block used to model problems ranging from Sudoku puzzles to complex scheduling and resource allocation. To solve these problems efficiently, solvers rely on filtering algorithms to prune the search space. The most rigorous level of pruning is Generalized Arc Consistency (GAC). However, traditional GAC algorithms often suffer from significant computational overhead. This paper introduces $Alldiff^{bit}$, a high-performance algorithm that leverages bitwise operations and a simplified connectivity model to achieve a 60% average speedup over state-of-the-art methods.

The Challenge of GAC Filtering

The classic approach to enforcing GAC, pioneered by the Régin algorithm, is rooted in graph theory. It involves constructing a bipartite matching between variables and values, building a residual graph, and identifying Strongly Connected Components (SCCs). Any edge in the graph that does not belong to an SCC or a path starting from a free node is considered redundant and can be removed.

Traditionally, identifying these components requires Tarjan’s algorithm or similar depth-first search (DFS) methods. These methods necessitate complex data structures—such as stacks, queues, and traversal pointers—that must be frequently updated and reset as the solver backtracks through the search tree. This maintenance creates a performance bottleneck, especially in large-scale problems where these structures are modified thousands of times per second.

The $Alldiff^{bit}$ Approach

The core innovation of $Alldiff^{bit}$ is the realization that the filtering process does not actually require identifying specific SCCs. Instead, it only needs to determine whether a node is reachable within a certain context. By reframing the problem from "partitioning nodes into components" to a simpler "yes-or-no" connectivity check, the authors eliminate the need for heavy graph-traversal structures.

Comparison of filtering algorithms: (a) Régin’s SCC-based approach, (b) Zhang18’s approach, and (c) the proposed bitwise filtering using node merging.

Key Methodological Innovations:

  1. Node Merging: The algorithm simplifies the bipartite graph by merging matched variable-value pairs into single nodes. This reduction in graph size directly translates to fewer operations during the filtering phase.
  2. Bitwise Adjacency Matrix: The graph is represented as a bit-matrix rather than linked lists or pointers. This allows the algorithm to exploit word-level parallelism (the WordRam model), processing multiple nodes simultaneously.
  3. Bit-BFS Connectivity: Instead of DFS, $Alldiff^{bit}$ uses a bitwise Breadth-First Search (BFS). By using simple bitwise OR and AND operations to propagate reachability, the algorithm aligns better with modern CPU architectures, performing connectivity checks in significantly fewer clock cycles.
  4. Synergistic Integration: The simplicity of the bit-matrix structure allows for the seamless integration of existing optimizations—such as SCC-splitting and early detection—which were previously difficult to combine due to conflicting data structure requirements.

Experimental Evaluation and Results

The researchers evaluated $Alldiff^{bit}$ using the XCSP3 benchmark suite, encompassing over 800 instances across 18 problem series, including GolombRuler, Sudoku, and MagicSquare. The algorithm was compared against four leading GAC implementations: Gent, WordRam, Zhang18, and Zhang20.

Performance comparison showing the CPU time of $Alldiff^{bit}$ (WordRam) against other state-of-the-art algorithms across various benchmarks.

The results demonstrate a significant leap in efficiency. $Alldiff^{bit}$ achieved an average performance speedup of 60.65% across all test groups. In challenging instances like GolombRuler, solving time was reduced from approximately 44 seconds to just 16 seconds. Notably, the algorithm was the fastest in every single one of the 18 problem categories tested, proving its robustness across diverse graph topologies.

Conclusion

By replacing complex graph-traversal logic with hardware-friendly bitwise operations, $Alldiff^{bit}$ sets a new standard for enforcing GAC in alldifferent constraints. While extremely large domains may eventually hit the limits of CPU word sizes, the current implementation provides a massive performance boost for the vast majority of practical CP applications. Future work may extend this bitwise connectivity approach to other global constraints, potentially offering similar speedups across the broader field of constraint satisfaction.

Summary updated

Abstract

The generalized arc consistency (GAC) algorithm is the prevailing solution for alldifferent constraint problems. The core part of GAC for alldifferent constraints is excavating and enumerating all the strongly connected components (SCCs) of the graph model. This causes a large amount of complex data structures to maintain the node information, leading to a large overhead both in time and memory space. More critically, the complexity of the data structures further precludes the coordination of different optimization schemes for GAC. To solve this problem, the key observation of this paper is that the GAC algorithm only cares whether a node of the graph model is in an SCC or not, rather than which SCCs it belongs to. Based on this observation, we propose AllDiffbit, which employs bitwise data structures and operations to efficiently determine if a node is in an SCC. This greatly reduces the corresponding overhead, and enhances the ability to incorporate existing optimizations to work in a synergistic way. Our experiments show that AllDiffbit outperforms the state-of-the-art GAC algorithms over 60%.
BibTeX
@inproceedings{li2023bitwise,
  author = {Zhe Li and Yaohua Wang and Zhanshan Li},
  title = {{A Bitwise GAC Algorithm for Alldifferent Constraints}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/221},
}
Figure