Prediction-Based Adaptive Variable Ordering Heuristics for Constraint Satisfaction Problems

No single variable ordering heuristic dominates across constraint satisfaction problems, and the right choice often depends on structure that only becomes visible partway through the search. This work represents the shape of the early search tree as a sequence, predicts the eventual number of failures from it, and uses that prediction to pick a heuristic — identifying an effective one for 86% of hard instances and outperforming state-of-the-art adaptive methods on both solution rate and runtime.

Recommended citation: Jitao Xu, Y. Wu, H. Li, M. Yin. (2025). "Prediction-Based Adaptive Variable Ordering Heuristics for Constraint Satisfaction Problems." Proceedings of the AAAI Conference on Artificial Intelligence, 39(11), 11390.