Intelligent Constraint Solving: Predicting the Best Propagation Method via Machine Learning

TL;DR

Is there a "one size fits all" algorithm for Constraint Satisfaction Problems (CSPs)? The answer is a resounding no. This paper addresses this by building a metareasoning framework that uses machine learning to look at a CSP's structure and decide—within milliseconds—whether to use Forward Checking (FC) or Arc Consistency (AC-3). The result is a solver that performs nearly as well as a perfect "oracle."

The Problem: The Algorithm Selection Dilemma

In the world of CSPs (scheduling, layout, logic puzzles), we have a library of propagation techniques. Forward Checking (FC) is simple and fast per node but explores more of the tree; Arc Consistency (AC) is computationally heavier but prunes the search space more aggressively.

The performance gap between these methods isn't just a few percentage points—it can be orders of magnitude. Prior work like SATzilla proved that portfolios work for SAT, but the question remained: Can we efficiently predict the right propagator for a specific CSP instance without the prediction overhead eating up all our time savings?

Methodology: High-Speed Meta-Analysis

The authors treated algorithm selection as a classification task.

1. Feature Extraction: They identified 24 attributes of CSPs, ranging from simple stats (number of variables $n$, domain size $m$) to graph-theoretic measures (constraint graph width).
2. Dataset Diversity: They tested on three distinct classes:
   • Random Problems: Unstructured, following specific density/tightness parameters.
   • Small World Problems: Structured graphs mimicking real-world networks.
   • Quasigroups with Holes (QWH): Latent structure similar to Sudoku.
3. Cost-Sensitive Learning: Not all mistakes are equal! Misclassifying a problem where AC and FC take roughly the same time is fine. Misclassifying a problem where AC takes 1 second and FC takes 30 minutes is a disaster. They weighted the training of the j48 Decision Tree to minimize the "time-lost" cost.

Table 1: The underlying distribution shows that FC is often preferred in random sets, while AC excels in QWH.

Why Decisions Trees?

The authors found that decision trees outperformed Neural Networks and Naive Bayes for this specific task. Furthermore, decision trees are interpretable and fast. A tree 10 levels deep translates to a few if-else statements in code, making the reasoning time ($t_r$) virtually zero.

Results & The "Oracle" Benchmark

A key highlight is the performance compared to an Oracle—a hypothetical entity that always picks the best solver with zero overhead.

Table 4: Comparing standardized solvers against the metareasoner ($t_{as}+t_{ps}$).

• Heterogeneous Efficiency: The metareasoner significantly outperformed any single solver on the "All Problems" set.
• Minimal Overhead: By using the "Expert" subset of attributes (like $n,m,p1,p2,au$), the feature extraction time ($t_{as}$) was reduced to a fraction of a millisecond.
• Near-Optimal Performance: The relative error compared to the Oracle was just 1.9%.

Critical Insight: The Value of "Hard" Problems

The authors discovered that as problems get "harder" (longer runtimes), the classifier's accuracy actually increases. This is excellent news for practical applications: machine learning is most accurate exactly when it matters most—on the complex instances that would otherwise crush a standard solver.

Conclusion & Future Look

While this study limited itself to AC and FC, the implications are much broader. In a world where state-of-the-art solvers (like Choco or Google OR-Tools) have hundreds of parameters and heuristics, automated per-instance configuration is the next frontier.

The main limitation? The study excludes instances exceeding a 30-minute timeout. Future research should investigate if these "extreme" problems follow the same structural patterns or if they require fundamentally different features to predict.

Takeaway for Practitioners

If you are building a CSP-based system, don't settle for a default propagator. Even a simple decision tree based on basic problem statistics can slash your compute costs by ensuring you aren't using a "heavy" propagator on a "light" problem, or vice versa.