Abstract
This paper introduces two novel encoding strategies for translating Answer Set Programming (ASP) into Integer Programming (IP) by focusing on the efficient representation of acyclicity constraints. By leveraging vertex elimination (VE) graphs and feedback vertex sets (FVS), the authors create IP formulations with significantly tighter linear relaxations. These methods allow standard IP solvers like Gurobi and CPLEX to prune search spaces more effectively, enabling them to compete with and sometimes outperform state-of-the-art native ASP solvers in complex optimization and decision-making tasks.
Introduction
Answer Set Programming (ASP) is a powerful paradigm for modeling complex logical problems, while Integer Programming (IP) remains the gold standard for high-performance optimization. To leverage the strengths of both, researchers often translate ASP rules into IP constraints. A major hurdle in this translation is enforcing acyclicity. In ASP, "stable models" must be well-supported, meaning circular reasoning (e.g., "A is true because B is true, and B is true because A is true") is forbidden.
Previous translation methods relied on "level numbers" (similar to the Bellman-Ford algorithm) to enforce these constraints. However, these encodings often result in "weak" linear programming (LP) relaxations. In IP solving, a weak relaxation means the solver's fractional "best guess" is far from the actual integer solution, forcing the solver to explore a much larger search space.
Methodology
The authors propose two new encoding strategies to replace the standard level-number approach:
- Vertex Elimination (VE) Based Translation: This method utilizes vertex elimination graphs. By systematically "removing" vertices and adding "fill-in" arcs between their neighbors, the process ensures that any cycle in the original graph eventually manifests as a simple 2-cycle (a pair of mutually dependent nodes). This encoding is mathematically more restrictive than previous methods, providing a tighter bound for the IP solver's search.
- Feedback Vertex Set (FVS) Based Translation: Because vertex elimination can generate a large number of extra variables in dense graphs, the authors introduced the FVS-based translation as a more concise alternative. By identifying a subset of nodes that, if removed, leaves the graph acyclic, the solver can restrict variable domains to prevent circularity more compactly.
Experimental Evaluation
The methods were evaluated using a benchmark set of non-tight ASP problems (problems containing cycles) from previous ASP competitions. These included optimization problems such as Bayesian Network Learning and Traveling Salesman Problem (TSP), as well as decision problems like Hamiltonian Cycle and Maze Generation.
Results and Discussion
The experimental results highlight the power of restrictive relaxations. By making the fractional version of the problem harder to satisfy, the solvers could discard large portions of the search tree earlier in the process.
Optimization Performance
The VE-based translation using Gurobi solved significantly more optimization problems (184/588) compared to the previous A2S IP translation (124/588). Notably, it outperformed the native ASP solver Clingo in specific categories like Bayesian and Markov Network Learning.
Decision Problem Performance
For decision problems, the VE-based translation with CPLEX proved highly effective. While native ASP solvers like Clingo still maintain an edge in finding any valid solution, the proposed encodings significantly closed the performance gap.
Conclusion
This research demonstrates that by exploiting the specific graph-theoretic structure of program dependencies, general-purpose IP solvers can be made competitive with specialized ASP solvers. While the VE method is sensitive to the "elimination width" of a graph, the FVS-based method serves as a robust fallback for dense instances. Future work will explore generalizing these techniques to other IP problems involving acyclicity and further refining the FVS translation to improve performance on decision-oriented benchmarks.
Summary updated