Using mini-bucket heuristics for max-csp

This paper evaluates the power of a new scheme that generates search heuristics mechanically. This approach was presented and evaluated rst in the context of optimization in belief networks. In this paper we extend this work to Max-CSP. The approach involves extracting heuristics from a parameterized approximation scheme called Mini-Bucket elimination that allows controlled trade-o between computation and accuracy. The heuristics are used to guide Branch-and-Bound and Best-First search, whose performance are compared on a number of constraint problems. Our results demonstrate that both search schemes exploit the heuristics e ectively, permitting controlled trade-o between preprocessing (for heuristic generation) and search.