Learning Robust Search Strategies Using a Bandit-Based Approach

Wei Xia, Roland H. C. YapAAAI 2018 · DOI

Introduction: The Challenge of Heuristic Selection

In Constraint Programming (CP), solving complex combinatorial problems—ranging from scheduling and routing to resource allocation—requires a search strategy to navigate vast decision trees. A critical component of this strategy is the variable ordering heuristic, which determines the sequence in which variables are assigned values. While powerful heuristics like wdeg/dom, activity, and impact have been developed, they suffer from a lack of universality. A heuristic that performs exceptionally well on one problem instance may fail catastrophically on another, leading to massive fluctuations in solving time.

Traditionally, selecting the optimal heuristic required deep domain expertise or exhaustive trial-and-error. Furthermore, the effectiveness of a heuristic can shift during the search process; a strategy that is efficient at the root of the tree may become a bottleneck as the solver explores deeper subproblems. This paper addresses these challenges by proposing an online, adaptive framework that automatically selects the best heuristic in real-time.

The authors frame the selection of variable ordering heuristics as a Multi-Armed Bandit (MAB) problem. In this model, the solver acts as an agent that must choose between several "arms," where each arm represents a candidate heuristic (e.g., ddeg/dom, wdeg/dom, impact, and activity).

The Reward Mechanism

The core of any MAB approach is the reward function. In this context, the goal is to minimize the size of the search tree. The authors define the reward based on the branching factor: choosing a heuristic that generates fewer children at a specific node results in a higher reward. This encourages the solver to favor strategies that prune the search space more effectively.

Algorithms: UCB1 and Thompson Sampling

The framework utilizes two well-known MAB algorithms:

  1. UCB1 (Upper Confidence Bound): A deterministic algorithm that balances exploitation (choosing the heuristic with the highest known average reward) and exploration (trying less-frequently used heuristics to refine reward estimates).
  2. Thompson Sampling (TS): A stochastic approach that maintains a probability distribution for each heuristic's success, allowing for a more nuanced exploration strategy.

Unlike traditional portfolio methods that require extensive offline training on historical data, this approach is purely online. The solver begins with no prior knowledge and learns the optimal strategy specifically for the instance it is currently solving.

Key Results: Solving Power and Robustness

The experimental results, conducted using the AbsCon solver on 363 problem instances, highlight two primary advantages of the bandit-based approach: raw solving power and, more importantly, robustness.

Solving time vs. number of instances solved across all benchmarks.

As shown in the timing data, the MAB-based solvers—particularly the Thompson Sampling variant with a sliding window (TS-500)—solved the highest total number of instances (328 out of 363), outperforming all individual fixed heuristics.

However, the most significant finding is the improvement in robustness. Fixed heuristics often exhibit "heavy-tailed" performance, where they solve most problems quickly but take an exorbitant amount of time on a few specific instances. The MAB approach mitigates this risk by dynamically shifting away from poorly performing strategies.

Runtime ratios relative to the virtual best solver.

By analyzing the runtime ratios relative to a "Virtual Best Solver" (a theoretical optimum), the authors found that UCB1 was remarkably stable. While traditional heuristics like wdeg/dom had maximum runtime ratios exceeding 4600, UCB1’s maximum ratio was only 120.7. This indicates that the bandit-based solver consistently avoids the worst-case performance traps that plague static strategies.

Insights and Future Directions

The study reveals that the "best" heuristic often changes as the search progresses. Sliding window versions of the algorithms (UCB1-K and TS-K) allow the solver to "forget" outdated rewards and adapt to the current state of the search tree, further enhancing performance. Interestingly, even a simple "random-arm" baseline performed reasonably well, suggesting that simply mixing strategies provides a natural defense against search cost variability.

While the approach introduces some computational overhead—as the solver must track scores for multiple heuristics—the gains in reliability and solving power are substantial. Future work may extend this framework to include value ordering heuristics and dynamic selection of constraint propagation levels, moving closer to a truly autonomous, "black-box" CP solver.

Summary updated

BibTeX
@inproceedings{xia2018learning,
  author = {Wei Xia and Roland H. C. Yap},
  title = {{Learning Robust Search Strategies Using a Bandit-Based Approach}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.12211},
}
Figure