Solving set Optimization problems by cardinality Optimization with an application to argumentation

Wolfgang Faber, Mauro Vallati, Federico Cerutti, Massimiliano Giacomin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Citations (Scopus)

Abstract

Optimization-minimization or maximization-in the lattice of subsets is a frequent operation in Artificial Intelligence tasks. Examples are subset-minimal model-based diagnosis, nonmonotonic reasoning by means of circumscription, or preferred extensions in abstract argumentation. Finding the optimum among many admissible solutions is often harder than finding admissible solutions with respect to both computational complexity and methodology. This paper addresses the former issue by means of an effective method for finding subset-optimal solutions. It is based on the relationship between cardinality-optimal and subset-optimal solutions, and the fact that many logic-based declarative programming systems provide constructs for finding cardinality-optimal solutions, for example maximum satisfiability (MaxSAT) or weak constraints in Answer Set Programming (ASP). Clearly each cardinality-optimal solution is also a subset-optimal one, and if the language also allows for the addition of particular restricting constructs (both MaxSAT and ASP do) then all subset-optimal solutions can be found by an iterative computation of cardinality-optimal solutions. As a showcase, the computation of preferred extensions of abstract argumentation frameworks using the proposed method is studied.

Original languageEnglish
Title of host publicationFrontiers in Artificial Intelligence and Applications
PublisherIOS Press
Pages966-973
Number of pages8
Volume285
ISBN (Electronic)9781614996712
DOIs
Publication statusPublished - 2016
Event22nd European Conference on Artificial Intelligence - World Forum, The Hague, Netherlands
Duration: 29 Aug 20162 Sep 2016
Conference number: 22
http://www.ecai2016.org/ (Link to Conference Website )

Publication series

NameFrontiers in Artificial Intelligence and Applications
Volume285
ISSN (Print)0922-6389

Conference

Conference22nd European Conference on Artificial Intelligence
Abbreviated titleECAI 2016
CountryNetherlands
CityThe Hague
Period29/08/162/09/16
Internet address

Fingerprint

Computer systems programming
Set theory
Artificial intelligence
Computational complexity

Cite this

Faber, W., Vallati, M., Cerutti, F., & Giacomin, M. (2016). Solving set Optimization problems by cardinality Optimization with an application to argumentation. In Frontiers in Artificial Intelligence and Applications (Vol. 285, pp. 966-973). (Frontiers in Artificial Intelligence and Applications; Vol. 285). IOS Press. https://doi.org/10.3233/978-1-61499-672-9-966
Faber, Wolfgang ; Vallati, Mauro ; Cerutti, Federico ; Giacomin, Massimiliano. / Solving set Optimization problems by cardinality Optimization with an application to argumentation. Frontiers in Artificial Intelligence and Applications. Vol. 285 IOS Press, 2016. pp. 966-973 (Frontiers in Artificial Intelligence and Applications).
@inproceedings{9440293847084a1cbafb6a9e302ed8c4,
title = "Solving set Optimization problems by cardinality Optimization with an application to argumentation",
abstract = "Optimization-minimization or maximization-in the lattice of subsets is a frequent operation in Artificial Intelligence tasks. Examples are subset-minimal model-based diagnosis, nonmonotonic reasoning by means of circumscription, or preferred extensions in abstract argumentation. Finding the optimum among many admissible solutions is often harder than finding admissible solutions with respect to both computational complexity and methodology. This paper addresses the former issue by means of an effective method for finding subset-optimal solutions. It is based on the relationship between cardinality-optimal and subset-optimal solutions, and the fact that many logic-based declarative programming systems provide constructs for finding cardinality-optimal solutions, for example maximum satisfiability (MaxSAT) or weak constraints in Answer Set Programming (ASP). Clearly each cardinality-optimal solution is also a subset-optimal one, and if the language also allows for the addition of particular restricting constructs (both MaxSAT and ASP do) then all subset-optimal solutions can be found by an iterative computation of cardinality-optimal solutions. As a showcase, the computation of preferred extensions of abstract argumentation frameworks using the proposed method is studied.",
author = "Wolfgang Faber and Mauro Vallati and Federico Cerutti and Massimiliano Giacomin",
year = "2016",
doi = "10.3233/978-1-61499-672-9-966",
language = "English",
volume = "285",
series = "Frontiers in Artificial Intelligence and Applications",
publisher = "IOS Press",
pages = "966--973",
booktitle = "Frontiers in Artificial Intelligence and Applications",
address = "Netherlands",

}

