Proceedings

Bimodal Depth-First Search for Scalable GAC for AllDifferent

Sulian Le Bozec-Chiffoleau, Nicolas Beldiceanu, Charles Prud'homme, Gilles Simonin, Xavier Lorca

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 2610-2618.

https://doi.org/10.24963/ijcai.2025/291

Keywords

  • Constraint Satisfaction and Optimization: CSO: Constraint programming
  • Constraint Satisfaction and Optimization: CSO: Solvers and tools
  • Constraint Satisfaction and Optimization: CSO: Constraint satisfaction

Abstract

We propose a version of DFS designed for Constraint Programming, called bimodal DFS, that scales to both sparse and dense graphs. It runs in O(n + ~m) time, where ~m is the sum, for each vertex v, of the minimum between the numbers of successors and non-successors of v.

Integrating it into Régin’s GAC algorithm for the AllDifferent constraint results in faster performance as the problem size increases, outperforming a GPU-accelerated version.

In the vast majority of our tests, GAC now performs similarly to BC in terms of speed, but is able to solve more problems.

Sulian Le Bozec-Chiffoleau, Nicolas Beldiceanu, Charles Prud'homme, Gilles Simonin, and Xavier Lorca. 2025. Bimodal Depth-First Search for Scalable GAC for AllDifferent. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 2610–2618. https://doi.org/10.24963/ijcai.2025/291
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards