1993 · 39 citations · 13 references
ComputingComputer ScienceAlgorithmsKnowledge RepresentationOptimizationConstrained OptimizationConstraint ProgrammingConstraint SatisfactionConstraint SolvingHeuristic OptimizationHeuristic SearchConstraint GenerationConstraint Optimization ProblemsCsp Search AlgorithmsCsp SolvingGeneric AlgorithmsHeuristics
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...
13
Algorithms for constraint-satisfaction problems: a survey
Vipin Kumar · 1992 · 891 citations
Explanation-based learning:A problem solving perspective
Steven Minton, Jaime Carbonell, Craig A. Knoblock et al. · Artificial Intelligence · 1989 · 226 citations