Integrating Heuristics for Constraint Satisfaction Problems: A Case Study

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.

Authors

• Steven Minton

Keywords

No keywords are indexed for this paper.