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

DOI10.3233/978-1-61499-672-9-966zbMATH Open1403.68236arXiv1612.07589OpenAlexW2516814890MaRDI QIDQ4576229FDOQ4576229

Authors: Wolfgang Faber, Mauro Vallati, Federico Cerutti, Massimiliano Giacomin 

Publication date: 12 July 2018

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.

Full work available at URL: https://arxiv.org/abs/1612.07589

Recommendations

• SAT-based approaches to adjusting, repairing, and computing largest extensions of argumentation frameworks
• On computing the set of acceptable arguments in abstract argumentation
• On optimal solutions of answer set optimization problems
• Computing strongly admissible sets
• Argumentation frameworks as constraint satisfaction problems

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Logic in artificial intelligence (68T27)

Cited In (5)

• Model enumeration in propositional circumscription via unsatisfiable core analysis
• Design and results of the second international competition on computational models of argumentation
• How we designed winning algorithms for abstract argumentation and which insight we attained
• Paracoherent answer set computation
• Acceptance in incomplete argumentation frameworks

This page was built for publication: Solving set optimization problems by cardinality optimization with an application to argumentation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4576229)