Introduction: The Propagation Trade-off
In Constraint Programming (CP), solvers rely on "propagation" to prune the search space by removing values from variable domains that cannot participate in a valid solution. This process involves a fundamental trade-off: weak propagation methods, such as Arc Consistency (AC), are computationally inexpensive but offer limited pruning. Conversely, stronger methods like Partition One-Arc Consistency (POAC) prune the search space aggressively but incur significant computational overhead.
Historically, selecting the optimal propagation level required manual expert tuning or static heuristics. However, the ideal level of consistency often shifts depending on the specific problem instance and even the current depth within the search tree. This paper introduces an automated, "plug-and-play" framework that uses Multi-Armed Bandits (MAB) to dynamically select the most efficient propagation level during search without requiring offline training.
The MAB Framework for Adaptive Selection
The authors frame the selection of a propagation level as a Multi-Armed Bandit problem, where different local consistency algorithms (e.g., AC, maxRPC, POAC) act as the "arms."
Depth-Specific Selectors
A key insight of this work is that context matters. The effectiveness of a propagator at the root of the search tree rarely matches its effectiveness near the leaves. To address this, the framework places a separate MAB selector at each depth of the search tree. This allows the solver to evolve a custom "propagation schedule" tailored to the specific problem's structure.
Reward and Policy
To balance exploration and exploitation, the system employs the UCB1 algorithm. The reward function is the "secret sauce" of the approach: it accounts for both the immediate CPU time required for propagation and the time spent exploring the resulting subtree. This ensures that the MAB recognizes the long-term benefits of heavy pruning, even if the initial propagation step is slow.
As shown in the learning curves above, the system dynamically adjusts the selection ratio of different arms based on their observed mean rewards, eventually converging on the most effective strategies for the given context.
Experimental Evaluation
The researchers evaluated the MAB-based solver on 313 instances from the CRIL repository, covering a diverse range of structured, random, and graph-based problems.
Superior Coverage and Speed
The adaptive method utilizing all three consistencies (AC-maxRPC-POAC) demonstrated superior performance, solving 309 out of 313 instances. This outperformed the best single-consistency method, which solved only 296 instances.
As illustrated in Figure 1, the MAB-based approaches (represented by the upper dotted and dashed curves) consistently solve more instances faster than static methods. On difficult instances, the speedups were substantial; for example, the total time for the AC-maxRPC-POAC method was approximately 11,104 seconds, compared to 25,599 seconds for standard Arc Consistency.
Conclusion and Future Work
The MAB framework provides a robust safety net for CP solvers. If a strong consistency level performs poorly on a specific problem, the MAB quickly learns to deprioritize it, preventing the solver from becoming bogged down by high overhead.
While UCB1 is effective, future work could explore more granular selection (e.g., per-constraint selectors) or advanced reinforcement learning techniques like Q-learning to better model the dependencies between choices made at different search depths. Currently, the "learning lag" inherent in exploration means that for extremely simple problems solved in seconds, the overhead of the MAB might slightly exceed the benefits, though it remains a powerful tool for complex, real-world constraints.
Summary updated