Activity-Based Search for Black-Box Contraint-Programming Solvers

Laurent D. Michel, Pascal Van Hentenryck

Abstract

Constraint Programming (CP) is evolving from expert-tuned models toward "black-box" solvers that require minimal manual intervention. This paper introduces Activity-Based Search (ABS), a robust heuristic that tracks the frequency of variable domain pruning during propagation to guide search. Evaluations across diverse benchmarks show that ABS is more stable and often significantly faster than industry standards such as Impact-Based Search (IBS) and Weighted-Degree (wdeg) heuristics.

Introduction

Historically, CP required manual design of search strategies, creating a high barrier to entry compared to SAT or Mixed-Integer Programming (MIP) solvers. The challenge in building a black-box CP solver lies in creating a robust search procedure that performs efficiently across varied problem types without manual tuning. Existing methods like IBS are computationally expensive to initialize, while others like wdeg can be "blinded" by global constraints. ABS aims to provide a computationally light and effective middle ground.

Methodology

The core of ABS is its focus on constraint propagation—the process of removing values from a variable's domain that cannot be part of a solution.

  1. Activity Tracking: ABS maintains a counter for each variable, incremented whenever its domain is reduced during propagation.
  2. Aging Mechanism: A decay parameter ($\gamma$) is used to "forget" older activity, allowing the solver to adapt to the current search state.
  3. Probing: Before the main search, ABS performs random "probes" to gather initial statistics and avoid starting "blind."
  4. Selection Criteria: The solver selects variables with the highest Activity / Domain Size ratio, targeting active variables with many remaining possibilities.

Experimental Evaluation

The authors evaluated ABS on classic and complex benchmarks, including Multi-Knapsack, Magic Squares, the Progressive Party Problem, Nurse Rostering, and Radiation Therapy.

Results and Discussion

ABS demonstrated superior robustness and speed across the test suite. On the Multi-Knapsack problem, as difficulty increased, the performance of the wdeg heuristic degraded significantly, while ABS remained stable and efficient.

Performance scaling on Knapsack benchmarks comparing wdeg (W), IBS (I), and ABS (A).

Quantitatively, ABS often outperformed IBS by a factor of five or more. For instance, in the 1-4 benchmark variant for Constraint Optimization Problems (COP), ABS achieved a mean search time of 26.16 seconds compared to 200.96 seconds for IBS, as shown in the table below.

Mean search time and standard deviation for ABS, IBS, and wDEG across benchmarks.

Key insights from the study suggest that propagation frequency is a more effective signal for variable importance than failure counts alone. Furthermore, the simplicity of ABS makes it more memory-efficient and scalable for problems with large domains.

Conclusion

ABS proves to be a consistent performer, making it an ideal candidate for default search in general-purpose CP solvers. While sensitive to internal parameters like the decay rate and probing depth, its ability to "dive" to optimal solutions quickly highlights its potential for real-world optimization. Future work will explore dynamic re-initialization and interactions with different levels of constraint consistency.

Summary updated

BibTeX
@misc{michel2011activity,
  author = {Laurent D. Michel and Pascal Van Hentenryck},
  title = {{Activity-Based Search for Black-Box Contraint-Programming Solvers}},
  year = {2011},
  eprint = {1105.6314},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1105.6314},
}
Figure