Reference:
Emilia Oikarinen and Matti Järvisalo. MaxASP: Maximum satisfiability of answer set programs. In Esra Erdem, Fangzhen Lin, and Torsten Schaub, editors, Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2009), volume 5753 of Lecture Notes in Artificial Intelligence, pages 236–249. Springer, 2009.
Abstract:
This paper studies answer set programming (ASP) in the generalized context of soft constraints and optimization criteria. In analogy to the wellknown MaxSAT problem of maximum satisfiability of propositional formulas, we introduce the problems of unweighted and weighted MaxASP. Given a normal logic program , in MaxASP the goal is to find so called optimal MaxASP models, which minimize the total cost of unsatisfied rules in and are at the same time answer sets for the set of satisfied rules in . Inference rules for MaxASP are developed, resulting in a complete branchandbound algorithm for finding optimal models for weighted MaxASP instances. Differences between the MaxASP problem and earlier proposed related concepts in the context of ASP are also discussed. Furthermore, translations between MaxASP and MaxSAT are studied.
Suggested BibTeX entry:
@inproceedings{OikarinenJ:LPNMR09,
author = {Emilia Oikarinen and Matti J\"arvisalo},
booktitle = {Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2009)},
editor = {Esra Erdem and Fangzhen Lin and Torsten Schaub},
pages = {236249},
publisher = {Springer},
series = {Lecture Notes in Artificial Intelligence},
title = {{MaxASP}: Maximum Satisfiability of Answer Set Programs},
volume = {5753},
year = {2009},
}
