Strong Equivalence of Qualitative Optimization Problems

Wolfgang Faber, Miroslaw Truszczyski, Stefan Woltran

Research output: Contribution to journalArticle

2 Citations (Scopus)

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
Pages (from-to)351-391
Number of pages41
JournalJournal of Artificial Intelligence Research
Volume47
DOIs
Publication statusPublished - Jun 2013
Externally publishedYes

Fingerprint

Semantics

Cite this

Faber, Wolfgang ; Truszczyski, Miroslaw ; Woltran, Stefan. / Strong Equivalence of Qualitative Optimization Problems. In: Journal of Artificial Intelligence Research. 2013 ; Vol. 47. pp. 351-391.
@article{4a139c41c0b048ba8047227cd68e7459,
title = "Strong Equivalence of Qualitative Optimization Problems",
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.",
author = "Wolfgang Faber and Miroslaw Truszczyski and Stefan Woltran",
year = "2013",
month = "6",
doi = "10.1613/jair.3991",
language = "English",
volume = "47",
pages = "351--391",
journal = "Journal of Artificial Intelligence Research",
issn = "1076-9757",
publisher = "Morgan Kaufmann Publishers, Inc.",

}

Strong Equivalence of Qualitative Optimization Problems. / Faber, Wolfgang; Truszczyski, Miroslaw; Woltran, Stefan.

In: Journal of Artificial Intelligence Research, Vol. 47, 06.2013, p. 351-391.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Strong Equivalence of Qualitative Optimization Problems

AU - Faber, Wolfgang

AU - Truszczyski, Miroslaw

AU - Woltran, Stefan

PY - 2013/6

Y1 - 2013/6

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

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

UR - http://www.jair.org/

U2 - 10.1613/jair.3991

DO - 10.1613/jair.3991

M3 - Article

VL - 47

SP - 351

EP - 391

JO - Journal of Artificial Intelligence Research

JF - Journal of Artificial Intelligence Research

SN - 1076-9757

ER -