Overview

Answer Set Programming (ASP) is a declarative paradigm for knowledge representation and combinatorial problem solving. In ASP, a problem is encoded as a logic program whose answer sets (stable models) correspond to the solutions of the problem, and solutions are computed by an off-the-shelf ASP solver [cd609c07].

A standard reference introduction to the syntax and semantics of ASP is the primer by Lifschitz and colleagues, intended as a handout for undergraduate and graduate courses on Artificial Intelligence and Logic Programming [arxiv:cs/0508100v1].

Modeling Features

ASP is described in the literature as offering a high-level modeling approach with several distinguishing advantages [cd609c07]:

• Expressive language: problems can be expressed compactly using first-order rules, including choice rules, cardinality constraints, and aggregates.
• Extensible encodings: a base encoding can be extended with additional rules to capture richer problem variants (e.g., adding weak coverage constraints or soft constraints to a basic encoding) [712c3164].
• Flexible multi-criteria optimization: solvers natively support lexically ordered optimization criteria through directives such as #minimize and #maximize, with priorities given after @ [712c3164].

A typical ASP encoding uses the gringo series 4 language family and is paired with a fact-format instance description, which are combined and grounded before solving [cd609c07].

Solving

ASP programs are solved by general-purpose ASP systems. The widely used solver clingo accepts ground programs produced by the gringo grounder and computes answer sets, also providing lexicographic optimization across multiple #minimize/#maximize statements with differing weights [712c3164]. Multi-threaded portfolio search configurations of clingo are also used in practice [6136e7ed].

Example Constructs

Common ASP language constructs used in encodings include:

• Choice rules with cardinality bounds, e.g., 1 { assigned(R,I,A) : p(I,A) } 1 :- row(R); col(I). chooses exactly one value assignment per row and column [f5bdce69].
• Integrity constraints written as :- Body., which forbid answer sets whose body holds; for example, coverage constraints check that required pair(I,J,A,B) facts are covered [f5bdce69].
• Optimization statements such as #minimize{ 1,R : activated(R) }. to minimize the number of activated rows, and #maximize{ 1@coverage,I,J,A,B : covered(I,J,A,B) }. to maximize covered pairs with priority coverage [712c3164].
• Aggregates over literals, e.g., { assigned(R,I,A) : p(I,A) }, representing a set of candidate atoms [f5bdce69].

Applications

Constrained Combinatorial Testing (CCT)

The catnap system applies ASP to Constrained Combinatorial Testing, where the goal is to find a Constrained Mixed-level Covering Array (CMCA) of minimum size subject to hard and soft constraints on parameter values [cd609c07]. catnap combines a fact-format CCT instance with a first-order ASP encoding and delegates solving to clingo [cd609c07].

The basic ASP encoding for strength-2 CMCA finding (Listing 2 of the catnap paper) generates rows, columns, and constraint identifiers; assigns exactly one value per (row, column) cell; enforces domain constraints; and ensures that every valid (I,J,A,B) pair appears in some row [f5bdce69]. The optimal strength-2 CMCA finding encoding (Listing 3) extends this with activated/1 atoms whose count is minimized, and assigns values only to activated rows [f5bdce69, 712c3164]. A further weakened encoding (Listing 4) converts coverage constraints to soft constraints via #maximize, enabling lexicographic optimization of size and coverage, and avoids the pre-calculation of valid pairs required by earlier dedicated implementations [712c3164].

Empirically, catnap found the best known bounds on 25 of the benchmark instances compared, while dedicated tools such as TCA, CASA, ACTS, and Cascade found best bounds on 34, 15, 0, and 0 instances respectively, with catnap also improving the bound on the large benchmark_gcc instance to 15 [6136e7ed].

Other ASP Applications Mentioned

• Curriculum-based course timetabling: the teaspoon system [6136e7ed].
• Event-sequence test case generation: ASP encodings using #maximize over covered atoms to greedily generate test cases with maximal coverage, and to produce strength-t test suites of maximal (t+1)-coverage for early failure detection [6136e7ed].
• Symmetry detection and breaking: methods that reduce symmetry detection to a graph automorphism problem, encode symmetry-breaking constraints as permutation cycles, and have been evaluated on benchmarks against direct solver application; the approach also extends to constraint ASP solving and distributed nonmonotonic multi-context systems [arxiv:1008.5033v1].
• Constraint ASP (CASP): an extension of ASP that allows finite linear Constraint Satisfaction Problems to be represented and solved declaratively, with solvers such as clingcon [6136e7ed].

Relation to Constraint Solving and SAT

In constrained combinatorial testing, dedicated greedy or metaheuristic implementations cannot guarantee optimality, while direct SAT encodings are costly to maintain [cd609c07]. ASP occupies a middle ground by providing a high-level declarative language while leveraging general-purpose solver technology, and Constraint ASP (CASP) further extends ASP to handle richer finite linear constraints [6136e7ed].