Abstract
Constraint Satisfaction Problems (CSPs) are fundamental to many real-world applications, from resource allocation to hardware configuration, but remain computationally expensive to solve. This paper introduces PBAVOH, a novel adaptive variable ordering heuristic that utilizes machine learning to predict the most efficient search strategy early in the solving process. By representing search tree topology as a unique numerical sequence called Numbers of Positive Decisions (NPD), the method identifies the optimal heuristic with high accuracy. Experimental results on MiniZinc benchmarks demonstrate that PBAVOH significantly outperforms existing state-of-the-art methods in both success rate and solving efficiency, particularly on difficult problem instances.
Introduction
Many complex logic challenges are modeled as Constraint Satisfaction Problems (CSPs). These problems are NP-hard, meaning they are computationally "expensive" to solve. The standard approach involves backtracking search, where a solver builds a search tree by making sequential decisions about variables. The order in which these variables are selected—the Variable Ordering Heuristic (VOH)—is critical: a good heuristic can find a solution in seconds, while a poor one may take years.
While adaptive solvers exist, they often struggle to identify the most efficient strategy early enough to make a difference for truly difficult instances. This research addresses the challenge by "peeking into the future" of the search algorithm using machine learning to predict which strategy will minimize failures.
Methodology: PBAVOH and NPD Sequences
The authors introduce PBAVOH (Prediction-Based Adaptive Variable Ordering Heuristic), which operates in three distinct phases:
- Probing Phase: The solver runs several candidate heuristics (e.g., ABS, CHS, FRBA) for a very short duration, limited by a small number of failures.
- Prediction Phase: During probing, the solver records the "topology" or shape of the search tree. The authors propose a new representation called the NPD sequence (Numbers of Positive Decisions). They mathematically prove that this sequence uniquely identifies the structure of a binary search tree.
- Selection Phase: The NPD sequence is fed into machine learning models—specifically Long Short-Term Memory (LSTM) networks and Gradient Boosting Decision Trees (GBDT). These models predict the total number of failures the search tree will encounter for each heuristic. The solver then selects the heuristic with the lowest predicted failure count to complete the search.
A key insight of this work is that the initial "shape" of a search tree—specifically how many successful steps are taken between failures—contains sufficient information to predict the eventual size of the entire tree. Furthermore, models trained on "easy" problem instances were found to be highly effective at predicting outcomes for "hard" problems, suggesting universal structural properties in search trees across different logic domains.
Experimental Evaluation
The researchers evaluated PBAVOH using the MiniZinc benchmark suite, a standard in the constraint programming community. The training set consisted of 937 easy instances, generating nearly 28,000 data points. Testing was conducted on 1,876 instances across 46 different models, with a specific focus on 356 "hard" instances that remained unsolved after the initial probing phase.
Key Results
PBAVOH demonstrated superior performance compared to existing state-of-the-art methods:
- Higher Success Rate: PBAVOH solved 307 out of 356 hard instances (roughly 86%), outperforming the previous leading adaptive method, SEVOH, which solved 285.
- Better Efficiency: In terms of the PAR2 score (a metric that penalizes timeouts), PBAVOH achieved a score of 686.8, significantly lower (better) than SEVOH (787.6) and the AST algorithm (854.8).
- Robustness: A "Blend" version combining LSTM and GBDT models provided the most stable results, effectively identifying the best heuristic even when one model made a poor prediction.
Conclusion and Future Work
The proof that an NPD sequence has a one-to-one correspondence with tree topology is a significant theoretical contribution, providing a compact and machine-learning-friendly descriptor for search behavior. However, some limitations remain. The current NPD representation is tailored for binary search trees; extending this to $k$-way branching remains a challenge. Additionally, while the probing overhead is minimal, it does represent a small computational cost. Future work could explore dynamic heuristic switching if the search tree's topology changes unexpectedly during the solving process.
Summary updated