Counting-Based Search: Branching Heuristics for Constraint Satisfaction Problems
This addresses the challenge of creating robust branching heuristics for constraint satisfaction problems, which is important for practitioners in fields like scheduling and puzzles, though it appears incremental as it builds on existing counting-based ideas.
The paper tackled the problem of designing reliable search heuristics for constraint programming across domains by proposing counting-based search, which uses global constraint-level information to preserve solutions, and found that it generally outperforms state-of-the-art generic heuristics in experiments across eight problem domains.
Designing a search heuristic for constraint programming that is reliable across problem domains has been an important research topic in recent years. This paper concentrates on one family of candidates: counting-based search. Such heuristics seek to make branching decisions that preserve most of the solutions by determining what proportion of solutions to each individual constraint agree with that decision. Whereas most generic search heuristics in constraint programming rely on local information at the level of the individual variable, our search heuristics are based on more global information at the constraint level. We design several algorithms that are used to count the number of solutions to specific families of constraints and propose some search heuristics exploiting such information. The experimental part of the paper considers eight problem domains ranging from well-established benchmark puzzles to rostering and sport scheduling. An initial empirical analysis identifies heuristic maxSD as a robust candidate among our proposals.eWe then evaluate the latter against the state of the art, including the latest generic search heuristics, restarts, and discrepancy-based tree traversals. Experimental results show that counting-based search generally outperforms other generic heuristics.