10.4230/LIPICS.ICLP.2010.14
Balduccini, Marcello
Marcello
Balduccini
Learning Domain-Specific Heuristics for Answer Set Solvers
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2010
Article
Answer set programming
solvers
domain-specific heuristics
Hermenegildo, Manuel
Manuel
Hermenegildo
Schaub, Torsten
Torsten
Schaub
2010
2010-06-25
2010-06-25
2010-06-25
en
urn:nbn:de:0030-drops-25797
10.4230/LIPIcs.ICLP.2010
978-3-939897-17-0
1868-8969
10.4230/LIPIcs.ICLP.2010
LIPIcs, Volume 7, ICLP 2010
Technical Communications of the 26th International Conference on Logic Programming
2013
7
5
14
23
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Hermenegildo, Manuel
Manuel
Hermenegildo
Schaub, Torsten
Torsten
Schaub
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2010
7
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
10 pages
275982 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
In spite of the recent improvements in the performance of Answer Set Programming (ASP) solvers, when the search space is sufficiently large, it is still possible for the search algorithm to mistakenly focus on areas of the search space that contain no solutions or very few. When that happens, performance degrades substantially, even to the point that the solver may need to be terminated before returning an answer. This prospect is a concern when one is considering using such a solver in an industrial setting, where users typically expect consistent performance. To overcome this problem, in this paper we propose a technique that allows learning domain-specific heuristics for ASP solvers. The learning is done off-line, on representative instances from the target domain, and the learned heuristics are then used for choice-point selection. In our experiments, the introduction of domain-specific heuristics improved performance on hard instances by up to 3 orders of magnitude (and 2 on average), nearly completely eliminating the cases in which the solver had to be terminated because the wait for an answer had become unacceptable.
LIPIcs, Vol. 7, Technical Communications of the 26th International Conference on Logic Programming, pages 14-23