An Experimental Comparison of Constraint Logic Programming and Answer Set Programming

Agostino Dovier, Andrea Formisano, Enrico PontelliAAAI 2007

Abstract

This paper provides a head-to-head empirical showdown between two heavyweights of declarative programming: Answer Set Programming (ASP) and Constraint Logic Programming over Finite Domains (CLP(FD)). By benchmarking both paradigms against a suite of NP-complete problems, the study reveals that while CLP(FD) excels at arithmetic-heavy optimization, ASP—particularly SAT-based solvers—is often superior for graph-based problems and proving that no solution exists.

Introduction

When faced with computationally "hard" problems such as scheduling, planning, or circuit design, researchers often turn to logic-based declarative languages. These allow a programmer to describe what the problem is rather than how to solve it. However, the two most popular frameworks—ASP and CLP(FD)—evolved from different traditions. ASP grew out of non-monotonic reasoning and stable model semantics, while CLP(FD) emerged from the integration of logic programming (Prolog) with constraint satisfaction techniques. This study aims to bridge the gap between these paradigms by identifying which is best suited for specific types of combinatorial challenges.

Methodology

The researchers compared the two paradigms by implementing the same set of problems in both frameworks using the most "natural" encoding for each:

  • CLP(FD) Approach: Utilizes a "constrain-and-generate" strategy. The program first defines variables and their domains, imposes constraints, and then uses a labeling predicate to systematically search for values. SICStus Prolog was used as the primary CLP representative.
  • ASP Approach: Utilizes a "generate-and-test" strategy. It uses rules to define a space of potential "answer sets" and constraints to eliminate invalid ones. The study tested both SMODELS (a dedicated ASP solver) and CMODELS (which translates ASP problems into SAT problems to leverage high-performance SAT solvers).

The comparison focused on two metrics: programming effort (declarative nature and compactness) and computational performance (CPU time and memory).

Benchmarks

The solvers were evaluated using a diverse set of classic NP-complete and combinatorial problems:

  • Graph-based: $k$-coloring and Hamiltonian Circuit.
  • Mathematical/Combinatorial: Schur numbers and the Generalized Knapsack problem.
  • AI & Bioinformatics: Protein structure prediction (2D lattice), Blocks World planning, and Code Design.

These benchmarks represent different "flavors" of complexity—some are heavy on logic and connectivity, while others are dominated by arithmetic.

Results and Discussion

The experimental results highlight distinct performance profiles for each paradigm.

Comparison of solver performance across problem types and instance results. Bubble size represents relative performance/efficiency.

Performance Winners

  • CLP(FD) (SICStus): Dominates in Protein Structure Prediction and Knapsack problems. It is also generally faster at finding a single valid solution ("Yes" instances) in many cases.
  • ASP (CMODELS): The clear winner for "No" instances across almost all benchmarks, particularly in Graph Coloring and Hamiltonian Circuits.

Key Insights

  • Declarative Ease vs. Control: ASP is generally more "declarative," handling grounding automatically and avoiding explicit recursion. CLP(FD) often requires the programmer to understand the underlying search engine to write efficient code.
  • The "No" Instance Advantage: ASP (specifically CMODELS) is significantly better at proving a problem has no solution. This is attributed to the power of modern SAT solvers in pruning search spaces.
  • Arithmetic and Grounding: Problems involving intense numerical calculations or large domains (e.g., Knapsack) are handled more efficiently by CLP(FD). ASP struggles here due to the "grounding bottleneck," where enumerating all possible values can lead to a combinatorial explosion in memory.

Conclusion

The study identifies the grounding bottleneck as a primary limitation for ASP in arithmetic-heavy domains, while CLP(FD) lacks the automated optimization found in SAT-based solvers for purely logical constraints. Future work points toward hybridization, such as Constraint Answer Set Programming, which allows ASP to outsource arithmetic constraints to a CLP engine, combining the strengths of both paradigms.

Summary updated

BibTeX
@inproceedings{dovier2007experimental,
  author = {Agostino Dovier and Andrea Formisano and Enrico Pontelli},
  title = {{An Experimental Comparison of Constraint Logic Programming and Answer Set Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2007},
}
Figure