@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.