TLDR: ASP-FZN is a new solver for Constraint Answer Set Programming (CASP) that translates CASP programs into FlatZinc, allowing it to leverage powerful Constraint Programming and Integer Programming solvers. It shows competitive performance on plain ASP and outperforms existing CASP solvers like clingcon on certain benchmarks, offering a promising approach for complex AI and combinatorial problems.
In the world of artificial intelligence and complex problem-solving, two powerful paradigms stand out: Answer Set Programming (ASP) and Constraint Programming (CP). ASP is excellent for problems that can be represented by logical rules, where solutions are found as ‘answer sets’. Constraint Answer Set Programming (CASP) extends ASP by adding the ability to handle linear constraints, making it particularly effective for real-world challenges like scheduling.
While CASP has proven its worth, existing solvers sometimes struggle to match the efficiency of dedicated Constraint Programming (CP) or Mixed Integer Programming (MIP) solvers for certain types of problems. Many CASP solvers rely on dedicated algorithms or translations into related formalisms like Satisfiability Modulo Theory (SMT). However, SMT solvers often lack the optimization features crucial for many practical applications.
Introducing ASP-FZN: A New Approach to CASP
To address this gap, researchers have introduced a new solver called asp-fzn. This innovative tool takes a different approach: it translates CASP programs into FlatZinc, a solver-independent intermediate language. This allows asp-fzn to tap into the decades of engineering and advancements in modern CP and MIP solvers, leveraging their strengths for efficient and optimal solution finding.
The core idea behind asp-fzn is to bridge the gap between CASP and the highly optimized CP/MIP solvers. By converting CASP programs into FlatZinc, asp-fzn can utilize powerful backend engines like Google OR-Tools’ CP-SAT or Gurobi, a state-of-the-art MIP solver. This not only benefits from current solver capabilities but also from future improvements in these well-established fields.
What Can ASP-FZN Do?
ASP-FZN supports a rich language of linear constraints, including common global constraints such as ‘alldifferent’ (ensuring all variables have distinct values), ‘cumulative’ (managing resource usage over time), and ‘disjoint’ (ensuring intervals do not overlap). It also handles various ASP constructs like variables, aggregates (sums, counts), choice rules, and disjunctions. A notable advantage is its ability to easily incorporate complex global constraints and perform hybrid optimization, combining ASP’s weak constraints with objectives over linear variables – features not fully supported by other prominent CASP solvers like clingcon.
How It Works Under the Hood
The asp-fzn tool works by taking a CASP program, which can be a non-ground ASP program or in ASPIF format (an intermediate format produced by grounders like gringo). It then translates this program into a FlatZinc theory. This FlatZinc output can either be processed externally or directly relayed by asp-fzn to a MiniZinc interface, which then communicates with a chosen backend solver. The translation ensures that the models found by the FlatZinc solver correspond faithfully to the answer sets of the original CASP program.
Also Read:
- Assessing LLM Capabilities in Answer Set Programming: A New Benchmark Reveals Core Challenges
- Boosting Interactive Product Configuration with Intelligent ASP Techniques
Performance in Action
The researchers conducted extensive experiments to evaluate asp-fzn’s performance. They compared it against leading ASP solvers like clingo and DLV on a wide range of plain ASP benchmarks, and against clingcon on several CASP problems from the literature.
On plain ASP benchmarks, asp-fzn, particularly when using CP-SAT as its backend solver, proved to be highly competitive with state-of-the-art ASP solvers like clingo, often outperforming DLV. The non-strict version of asp-fzn’s translation showed even better performance in some cases, suggesting that a less strict mapping between models and answer sets can sometimes aid the search process.
For CASP problems, asp-fzn demonstrated very promising results. On the Test Laboratory Scheduling Problem (TLSPS) and Multi-Agent Path Finding (MAPF) benchmarks, asp-fzn with CP-SAT often outperformed clingcon, solving more instances to optimality and achieving better average solution times. This was partly due to asp-fzn’s ability to mix ASP and linear variable minimization objectives, and its support for global disjunctive constraints, which proved very effective. While clingcon showed strength in finding feasible solutions in parallel mode for some problems like Parallel Machine Scheduling Problem (PMSP), asp-fzn often provided the best final results and proved optimality faster.
One point to note is that CP-SAT, while powerful, can have a higher memory footprint compared to traditional ASP solvers like clingo. However, the time taken for asp-fzn to translate the gringo output to FlatZinc was negligible compared to the grounding time.
In conclusion, asp-fzn represents a significant step forward in Constraint Answer Set Programming. By leveraging the robust and highly optimized ecosystem of FlatZinc, CP, and MIP solvers, it offers a powerful and competitive new tool for tackling complex combinatorial and AI problems. For more technical details, you can refer to the full research paper.
