Strong equivalence of qualitative optimization problems

Wolfgang Faber, Mirosław Truszczyński, Stefan Woltran

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

2 Scopus citations

Abstract

We introduce the framework of qualitative optimization problems (or, simply, optimization problems) to represent preference theories. The formalism uses separate modules to describe the space of outcomes to be compared (the generator) and the preferences on outcomes (the selector). We consider two types of optimization problems. They differ in the way the generator, which we model by a propositional theory, is interpreted: by the standard propositional logic semantics, and by the equilibrium-model (answer-set) semantics. Under the latter interpretation of generators, optimization problems directly generalize answer-set optimization programs proposed previously. We study strong equivalence of optimization problems, which guarantees their interchangeability within any larger context. We characterize several versions of strong equivalence obtained by restricting the class of optimization problems that can be used as extensions and establish the complexity of associated reasoning tasks. Understanding strong equivalence is essential for modular representation of optimization problems and rewriting techniques to simplify them without changing their inherent properties.

Original languageEnglish
Title of host publication13th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2012
Pages188-198
Number of pages11
StatePublished - 2012
Event13th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2012 - Rome, Italy
Duration: Jun 10 2012Jun 14 2012

Publication series

NameProceedings of the International Conference on Knowledge Representation and Reasoning
ISSN (Print)2334-1025
ISSN (Electronic)2334-1033

Conference

Conference13th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2012
Country/TerritoryItaly
CityRome
Period6/10/126/14/12

Bibliographical note

Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Strong equivalence of qualitative optimization problems'. Together they form a unique fingerprint.

Cite this