ASP-FZN: A Translation-based Constraint Answer Set Solver
THOMAS EITER 1, TOBIAS GEIBINGER 1, TOBIAS KAMINSKI 3, NYSRET MUSLIU 1, JOHANNES OETSCH 2 · 2025
Read ASP-FZN: A Translation-based Constraint Answer Set Solver by THOMAS EITER 1, TOBIAS GEIBINGER 1, TOBIAS KAMINSKI 3, NYSRET MUSLIU 1, JOHANNES OETSCH 2 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-22774.txt.
Introduction
Thomas Eiter and four co-authors present asp-fzn, a solver for logic programs with number constraints, in a 2025 paper. Answer set programming states rules and facts and lets a solver find the sets that satisfy them, but plain versions struggle with arithmetic.
Their solver translates such programs into FlatZinc, a shared language read by many constraint and integer programming backends. It handles a rich set of linear constraints, including some common global ones. On past competition benchmarks it matched leading answer set solvers even on plain problems. On constraint problems it sometimes beat clingcon, the best-known rival. Translation, the results suggest, can rival solvers built for one language from the start.
Catalog record
| CREATOR | THOMAS EITER 1, TOBIAS GEIBINGER 1, TOBIAS KAMINSKI 3, NYSRET MUSLIU 1, JOHANNES OETSCH 2 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 88 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-22774
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
ASP-FZN: A Translation-based Constraint Answer Set Solver THOMAS EITER 1, TOBIAS GEIBINGER 1, TOBIAS KAMINSKI 3, NYSRET MUSLIU 1, JOHANNES OETSCH 2 Abstract We present the solver asp-fzn for Constraint Answer Set Programming (CASP), which extends ASP with linear constraints. Our approach is based on translating CASP programs into the solver-independent FlatZinc language that supports several Constraint Programming and Integer Programming backend solvers. Our solver supports a rich language of linear constraints, including some common global constraints. As for evaluation, we show that asp-fzn is competitive with state-of-the-art ASP solvers on benchmarks taken from past ASP competitions. Furthermore, we evaluate it on several CASP problems from the literature and compare its performance with clingcon, which is a prominent CASP solver that supports most of the asp-fzn language. The performance of asp-fzn is very promising as it is already competitive on plain ASP and even outperforms clingcon on some CASP benchmarks. \DeclareCaptionType listing keywords Answer Set Programming, Constraint Programming, Integer Programming 1 Introduction Answer Set Programming (ASP) is a popular rule-based formalism for various AI applications and combinatorial problem-solving, where a problem is represented by an ASP program whose answer sets (models) represent the solutions, potentially also under certain optimization criteria. Especially for modeling industrial problems, Constraint Answer Set Programming (CASP), which adds reasoning over linear constraints to ASP, proved to be quite effective, e.g., for scheduling problems ( Balduccini 2011 ; Geibinger et al. 2021 ) . While efficient CASP solvers are available, cf. the recent survey by Lierler 2023 , they still often lag behind state-of-the-art Constraint Programming (CP) or Mixed Integer Programming (MIP) solvers for certain problem domains. CASP solvers are either based on dedicated algorithms or translations into related formalisms such as Satisfiability Modulo Theory (SMT). The latter approach is inspired by similar works for solving plain ASP programs, but has the downside that SMT solvers generally lack optimization features and are thus not applicable for many problems appearing in practice. This begs the question why, instead of targeting SMT, the translation is not aimed at FlatZinc ( Nethercote et al. 2007 ) , which is a solver-independent intermediate language that offers those lacking optimization features and works with many modern CP and MIP solvers as backend engines. The lack of such an approach was also noted by Lierler 2023 . To fill this gap, we present the CASP solver asp-fzn , which translates CASP programs into FlatZinc, thereby leveraging decades of CP and MIP solver engineering for efficient (optimal) solution finding. To support modern CASP encodings featuring not only linear constraints but also specific scheduling constraints and ASP constructs like variables, aggregates, choice, and disjunction, we uilize gringo’s theory interface ( Gebser et al. 2019 ; Kaminski et al. 2023 ) to obtain a simplified program format. Our approach then combines and extends ideas from translation-based ASP solving ( Alviano and Dodaro 2016 ; Janhunen 2023 ) to create a FlatZinc representation encompassing all mentioned constructs. By the richness of FlatZinc, incorporating complex global constraints and hybrid optimization of both ASP weak constraints and objectives over linear variables is easy. Notably, those features are not yet fully supported by other state-of-the-art CASP solvers like clingcon ( Banbara et al. 2017 ; Cabalar et al. 2023 ) . Our main contributions are briefly summarized as follows: \bullet We present a translation \mathit{Tr}(P) of head-cycle-free CASP programs P into a low level constraint language, which can be parsed by several state-of-the-art CP and MIP solvers. \bullet Our translation extends and combines existing concepts from the literature and supports not only linear constraints but also choice rules, weight rules, disjunction, and optimization. \bullet We show that \mathit{Tr}(P) captures all answer sets of P , with a one-to-one or many-to-one mapping to its models, depending on the presence of correspondence constraints. \bullet We introduce our solver asp-fzn , which implements the described translation and utilizes external grounding and a parametric backend solver for answer-set optimization. \bullet We evaluate asp-fzn using different backend solvers against state-of-the-art (C)ASP solvers, finding that it is competitive on plain ASP and outperforms clingcon on some CASP benchmarks. The solver asp-fzn thus enables solving expressive (C)ASP programs via CP and MIP solvers, leveraging their strengths. As with SAT-based ASP solvers, this approach benefits from the substantial engineering behind these solvers, future advancements, and the decoupling of (C)ASP solving from specialized, maintenance-heavy algorithms. 2 Preliminaries We consider propositional Answer Set Programming (ASP) ( Brewka et al. 2011 ) with programs P that are sets of rules r of the form \displaystyle H\leftarrow B (1) where H is the head of the rule and B its body , also denoted by H(r) and B(r) , respectively; by \mathcal{A}_{P} we denote the set of all propositional atoms occurring in P . We distinguish two types of rules: 1) disjunctive rules and 2) choice rules , where H has the form \displaystyle a_{1}\mid\dots\mid a_{n} ( disjunctive head ) (2) \displaystyle\text{respectively}~~\{a_{1},\dots,a_{m}\} ( choice head ) (3) where all a_{i} are atoms. Intuitively, ” \mid ” stands for logical disjunction, i.e., at least one of the atoms must hold, while for choice, any number of a_{i} can be true if H is true. A disjunctive rule is a constraint rule if H(r)=\emptyset and a normal rule if |H(r)|=1 . Furthermore, we consider two types of rule bodies: 1) normal rule bodies of the form \displaystyle b_{1},\dots,b_{k},\neg b_{k+1},\dots,\neg b_{n} (4) where all b_{i} are atoms, \neg is negation as failure, and “,” is conjunction, and 2) weighted rule bodies \displaystyle l\leq\{b_{1}:w_{1},\dots,b_{k}:w_{k},\neg b_{k+1}:w_{k+1},\dots,\neg b_{n}:w_{n}\} (5) where all b_{i} are atoms, all w_{i} are integer weights , and l is the integer lower bound ; we let B^{+}(r)=\{b_{1},\ldots,b_{k}\} and B^{-}(r)\,{=}\,\{b_{k+1},\ldots,b_{n}\} . By slight abuse of notation, a\in H(r) denotes that atom a occurs in H(r) and l\in B(r) that literal l , i.e., an atom or its negation, occurs in B(r) . We further let w_{b}^{r} denote the weight of atom b in the body of rule r , let \top denote an empty conjunction, and let \bot denote an empty rule head. Example 1. Consider the program P_{1}=\{\ \{a,b\}\leftarrow c,\ \bot\leftarrow 3\leq\{a:1,b:2\},\ c\leftarrow\neg d\ \} . The first rule of P_{1} is a choice rule with normal body, the second rule is a constraint rule with a weighted body, and the last rule is a normal rule. Semantics. An interpretation of a program P is a set I\subseteq\mathcal{A}_{P} of atoms, which satisfies a disjunctive head ( 2 ) if a_{i}\in I for some i\in[1,m] , and satisfies every choice rule head ( 3 ). Given a rule r and an interpretation I , I\models H(r) denotes that I satisfies the head of r . Satisfaction of the body B(r) by I , denoted I\models B(r) , is as follows: 1) for a normal rule body ( 4 ), b_{i}\in I for every i\in[1,k] and b_{j}\not\in I for every j\in(k,n] must hold; 2) for a weighted rule body ( 5 ), the following linear inequality must hold: l\;\leq\sum_{i\in[1,k],b_{i}\in I}w_{i}+\sum_{j\in(j,n],b_{j}\not\in I}w_{j}. An interpretation I satisfies a rule r , denoted I\models r , whenever I\models B(r) implies I\models H(r) and I is a model of program P , denoted I\models P , if I\models r for