Faber, W, Vallati, M, Cerutti, F & Giacomin, M 2016, Solving set Optimization problems by cardinality Optimization with an application to argumentation. in Frontiers in Artificial Intelligence and Applications. vol. 285, Frontiers in Artificial Intelligence and Applications, vol. 285, IOS Press, pp. 966-973, 22nd European Conference on Artificial Intelligence, The Hague, Netherlands, 29/08/16. https://doi.org/10.3233/978-1-61499-672-9-966

Solving set Optimization problems by cardinality Optimization with an application to argumentation. / Faber, Wolfgang; Vallati, Mauro; Cerutti, Federico; Giacomin, Massimiliano.

Frontiers in Artificial Intelligence and Applications. Vol. 285 IOS Press, 2016. p. 966-973 (Frontiers in Artificial Intelligence and Applications; Vol. 285).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Solving set Optimization problems by cardinality Optimization with an application to argumentation

AU - Faber, Wolfgang

AU - Vallati, Mauro

AU - Cerutti, Federico

AU - Giacomin, Massimiliano

PY - 2016

Y1 - 2016

N2 - Optimization-minimization or maximization-in the lattice of subsets is a frequent operation in Artificial Intelligence tasks. Examples are subset-minimal model-based diagnosis, nonmonotonic reasoning by means of circumscription, or preferred extensions in abstract argumentation. Finding the optimum among many admissible solutions is often harder than finding admissible solutions with respect to both computational complexity and methodology. This paper addresses the former issue by means of an effective method for finding subset-optimal solutions. It is based on the relationship between cardinality-optimal and subset-optimal solutions, and the fact that many logic-based declarative programming systems provide constructs for finding cardinality-optimal solutions, for example maximum satisfiability (MaxSAT) or weak constraints in Answer Set Programming (ASP). Clearly each cardinality-optimal solution is also a subset-optimal one, and if the language also allows for the addition of particular restricting constructs (both MaxSAT and ASP do) then all subset-optimal solutions can be found by an iterative computation of cardinality-optimal solutions. As a showcase, the computation of preferred extensions of abstract argumentation frameworks using the proposed method is studied.

AB - Optimization-minimization or maximization-in the lattice of subsets is a frequent operation in Artificial Intelligence tasks. Examples are subset-minimal model-based diagnosis, nonmonotonic reasoning by means of circumscription, or preferred extensions in abstract argumentation. Finding the optimum among many admissible solutions is often harder than finding admissible solutions with respect to both computational complexity and methodology. This paper addresses the former issue by means of an effective method for finding subset-optimal solutions. It is based on the relationship between cardinality-optimal and subset-optimal solutions, and the fact that many logic-based declarative programming systems provide constructs for finding cardinality-optimal solutions, for example maximum satisfiability (MaxSAT) or weak constraints in Answer Set Programming (ASP). Clearly each cardinality-optimal solution is also a subset-optimal one, and if the language also allows for the addition of particular restricting constructs (both MaxSAT and ASP do) then all subset-optimal solutions can be found by an iterative computation of cardinality-optimal solutions. As a showcase, the computation of preferred extensions of abstract argumentation frameworks using the proposed method is studied.

UR - http://www.scopus.com/inward/record.url?scp=85013042086&partnerID=8YFLogxK

U2 - 10.3233/978-1-61499-672-9-966

DO - 10.3233/978-1-61499-672-9-966

M3 - Conference contribution

VL - 285

T3 - Frontiers in Artificial Intelligence and Applications

SP - 966

EP - 973

BT - Frontiers in Artificial Intelligence and Applications

PB - IOS Press

ER -

Faber W, Vallati M, Cerutti F, Giacomin M. Solving set Optimization problems by cardinality Optimization with an application to argumentation. In Frontiers in Artificial Intelligence and Applications. Vol. 285. IOS Press. 2016. p. 966-973. (Frontiers in Artificial Intelligence and Applications). https://doi.org/10.3233/978-1-61499-672-9-966