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.
Code (0)
등록된 구현이 없습니다.
Tasks
SchedulingSimilar Papers 제목 키워드 기반
Learning Branching Heuristics from Graph Neural Networks
Backtracking has been widely used for solving problems in artificial intelligence (AI), including constraint satisfaction problems and combinatorial optimization problems. Good branching heuristics can efficiently improv…
Combinatorial OptimizationGraph Neural NetworkStreamlining Variational Inference for Constraint Satisfaction Problems
Several algorithms for solving constraint satisfaction problems are based on survey propagation, a variational inference scheme used to obtain approximate marginal probability estimates for variable assignments. These ma…
SurveyVariational InferenceLearning Branching Heuristics for Propositional Model Counting
Propositional model counting, or #SAT, is the problem of computing the number of satisfying assignments of a Boolean formula. Many problems from different application areas, including many discrete probabilistic inferenc…
modelLearning Variable Ordering Heuristics for Solving Constraint Satisfaction Problems
Backtracking search algorithms are often used to solve the Constraint Satisfaction Problem (CSP). The efficiency of backtracking search depends greatly on the variable ordering heuristics. Currently, the most commonly us…
Deep Reinforcement LearningGraph Neural NetworkReinforcement LearningCounting the Number of Solutions to Constraints
Compared with constraint satisfaction problems, counting problems have received less attention. In this paper, we survey research works on the problems of counting the number of solutions to constraints. The constraints …
Survey