Integrating Heuristics for Constraint Satisfaction Problems: A Case Study

Steven MintonAAAI 1993

Introduction

In the early 1990s, the field of automated algorithm configuration was in its infancy. Steven Minton’s work on MULTI-TAC (Multi-Tactic Analytic Compiler), presented at AAAI-93, introduced a pioneering approach to bridging the gap between general-purpose AI search and highly optimized, hand-coded solvers. MULTI-TAC is a system that automatically synthesizes high-performance constraint satisfaction programs by specializing generic heuristics for specific problem types. By training on a distribution of problem instances, it can produce solvers that match or even outperform those written by expert human computer scientists.

The Challenge: Efficiency vs. Generality

Constraint Satisfaction Problems (CSPs) present a fundamental tension between efficiency and generality. While general heuristics are designed to work "well enough" across a broad range of problems, real-world applications—such as factory scheduling—often involve solving many similar instances of the same NP-complete problem. In these scenarios, a specialized solver is significantly more valuable. However, manually crafting such solvers is a time-consuming process requiring deep domain expertise. Minton’s research addresses whether a system can automatically tailor a search algorithm to a specific problem and data distribution.

The MULTI-TAC Architecture

MULTI-TAC functions as a CSP "expert" that synthesizes Lisp programs. Its architecture relies on four primary components:

  1. Algorithm Schemas: The system utilizes high-level search strategies, primarily backtracking.
  2. Heuristic Specialization: It maintains a library of generic heuristics (e.g., "Most-Constrained-Variable-First") and refines them into domain-specific versions using a process akin to partial evaluation.
  3. Configuration Search: Rather than selecting a single heuristic, MULTI-TAC uses parallel hill-climbing (beam search) to find the optimal combination of heuristics by testing them against training instances.
  4. Code Generation: The final configuration is compiled into a standalone Lisp program, incorporating low-level optimizations like finite differencing and efficient data structure selection.
Figure 1: Example of a graph problem and its corresponding Lisp-based relational data specification used by MULTI-TAC.

Experimental Evaluation

The system was evaluated using the Minimum Maximal Matching (MMM) problem, a graph theory challenge where the goal is to find a small subset of edges that "cover" the graph without sharing endpoints. Three distinct instance distributions were tested:

  • Experiment 1: Randomly generated solvable instances (~50 edges).
  • Experiment 2: Larger instances to test scalability.
  • Experiment 3: Sparse graphs with low edge-to-node ratios, which are empirically much harder to solve.

Key Insights and Results

The study revealed that heuristic effectiveness is highly sensitive to the data distribution. A strategy that excels on dense graphs may fail on sparse ones. Furthermore, MULTI-TAC demonstrated that heuristics often interact synergistically; combinations of individually weak heuristics can become powerful when paired.

The performance of MULTI-TAC was compared against programs written by human computer scientists and a project member. In Experiment 1, MULTI-TAC achieved parity with the best human-coded versions. In the most challenging distribution (Experiment 3), MULTI-TAC actually outperformed the human subjects, solving instances in 449 seconds compared to the best human time of 1035 seconds.

Figure 5: Performance comparison between MULTI-TAC, human subjects, and a simple CSP engine across three experimental distributions.

Conclusion and Limitations

MULTI-TAC proved that automated synthesis can match or exceed human performance in specialized CSP domains. However, the system had limitations: it was restricted to decision problems (Yes/No) rather than optimization, and its search schemas were primarily limited to backtracking. Despite these constraints, the work laid the groundwork for modern automated algorithm configuration, demonstrating that "offline" search for the right algorithm is a worthwhile investment for "online" performance gains.

Summary updated

BibTeX
@inproceedings{minton1993integrating,
  author = {Steven Minton},
  title = {{Integrating Heuristics for Constraint Satisfaction Problems: A Case Study}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure