Relative Support Weight Learning for Constraint Solving

Contents

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.