An Analytic Learning System for Specializing Heuristics

Steven MintonIJCAI 1993

Introduction

Solving combinatorial NP-hard problems, such as factory scheduling or graph coloring, typically involves a trade-off between the ease of using generic solvers and the performance of hand-tuned, problem-specific programs. While generic solvers are versatile, they often lack the efficiency required for large-scale instances. Conversely, custom heuristics are fast but labor-intensive to develop.

MULTI-TAC (Multi-Tactic Analytic Compiler) addresses this gap by automatically translating generic search heuristics into highly efficient, problem-specific code. Unlike previous "speed-up learning" approaches like Explanation-Based Learning (EBL), which primarily focus on caching specific solutions, MULTI-TAC employs meta-level reasoning to derive optimizations applicable across all instances of a problem class.

The MULTI-TAC Methodology

The system takes a problem specification in first-order logic and a set of sample instances as input. Its core innovation lies in a three-step process driven by meta-level theories.

1. Operationalization

In this stage, MULTI-TAC takes a generic heuristic—such as "Most-Constrained-Variable-First"—and uses its meta-theories to derive a specialized version. For instance, in a graph coloring problem, the system might mathematically simplify a general rule into a specific instruction: "count how many neighbors can still be colored with the current color."

The specialization process: a generic heuristic is expanded, specialized, and simplified into efficient problem-specific logic.

By reasoning about the structure of constraints, MULTI-TAC discovers optimizations that apply generally. This inferential process avoids the limitations of caching, which is often ineffective in massive search spaces where exact problem states rarely repeat.

2. Utility Evaluation

Since the effectiveness of a heuristic can vary based on data distribution, MULTI-TAC generates a library of candidate rules. It then employs a hill-climbing search to test various combinations on training instances, selecting the most effective configuration for the specific problem domain.

3. Compilation

Finally, the system compiles the selected heuristics and the search engine into a tailored Lisp program. This automated synthesis often results in code that rivals or exceeds the performance of programs written by competent human developers.

Experimental Results

The system was evaluated on classic NP-hard problems, including Minimal Maximal Matching and K-Closure, using 100 random instances for each. The performance of MULTI-TAC's generated code was compared against programs written by two Ph.D.-level computer scientists (Subjects 1 and 2) and a baseline "Simple CSP" engine.

Performance comparison showing MULTI-TAC significantly outperforming a human programmer (Subject 2) and a baseline solver.

The results demonstrated that MULTI-TAC's programs were significantly faster and solved more instances than those written by the volunteer scientists, who spent between 5 and 12 hours on their implementations. Notably, the system's output achieved performance levels nearly identical to code written by a project member expert in heuristic design.

Key Insights

  • Learning as Inference: Shifting from caching to an inferential process allows the system to discover structural optimizations, such as automated symmetry breaking. For example, in graph coloring, MULTI-TAC can recognize when two colors are functionally identical, preventing redundant search paths.
  • Tractable Meta-Reasoning: To avoid the complexity of infinite meta-reasoning, MULTI-TAC uses depth-limited analyses. By focusing on direct constraints between variables, it keeps the search space for specializations manageable.

Conclusion and Future Work

MULTI-TAC demonstrates that meta-level reasoning can effectively automate the design of high-performance heuristics. While the system currently requires hand-coded meta-theories, future research could explore the incremental refinement of general theories. Additionally, expanding the system's scope beyond backtracking search to include techniques like iterative repair would further enhance its utility in solving complex constraint satisfaction problems.

Summary updated

BibTeX
@inproceedings{minton1993analytic,
  author = {Steven Minton},
  title = {{An Analytic Learning System for Specializing Heuristics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1993},
}
Figure