@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 = {236--249},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
title = {{Max-ASP}: Maximum Satisfiability of Answer Set Programs},
volume = {5753},
year = {2009},
}
Abstract:
This paper studies answer set programming (ASP) in the generalized
context of soft constraints and optimization criteria. In analogy to the
well-known Max-SAT problem of maximum satisfiability of propositional
formulas, we introduce the problems of unweighted and weighted Max-ASP.
Given a normal logic program , in Max-ASP the goal is to find so called
optimal Max-ASP 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 Max-ASP are developed, resulting in a
complete branch-and-bound algorithm for finding optimal models for
weighted Max-ASP instances. Differences between the Max-ASP problem and
earlier proposed related concepts in the context of ASP are also
discussed. Furthermore, translations between Max-ASP and Max-SAT are
studied.