Name
Abstract | ||
|---|---|---|
We describe decomposition during search (DDS), an integra- tion of And/Or tree search into propagation-based constraint solvers. The presented search algorithm dynamically decomposes sub-problems of a constraint satisfaction problem into independent partial problems, avoiding redundant work. The paper discusses how DDS interacts with key features that make propagation-based solvers successful: constraint propagation, especially for global constraints, and dynamic search heuristics. We have implemented DDS for the Gecode constraint programming li- brary. Two applications, solution counting in graph coloring and protein structure prediction, exemplify the benefits of DDS in practice. |
Year | Venue | Keywords |
|---|---|---|
2007 | Clinical Orthopaedics and Related Research | constraint programming,artificial intelligent,protein structure prediction,graph coloring,constraint satisfaction problem,constraint propagation,search algorithm |
Field | DocType | Volume |
Computer science,Theoretical computer science,Artificial intelligence,Constraint logic programming,Constraint satisfaction,Mathematical optimization,Local consistency,Constraint programming,Constraint graph,Constraint satisfaction problem,Machine learning,Hybrid algorithm (constraint satisfaction),Binary constraint | Journal | abs/0712.2 |
Citations | PageRank | References |
3 | 0.54 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Mann | 1 | 130 | 9.59 |
| Guido Tack | 2 | 377 | 27.56 |
| Sebastian Will | 3 | 538 | 29.98 |