On optimal solutions of answer set optimization problems

Ying Zhu, Miroslaw Truszczynski

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations


In 2003, Brewka, Niemelä and Truszczynski introduced answer-set optimization problems. They consist of two components: a logic program and a set of preference rules. Answer sets of the program represent possible outcomes; preferences determine a preorder on them. Of interest are answer sets of the program that are optimal with respect to the preferences. In this work, we consider computational problems concerning optimal answer sets. We implement and study several methods for the problems of computing an optimal answer set; computing another one, once the first one is found; and computing an optimal answer set that is similar to (respectively, dissimilar from) a given interpretation. For the problems of the existence of similar and dissimilar optimal answer set we establish their computational complexity.

Original languageEnglish
Title of host publicationLogic Programming and Nonmonotonic Reasoning - 12th International Conference, LPNMR 2013, Proceedings
Number of pages13
StatePublished - 2013
Event12th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2013 - Corunna, Spain
Duration: Sep 15 2013Sep 19 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8148 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference12th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2013

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On optimal solutions of answer set optimization problems'. Together they form a unique fingerprint.

Cite this