Integrating Heuristics for Constraint Satisfaction Problems: A Case Study

Steven Minton

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.

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.