Counting-based search: branching heuristics for constraint satisfaction problems
From MaRDI portal
Publication:2887069
DOI10.1613/JAIR.3463zbMATH Open1237.68193arXiv1401.4601OpenAlexW2170780172WikidataQ129490055 ScholiaQ129490055MaRDI QIDQ2887069FDOQ2887069
Authors: Gilles Pesant, Claude-Guy Quimper, Alessandro Zanarini 
Publication date: 16 May 2012
Published in: The Journal of Artificial Intelligence Research (JAIR) (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1401.4601
Recommendations
Cited In (29)
- 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
- Artificial Intelligence: Methodology, Systems, and Applications
- A constraint programming primer
- Title not available (Why is that?)
- Branching constraint satisfaction problems and Markov decision problems compared
- 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
- Optimization bounds from decision diagrams in Haddock
- More robust counting-based search heuristics with alldifferent constraints
- Title not available (Why is that?)
- Title not available (Why is that?)
- Recovering indirect solution densities for counting-based branching heuristics
- Weight-based heuristics for constraint satisfaction and combinatorial optimization problems
- 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
- Learning value heuristics for constraint programming
- A new branch-and-filter exact algorithm for binary constraint satisfaction problems
- Search heuristics for box decomposition methods
- Principles and Practice of Constraint Programming – CP 2004
- 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)
