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