TL;DR
This paper introduces "Disco-Novo-GoGo," a hybrid algorithm that combines randomized complete search with a novel local search technique. By learning and adapting value selection heuristics across restarts, it significantly speeds up the search for solutions in under-constrained problems, achieving orders-of-magnitude improvements.
What Problem Does This Paper Address?
Solving complex computational problems often involves a trade-off between two main approaches: complete search (like backtracking) and local search. Complete search guarantees finding a solution if one exists and can prove unsatisfiability, but it can be prohibitively slow on "under-constrained" problems (where many solutions exist). Local search, on the other hand, is much faster on these problems but cannot guarantee finding a solution or proving unsatisfiability. Researchers have long sought ways to combine their strengths. This paper specifically addresses the challenge of making complete search methods more efficient on under-constrained problems without sacrificing their completeness. The authors observe that while random variable selection can help, a good value selection heuristic can guide the search effectively regardless of how the problem space is partitioned.
Methods
The core of the proposed method, "Disco-Novo-GoGo," lies in its hybrid approach to systematic search. Instead of relying on fixed heuristics, it dynamically learns and improves its value selection strategy over multiple restarts.
Here's a breakdown:
- Randomized Variable Selection: The algorithm uses random choices for selecting which variable to branch on. This is a common technique to avoid getting stuck in specific search paths.
- Restarts: When the search reaches a predefined limit (fail-limit) without finding a solution, it restarts. This is a standard strategy for dealing with heavy-tailed runtime distributions common in hard problems.
- Learning Value Heuristics: This is the novel contribution. After a restart fails, the algorithm analyzes the search path. If a chosen value for a variable was inconsistent (e.g., led to a dead end or was pruned by constraint propagation), the heuristic for that variable is updated. Specifically, if the current heuristic's preferred value is no longer in the variable's domain, a new random value is chosen as the next "first choice." This is described as a "coarse-grained local search" where the heuristic itself is the object being optimized.
- Meta-Restarts: To isolate the effect of the heuristic learning from the restart strategy itself, a "meta-restart" mechanism is introduced. This resets the fail-limit and randomly re-initializes the heuristic, allowing for a clean evaluation of the learning process.
Datasets
The paper evaluates the proposed method on two types of problems:
- Diagonally Ordered Magic Squares (DOMS): These are modeled as constraint programming problems. The instances vary in size from 3x3 to 12x12.
- Satisfiability (SAT) Instances:
- Randomly generated 5-SAT instances with 600 variables and varying numbers of clauses.
- Quasigroup Completion Problem (QCP) instances, which are known to be challenging and have a structured nature. These instances vary in order (from 38x38 to 44x44) and number of holes.
Key Insights and Ideas
- Heuristic Learning as a Form of Local Search: The paper frames the process of updating value selection heuristics across restarts as a form of "coarse-grained local search." This is a powerful conceptual link, suggesting that optimization techniques from local search can be applied to improve systematic search components.
- Complementary to No-Goods: The learned value heuristics are presented as complementary to "no-goods" (learned unsatisfiable clauses). While no-goods prune parts of the search space that cannot contain solutions, learned heuristics guide the search towards parts that are likely to contain solutions.
- Effective on Under-Constrained Problems: The core insight is that for problems with many solutions, a good value heuristic can drastically reduce the search effort, even if the variable ordering is random. This is where the method shines.
- Robustness on Tightly Constrained Problems: Importantly, the method doesn't significantly harm performance on more constrained problems where local search is less effective. This suggests a general-purpose improvement.
Key Results
- Orders-of-Magnitude Speedups: The Disco-Novo-GoGo method (specifically the MRH variant) achieved speedups of roughly 20 times on Diagonally Ordered Magic Squares of order 12 compared to traditional methods.
- Reduced Restarts: The heuristic learning significantly reduced the number of restarts needed, by an order of magnitude compared to a basic hybrid approach and by a factor of 2 compared to a traditional method with exponential fail-limit growth.
- SAT Instance Performance: On SAT instances, the hybrid methods were up to 7 times faster than their traditional counterparts. For larger instances, speedups reached an order of magnitude.
- QCP Performance: Even on structured QCP instances, the hybrid methods consistently outperformed traditional ones, with speedups becoming more pronounced as instances became less constrained. For example, BH-linear outperformed TR-linear by a factor of 10 on certain QCP instances.
- No Performance Degradation: On tightly constrained problems (like Dumbledore Squares), the performance of the hybrid method was comparable to traditional methods, indicating no significant overhead.
Limitations and Future Work
- Heuristic Update Granularity: The authors acknowledge that the current heuristic update is conservative. Future work could explore more sophisticated update mechanisms, such as keeping statistics on value domain consistency or maintaining orderings of values for each variable rather than just the first choice.
- Explaining BH-linear Outperforming BH-exp: The paper notes that BH-linear (linear fail-limit growth) outperformed BH-exp (exponential fail-limit growth) on SAT instances, which is counter-intuitive. They speculate this might be due to faster restarts benefiting the local search component more, but suggest more research is needed to fully understand this.
- Generalizability: While tested on CP and SAT problems, further exploration on other problem domains could be beneficial.
Summary updated