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.

@inproceedings{
    OikarinenJ:LPNMR09_eoikarin,
    editor = "Erdem, Esra and Lin, Fangzhen and Schaub, Torsten",
    author = {Oikarinen, Emilia and J\"arvisalo, Matti},
    volume = "5753",
    publisher = "Springer",
    title = "{Max-ASP}: Maximum Satisfiability of Answer Set Programs",
    url = "http://dx.doi.org/10.1007/978-3-642-04238-6_21",
    series = "Lecture Notes in Artificial Intelligence",
    booktitle = "Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2009)",
    corerank = "A",
    pages = "236--249",
    responsibleauthor = "Emilia Oikarinen",
    flags = "public MCM",
    year = "2009",
    impactfactor = "D3",
    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."
}

AUTHORS:

ABSTRACT:

URL:
http://dx.doi.org/10.1007/978-3-642-04238-6_21

AUTHORS:

ABSTRACT:

URL: http://dx.doi.org/10.1007/978-3-642-04238-6_21

URL:
http://dx.doi.org/10.1007/978-3-642-04238-6_21