Proceedings

Variable-Oriented Adaptive Singleton Consistency

Yaling Wu, Hongbo Li, Minghao Yin

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 2391-2399.

https://doi.org/10.24963/ijcai.2026/266

Keywords

  • Constraint Satisfaction and Optimization: Constraint satisfaction
  • Constraint Satisfaction and Optimization: Constraint programming

Abstract

Singleton consistency significantly reduces the search space of backtracking search for solving constraint satisfaction problems (CSP). However, it is too expensive to be used throughout the search, and it has not been successfully applied in solving general CSPs. In this paper, we propose a variable-oriented adaptive singleton consistency, namely VOASC, that could be applied in general-purpose constraint solvers. It calculates the filtering efficiency of local consistency enforced by the default propagation engine and the singleton-based consistency for each variable, and then selects an appropriate consistency to propagate the decisions of the variable in subsequent searches. We performed extensive experimentation with the MiniZinc benchmark suite. VOASC demonstrates superior solving performance on both CSP and COP, compared to the two candidate local consistencies and several existing adaptive propagation methods.

Yaling Wu, Hongbo Li, and Minghao Yin. 2026. Variable-Oriented Adaptive Singleton Consistency. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 2391–2399. https://doi.org/10.24963/ijcai.2026/266
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards