Computer Science – Artificial Intelligence
Scientific paper
2010-08-03
In Proceedings of the 19th European Conference on Artificial Intelligence - ECAI 2010
Computer Science
Artificial Intelligence
To appear in Proceedings of the 19th European Conference on Artificial Intelligence - ECAI 2010
Scientific paper
10.3233/978-1-60750-606-5-855
The two standard branching schemes for CSPs are d-way and 2-way branching. Although it has been shown that in theory the latter can be exponentially more effective than the former, there is a lack of empirical evidence showing such differences. To investigate this, we initially make an experimental comparison of the two branching schemes over a wide range of benchmarks. Experimental results verify the theoretical gap between d-way and 2-way branching as we move from a simple variable ordering heuristic like dom to more sophisticated ones like dom/ddeg. However, perhaps surprisingly, experiments also show that when state-of-the-art variable ordering heuristics like dom/wdeg are used then d-way can be clearly more efficient than 2-way branching in many cases. Motivated by this observation, we develop two generic heuristics that can be applied at certain points during search to decide whether 2-way branching or a restricted version of 2-way branching, which is close to d-way branching, will be followed. The application of these heuristics results in an adaptive branching scheme. Experiments with instantiations of the two generic heuristics confirm that search with adaptive branching outperforms search with a fixed branching scheme on a wide range of problems.
Balafoutis Thanasis
Stergiou Kostas
No associations
LandOfFree
Adaptive Branching for Constraint Satisfaction Problems 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 Adaptive Branching for Constraint Satisfaction Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive Branching for Constraint Satisfaction Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-81965