LIPIcs.IPEC.2017.17.pdf
- Filesize: 1.07 MB
- 13 pages
Document
DynASP2.5: Dynamic Programming on Tree Decompositions in Action
Authors
-
Part of:
Volume:
12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Parameterized and Exact Computation (IPEC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-03-02
Cite As Get BibTex
Johannes K. Fichte, Markus Hecher, Michael Morak, and Stefan Woltran. DynASP2.5: Dynamic Programming on Tree Decompositions in Action. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.IPEC.2017.17
Abstract
Efficient, exact parameterized algorithms are a vibrant theoretical research area. Recent solving competitions, such as the PACE challenge, show that there is also increasing practical interest in the parameterized algorithms community. An important research question is whether such algorithms can be built to efficiently solve specific problems in practice, that is, to be competitive with established solving systems. In this paper, we consider Answer Set Programming (ASP), a logic-based declarative modeling and problem solving framework. State-of-the-art ASP solvers generally rely on SAT-based algorithms. In addition, DynASP2, an ASP solver that is based on a classical dynamic programming on tree decompositions, has recently been introduced. DynASP2 outperforms modern ASP solvers when the goal is to count the number of solutions of programs that have small treewidth. However, for quickly finding one solutions, DynASP2 proved uncompetitive. In this paper, we present a new algorithm and implementation, called DynASP2.5, that shows competitive behavior compared to state-of-the-art ASP solvers on problems like Steiner tree for low-treewidth graphs, even when the task is to find just one solution. Our implementation is based on a novel approach that we call multi-pass dynamic programming.
Subject Classification
Keywords
- Parameterized algorithms
- Fixed-parameter linear time
- Tree decompositions
- Multi-pass dynamic programming
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Michael Abseher, Nysret Musliu, and Stefan Woltran. htd - A free, open-source framework for (customized) tree decompositions and beyond. In Domenico Salvagnin and Michele Lombardi, editors, Integration of AI and OR Techniques in Constraint Programming - 14th International Conference, CPAIOR 2017, Padua, Italy, June 5-8, 2017, Proceedings, volume 10335 of Lecture Notes in Computer Science, pages 376-386. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-59776-8_30.
- Michael Abseher, Nysret Musliu, and Stefan Woltran. Improving the efficiency of dynamic programming on tree decompositions via machine learning. J. Artif. Intell. Res., 58:829-858, 2017. URL: http://dx.doi.org/10.1613/jair.5312.
- Mario Alviano and Carmine Dodaro. Anytime answer set optimization via unsatisfiable core shrinking. TPLP, 16(5-6):533-551, 2016. URL: http://dx.doi.org/10.1017/S147106841600020X.
-
B. Bliem, M. Moldovan, M. Morak, and S. Woltran. The impact of treewidth on ASP grounding and solving. In IJCAI'17, The AAAI Press, pages 852-858, 2017.
- Bernhard Bliem, Günther Charwat, Markus Hecher, and Stefan Woltran. D-flat^2: Subset minimization in dynamic programming on tree decompositions made easy. Fundam. Inform., 147(1):27-61, 2016. URL: http://dx.doi.org/10.3233/FI-2016-1397.
- Hans L. Bodlaender and Arie M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth. Comput. J., 51(3):255-269, 2008. URL: http://dx.doi.org/10.1093/comjnl/bxm037.
- Holger Dell, Christian Komusiewicz, Nimrod Talmon, and Mathias Weller. The pace 2017 parameterized algorithms and computational experiments challenge: The second iteration. In IPEC'17, LIPIcs, pages 30:1 - -30:13, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2017.30.
- Thomas Eiter and Georg Gottlob. On the computational cost of disjunctive logic programming: Propositional case. Ann. Math. Artif. Intell., 15(3-4):289-323, 1995. URL: http://dx.doi.org/10.1007/BF01536399.
-
J. K. Fichte, M. Hecher, and S. Woltran. DynASP2.5: Dynamic Programming on Tree Decompositions in Action. CoRR, arXiv:1706.09370, 2017.
- Johannes Klaus Fichte, Markus Hecher, Michael Morak, and Stefan Woltran. Answer set solving with bounded treewidth revisited. In Marcello Balduccini and Tomi Janhunen, editors, Logic Programming and Nonmonotonic Reasoning - 14th International Conference, LPNMR 2017, Espoo, Finland, July 3-6, 2017, Proceedings, volume 10377 of Lecture Notes in Computer Science, pages 132-145. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-61660-5_13.
- Martin Gebser, Benjamin Kaufmann, and Torsten Schaub. Conflict-driven answer set solving: From theory to practice. Artif. Intell., 187:52-89, 2012. URL: http://dx.doi.org/10.1016/j.artint.2012.04.001.
- Georg Gottlob, Francesco Scarcello, and Martha Sideri. Fixed-parameter complexity in AI and nonmonotonic reasoning. Artif. Intell., 138(1-2):55-86, 2002. URL: http://dx.doi.org/10.1016/S0004-3702(02)00182-0.
- T. Janhunen and I. Niemelä. The answer set programming paradigm. AI Magazine, 37(3):13-24, 2016. URL: http://dx.doi.org/10.1609/aimag.v37i3.2671.
- Joachim Kneis, Alexander Langer, and Peter Rossmanith. Courcelle’s theorem - A game-theoretic approach. Discrete Optimization, 8(4):568-594, 2011. URL: http://dx.doi.org/10.1016/j.disopt.2011.06.001.
- Patrik Simons, Ilkka Niemelä, and Timo Soininen. Extending and implementing the stable model semantics. Artif. Intell., 138(1-2):181-234, 2002. URL: http://dx.doi.org/10.1016/S0004-3702(02)00187-X.