Bimodal Depth-First Search for Scalable GAC for AllDifferent

Sulian Le Bozec-Chiffoleau; Nicolas Beldiceanu; Charles Prud&#039;homme; Gilles Simonin; Xavier Lorca

IJCAI 20250 citations

Bimodal Depth-First Search for Scalable GAC for AllDifferent

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

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.

BibTeX

@inproceedings{ijcai2025_bimodaldepthfirs,
  title = {Bimodal Depth-First Search for Scalable GAC for AllDifferent},
  author = {Sulian Le Bozec-Chiffoleau and Nicolas Beldiceanu and Charles Prud&#039;homme and Gilles Simonin and Xavier Lorca},
  booktitle = {IJCAI 2025},
  year = {2025}
}