Counting-based search: branching heuristics for constraint satisfaction problems
From MaRDI portal
Abstract: 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.
Recommendations
Cited in
(29)- Branch \& Sample: A simple strategy for constraint satisfaction
- Accelerating counting-based search
- Branching constraint satisfaction problems and Markov decision problems compared
- Search heuristics for box decomposition methods
- Weight-based heuristics for constraint satisfaction and combinatorial optimization problems
- Counting weighted spanning trees to solve constrained minimum spanning tree problems
- Dynamic branching in qualitative constraint-based reasoning via counting local models
- A new branch-and-filter exact algorithm for binary constraint satisfaction problems
- Solution counting algorithms for constraint-centered search heuristics
- STR3: a path-optimal filtering algorithm for table constraints
- A constraint programming primer
- Achieving domain consistency and counting solutions for dispersion constraints
- Recovering indirect solution densities for counting-based branching heuristics
- Solution Counting Algorithms for Constraint-Centered Search Heuristics
- More robust counting-based search heuristics with alldifferent constraints
- CSPs with counters: a likelihood-based heuristic
- scientific article; zbMATH DE number 2080312 (Why is no real title available?)
- scientific article; zbMATH DE number 2080335 (Why is no real title available?)
- scientific article; zbMATH DE number 2084762 (Why is no real title available?)
- Using dual presolving reductions to reformulate cumulative constraints
- Shift-and-propagate
- Counting Solutions of Knapsack Constraints
- Learning value heuristics for constraint programming
- Recent Advances in Constraints
- Principles and Practice of Constraint Programming – CP 2004
- Principles and Practice of Constraint Programming – CP 2004
- Artificial Intelligence: Methodology, Systems, and Applications
- Optimization bounds from decision diagrams in Haddock
- Dynamic Branching in Qualitative Constraint Networks via Counting Local Models
This page was built for publication: Counting-based search: branching heuristics for constraint satisfaction problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2887069)
