Counting-Based Search: Branching Heuristics for Constraint Satisfaction
  Problems
  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.
