Integrating Heuristics for Constraint Satisfaction Problems: A Case Study

Abstract

This paper describes a set of experiments with a system that synthesizes constraint satisfaction programs. The system, Multi-tac, is a CSP "expert " that can specialize a library of generic algorithms and methods for a particular application. Multi-tac not only proposes domain-specific versions of its generic heuristics, but also searches for the best combination of these heuristics and integrates them into a complete problem-specific program. We demonstrate Multi-tac's capabilities on a combinatorial problem, "Minimum Maximal Matching", and show that Multi-tac can synthesize programs for this problem that are on par with hand-coded programs. In synthesizing a program, Multi-tac bases its choice of heuristics on the instance distribution, and we show that this capability has a significant impact on the results. Introduction AI research on constraint satisfaction has primarily focused on developing new heuristic methods. Invariably, in pursuing new techniques, a tension arises betwe...