Decomposition During Search for Propagation-Based Constraint Solvers

Details Decomposition During Search for Propagation-Based Constraint Solvers Decomposition During Search for Propagation-Based Constraint Solvers

2007-12-14

arxiv.org/abs/0712.2389v2

Computer Science

Artificial Intelligence

20 pages, 9 figures, 2 tables; longer, more detailed version

Scientific paper

We describe decomposition during search (DDS), an integration 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 library. Two applications, solution counting in graph coloring and protein structure prediction, exemplify the benefits of DDS in practice.

Affiliated with

Also associated with

No associations

Rating

Decomposition During Search for Propagation-Based Constraint Solvers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Decomposition During Search for Propagation-Based Constraint Solvers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decomposition During Search for Propagation-Based Constraint Solvers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-662844