Learning and using domain-specific heuristics in ASP solvers

Issue title: Answer Set Programming

Article type: Research Article

Authors: Balduccini, Marcello

Affiliations: Kodak Research Laboratories, Eastman Kodak Company, Rochester, NY 14650-2102, USA. E-mail: marcello.balduccini@gmail.com

Abstract: In spite of the improvements in the performance of many solvers for model-based languages, it is still possible for the search algorithm to focus on the wrong areas of the search space, preventing the solver from returning a solution in an acceptable amount of time. This prospect is a real concern e.g. in an industrial setting, where users typically expect consistent performance. To overcome this problem, we propose a framework that allows learning and using domain-specific heuristics in the solvers. The learning is done offline, on representative instances from the target domain, and the learned heuristics are then used for choice-point selection. In this paper we focus on Answer Set Programming (ASP) solvers. In our experiments, the introduction of domain-specific heuristics improved performance quite substantially on hard instances, and in particular made overall performance more consistent by reducing the number of cases in which the solver timed out.

Keywords: Answer set programming, solvers, domain-specific heuristics

DOI: 10.3233/AIC-2011-0493

Journal: AI Communications, vol. 24, no. 2, pp. 147-164, 2011