PaperlayerView exact revision on arXiv

Source-linked AI summary

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

L. Michel, P. Van Hentenryck

arXiv:1105.6314v1cs.AIcs.MS

TL;DR

Black-box CP solvers seek robust search procedures that reduce the burden of specialized search. This paper proposes activity-based search, which uses variable activity during propagation to guide decisions. Across varied benchmarks, it was more robust than Ibs and wdeg and often improved performance.

  • Problem

    Black-box constraint-programming solvers need robust search procedures, while specialized modeling and search can place a significant burden on practitioners.

    Source: §1 · p. 1

  • Method

    Activity-based search guides decisions with variable activity during propagation, updating activity during search and initializing it through sampling.

    Source: §1 · pp. 1–2, §6 · p. 15

  • Results

    Abs was significantly more robust than Ibs and wdeg across the tested benchmark classes and often produced significant performance improvements.

    Source: §5.2 · pp. 8, 12, §6 · p. 15

  • Takeaways & Limitations

    Abs was reported as robust across benchmarks and restart strategies and, in general, the fastest heuristic on the benchmark collection.

    Source: §5.2 · p. 12

    Activity levels may not be a good indicator of progress and may bias search toward certain variables.

    Source: §5.4 · p. 14

Abstract

from arXiv · show

Robust search procedures are a central component in the design of black-box constraint-programming solvers. This paper proposes activity-based search, the idea of using the activity of variables during propagation to guide the search. Activity-based search was compared experimentally to impact-based search and the WDEG heuristics. Experimental results on a variety of benchmarks show that activity-based search is more robust than other heuristics and may produce significant improvements in performance.

1 Introduction

Black-box CP solvers aim to reduce the burden of specialized search, making robust general-purpose search procedures an important research focus.

1 Introduction

  • Black-box solvers seek to let practitioners focus on modeling, in contrast to CP tools whose flexibility can place a significant burden on users.The paper relates this shift to the success of MIP and SAT solvers with automatic reformulations and general-purpose search.Source: §1 · p. 1
  • Prior approaches to robust search include Ibs, solution-counting alternatives to impacts, and wdeg, which adapts SAT Vsids using failure information.The paper identifies Ibs with MIP concepts such as strong branching and pseudo-costs.Source: §1 · p. 1
  • Abs guides search using variable activity during propagation, updating counters systematically and initializing them through probing.It avoids explicit domain handling and constraint instrumentation, and naturally handles global constraints.Source: §1 · pp. 1–2
  • Across varied benchmarks, Abs was reported as more robust than Ibs and wdeg and often improved performance, especially as problem complexity increased.The paper also describes Abs as robust across benchmarks and restart strategies and generally the fastest heuristic.Source: §1 · p. 2

2 Impact-Based Search

Impact-based search estimates how branching assignments contract the search space, then uses those estimates to select variables and values.

2 Impact-Based Search

  • An impact measures how effectively a branching assignment shrinks the search space; a failure yields zero remaining solutions, while little domain reduction implies little impact.A branch is formed by adding an assignment and propagating the resulting CSP.Source: §2 · p. 2
  • The engine parameter α controls impact memory: α = 1 yields a forgetful strategy, α = 2 gives a running average that progressively decays past impacts, and α > 2 favors past information over most recent observations.Source: §2 · p. 3
  • At the root, Ibs simulates assignments to initialize impacts; partitioning large domains reduces propagation work, while storage remains Θ(∑x∈X |D(x)|).With domain values partitioned into b blocks, initialization uses b propagations rather than |D(x)| for that variable.Source: §2 · p. 3
  • Ibs selects the variable with the largest estimated impact and then the value with the smallest estimated assignment impact, breaking ties uniformly at random.The variable impact is estimated from assignment impacts.Source: §2 · p. 3
  • Ibs can restart by limiting failures in each round and multiplying the next round's limit by ρ, where ρ > 1.The initial failure limit is l_i and the next is l_i+1 = ρ · l_i.Source: §2 · p. 3

3 The WDEG Heuristic

The wdeg heuristic uses failures of constraints to update weights that inform variable selection.

3 The WDEG Heuristic

  • wdeg maintains a weight for each constraint, incremented when its propagation removes all values from a variable's domain.The weights count how often variables appear in failed constraints.Source: §3 · p. 3
  • The weighted-degree definition uses FutVars(c), the set of uninstantiated variables in constraint c.The passage introduces this set in the context of the weighted-degree formula.Source: §3 · p. 3
  • wdeg selects the variable with the smallest ratio of domain size to weighted degree; all constraint weights start at 1.Its space overhead is Θ(|C|) for a CSP with constraint set C.Source: §3 · p. 3

4 Activity-Based Search

Activity-based search tracks propagation-driven variable activity, optionally tracks assignment activity, and uses these measures to order variables and values. It initializes activity by probing and updates it with decay during search.

4 Activity-Based Search

  • Abs is simple, needs no sophisticated constraint instrumentation, scales to large domains, and is domain-size-independent when value selection is unused.It also does not favor variables appearing in failed constraints, since CP failures typically follow many filtering algorithms.Source: §4 · p. 4
  • At each search node, free variables decay by γ and variables affected by propagation gain one activity unit.Per-variable activity uses Θ(|X|) space; the decaying sum progressively forgets older statistics.Source: §4 · p. 4
  • An assignment's activity counts variables affected by propagation, and its tree-wide estimate averages that count over visited nodes.Source: §4 · p. 4
  • Abs selects the variable with the largest activity-to-domain-size ratio and, optionally, the value with least assignment activity.When value selection is unused, its assignment-activity statistics need not be maintained; after restarts, activities can be used as-is.Source: §4 · p. 5
  • Initialization samples search paths by choosing free variables and values uniformly; probe updates omit aging so each probe contributes equally.Probes may terminate at a failure or reach a solution.Source: §4 · pp. 5–6
  • Probing stops when each variable’s 95% t-based confidence interval is sufficiently narrow, such as within δ% of its empirical mean.Probe statistics are computed incrementally without additional space requirements.Source: §4 · p. 6

5 Experimental Results

Across the benchmark collection, Abs is the most robust and generally fastest heuristic, with performance varying by benchmark and restart strategy. Experiments compare Ibs, wdeg, and Abs across benchmarks, restart settings, and sensitivity parameters.

5.2 The Core Results

  • On difficult multi-knapsack instances, Abs is the most robust and improves performance in both decision and optimization variants.For decision instance 1−6, Abs always finds solutions and is about five times faster than Ibs with no restarts; it finds solutions in all 50 runs for optimization instance 1−5, unlike wdeg.Source: §5.2 · p. 8
  • On magic squares, wdeg is poor and non-robust; Abs slightly improves on Ibs with fast restarts, while Ibs is more effective with slow or no restarts.For the progressive-party benchmark, Abs dominates Ibs under all restart strategies, but is slightly slower than wdeg with fast or slow restarts.Source: §5.2 · p. 9
  • Abs dominates Ibs on radiation and is robust on nurse rostering, while its advantage over wdeg depends on benchmark and restart strategy.On radiation, both Abs and wdeg are effective and clearly superior to Ibs; on nurse rostering, Abs solves every instance in every run, while wdeg times out systematically beyond z5.Source: §5.2 · pp. 9–12
  • Abs is the most robust across benchmarks and restart strategies and is generally the fastest heuristic.wdeg has robustness and performance issues on multi-knapsack, magic squares, and nurse rostering; Ibs has robustness issues on radiation, some rostering instances, and large knapsack optimization instances.Source: §5.2 · p. 12

5.3 Sensitivity Analysis

  • More initialization probes generally improve robustness and bring mean and median runtimes closer, but δ = 0.2 is judged a reasonable compromise.At δ = 0.05, msq-10 still shows variance; the mean decreases with more probes on msq-10 but increases on knap1-4 as probe time grows.Source: §5.3 · p. 12
  • Slow aging is desirable overall; on msq-10, timeouts rise from zero at γ = 0.999 to nine at γ = 0.5.Source: §5.3 · p. 13

5.4 Some Behavioral Observations

  • On radiation-9, Abs quickly reaches the optimum and spends the remaining time proving optimality, while restarts hurt Ibs.Abs hits the optimum within three seconds without restarts and within one second with restarts; Ibs reaches it slowly, then proves optimality quickly.Source: §5.4 · p. 13
  • On radiation-9, probing isolates a small subset of variables with very high activity, though a backdoor or cycle-cutset explanation remains conjectural.The authors state that more experiments are needed to confirm or disprove that conjecture.Source: §5.4 · p. 14

6 Conclusion

Activity-based search guides constraint-programming search with variable activity during propagation. On the evaluated benchmark classes, it was more robust than impact-based search and weighted-degree search, and often improved performance.

6 Conclusion

  • Activity-based search was significantly more robust than impact-based and weighted-degree search across the evaluated benchmark classes.It often produced significant performance improvements.Source: §6 · p. 15
  • A variable’s activity increases whenever propagation filters its domain and is aged otherwise.Source: §6 · p. 15
  • A sampling process initializes variable activities before search begins.Source: §6 · p. 15
Loading 1105.6314v1…