Actions
  • shareshare
  • link
  • cite
  • add
add
auto_awesome_motion View all 2 versions
Publication . Part of book or chapter of book . Conference object . 2016

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

Faber, Wolfgang; Vallati, Mauro; Cerutti, Federico; Giacomin, Massimiliano;
Open Access
English
Published: 01 Aug 2016
Country: United Kingdom
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\ud using the proposed method is studied.

Subjects

QA75, QA76

Related Organizations
25 references, page 1 of 3

[1] Mario Alviano, Carmine Dodaro, and Francesco Ricca, 'A maxsat algorithm using cardinality constraints of bounded size', in Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015), pp. 2677-2683, (2015).

[2] Ofer Arieli and Martin W.A. Caminada, 'A QBF-based formalization of abstract argumentation semantics', Journal of Applied Logic, 11(2), 229-252, (2013).

[3] Pietro Baroni, Martin Caminada, and Massimiliano Giacomin, 'An introduction to argumentation semantics', Knowledge Engineering Review, 26(4), 365-410, (2011).

[4] Pietro Baroni, Federico Cerutti, Paul E. Dunne, and Massimiliano Giacomin, 'Automata for Infinite Argumentation Structures', Artificial Intelligence, 203(0), 104-150, (2013).

[5] Philippe Besnard and Sylvie Doutre, 'Checking the acceptability of a set of arguments', in Proc. of the 10th Int. Workshop on Non-Monotonic Reasoning (NMR 2004), pp. 59-64, (2004).

[6] Philippe Besnard and Anthony Hunter, 'Constructing argument graphs with deductive arguments: a tutorial', Argument & Computation, 5(1), 5-30, (2014).

[7] Handbook of Satisfiability, eds., Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, volume 185 of Frontiers in Artificial Intelligence and Applications, IOS Press, 2009.

[8] Bernhard Bliem, Gu¨nther Charwat, Markus Hecher, and Stefan Woltran, 'D-FLATˆ2: Subset minimization in dynamic programming on tree decompositions made easy', in Eighth Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2015), (2015).

[9] Gerhard Brewka, James P. Delgrande, Javier Romero, and Torsten Schaub, 'asprin: Customizing answer set preferences without a headache', in Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI 2015), pp. 1467-1474, (2015).

[10] Re´mi Brochenin, Thomas Linsbichler, Marco Maratea, Johannes Peter Wallner, and Stefan Woltran, 'Abstract solvers for Dung's argumentation frameworks', in Proceedings of the International Workshop on Theory and Applications of Formal Argument (TAFA), (2015).

Download fromView all 2 sources
lock_open
University of Huddersfield Repository
Part of book or chapter of book . 2016
moresidebar