License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICLP.2010.14
URN: urn:nbn:de:0030-drops-25797
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2579/
Go to the corresponding LIPIcs Volume Portal

Balduccini, Marcello

Learning Domain-Specific Heuristics for Answer Set Solvers

pdf-format:
10003.BalducciniMarcello.2579.pdf (0.3 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{balduccini:LIPIcs:2010:2579,
  author =	{Marcello Balduccini},
  title =	{{Learning Domain-Specific Heuristics for Answer Set Solvers}},
  booktitle =	{Technical Communications of the 26th International Conference on Logic Programming},
  pages =	{14--23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-17-0},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{7},
  editor =	{Manuel Hermenegildo and Torsten Schaub},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2579},
  URN =		{urn:nbn:de:0030-drops-25797},
  doi =		{10.4230/LIPIcs.ICLP.2010.14},
  annote =	{Keywords: Answer set programming, solvers, domain-specific heuristics}
}

Keywords: Answer set programming, solvers, domain-specific heuristics
Collection: Technical Communications of the 26th International Conference on Logic Programming
Issue Date: 2010
Date of publication: 25.06.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI