Relative Support Weight Learning for Constraint Solving

Smiljana Petrovic, Susan Epstein

Many real-world problems can be represented and solved as constraint satisfaction problems, but their solution requires the development of effective, efficient constraint solvers. A constraint salver's success depends greatly upon the heuristics chosen to guide search. Some heuristics perform well on one class of problems, but are less successful on others. The solver described here learns a weighted combination of heuristic recommendations customized for a given class of problems. A pre-existing algorithm has weights learned for heuristics from the number of nodes explored during learning. We present here a new algorithm which learns weights for heuristics that consider the nuances of relative support for actions. The resultant performance is statistically significantly better than that of traditional individual heuristics.

Subjects: 15.2 Constraint Satisfaction

Submitted: May 17, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.