Introduction
In the domain of Constraint Satisfaction Problems (CSPs)—which underpin applications ranging from scheduling to hardware verification—computational efficiency is paramount. A key technique for accelerating solvers is computing a "minimal network," ensuring every tuple in a constraint belongs to at least one valid solution. However, the two primary algorithms for this task, PerTuple and AllSol, exhibit vastly different performance profiles depending on the problem instance. While PerTuple is generally faster for easy-to-find solutions, AllSol excels when solutions are sparse. This research addresses the "algorithm selection problem" by employing machine learning classifiers to predict the optimal algorithm for a given CSP instance.
Methodology
The researchers framed algorithm selection as a supervised classification task, utilizing three distinct classifiers from the Weka suite: J48 (decision tree), MultilayerPerceptron (neural network), and NaiveBayes (probabilistic). Each CSP instance was characterized by 12 features, including $\kappa$ (kappa) to predict phase transitions, and measures of constraint tightness like relLinkage and relPerVar.
To optimize performance, four training strategies were evaluated:
- Original dataset: Standard training on all instances.
- Filtering: Removing "noisy" instances where the runtime difference was less than 100ms.
- Weighted: Incentivizing the model to prioritize instances with large runtime disparities.
- Cost Matrix: Explicitly penalizing the selection of the slower algorithm.
The study utilized 3,592 data instances derived from the 2008 CSP Solver Competition benchmarks. Large problems were broken down into clusters using tree decomposition, treating each cluster as an independent instance.
Key Insights
The Impact of Phase Transitions
The study highlighted that near the phase transition—where problems transition from easy to difficult—backtrack search becomes computationally expensive. In these regions, PerTuple’s multiple searches become a liability compared to AllSol’s single search strategy.
Utility Over Accuracy
A critical finding was that a high F-measure does not always correlate with maximum utility. A model might achieve high accuracy but fail on the few instances that account for the majority of total computation time. Consequently, the researchers prioritized "Time Saved" as the definitive success metric.
Experimental Results
The J48 classifier trained on the weighted dataset emerged as the most effective strategy. As shown in the performance table below, this approach achieved 99.96% of the potential time savings offered by a theoretical perfect oracle.
While PerTuple was faster in 2,462 instances compared to AllSol’s 1,130, the margins by which AllSol won were often significantly larger. The weighted J48 model successfully navigated these trade-offs, reducing the "time lost" (the penalty for incorrect selection) to just 6,320 ms across the entire test set.
Conclusion and Future Work
The research demonstrates that machine learning can nearly eliminate the overhead of suboptimal algorithm selection in CSPs. While the cost-matrix approach underperformed due to high variance in execution times, the weighted strategy proved robust. Future work will explore dynamic selection strategies—switching algorithms during the search process—and extending this methodology to automatically determine the optimal level of consistency for a given problem.
Summary updated