@inproceedings{SaikkoADJ:KR2018,
title = {A Hybrid Approach to Optimization in Answer Set Programming},
author = {Paul Saikko and Carmine Dodaro and Mario Alviano and Matti J\"arvisalo},
editor = {Michael Thielscher and Francesca Toni and Frank Wolter},
booktitle = {Proceedings of the 16th International Conference on
             Principles of Knowledge Representation and Reasoning (KR 2018)},
pages = {32--41},
publisher = {AAAI Press},
year = {2018},
}

Abstract:

Answer set programming (ASP) is today a successful approach to knowledge representation
and reasoning in various real-world problem domains. ASP offers an expressive rule-based
constraint modelling language, supporting concise declarative modelling of both decision and
optimization problems within the first or the second level of the polynomial hierarchy.
In this paper, we propose a new approach to solving optimization problems via ASP, i.e., to
the problem of finding optimal solutions (in terms of optimal answer sets or stable models)
under a given weight function over soft atoms (weak constraints). Our approach constitutes
the first adaptation of the so-called implicit hitting set approach in the context of ASP.
In particular, in contrast to the earlier proposed family of core-guided algorithms for
optimization in answer set programming, we present a hybrid approach which makes use of
interactions between an ASP decision solver (as an unsatisfiable core extractor) and an
integer programming solver (as a minimum-cost hitting set algorithm). We explain how various
concepts and features specific to ASP and IP can be harnessed within the approach, including
several ways for obtaining better upper and lower bounds during search, with the aim of
speeding up the computation of an optimal answer set. By a careful integration of the
interactions between state-of-the-art ASP and IP solvers, we show that already our first
implementation provides a complementary approach when empirically compared to the currently
available solvers supporting optimization in answer set programming.