Anytime answer set optimization via unsatisfiable core shrinking

DOI10.1017/S147106841600020XMaRDI QIDQ4593041zbMATH OpenOpenAlexDBLPWikidataFDO

Authors M. Alviano, Carmine Dodaro

Publication date 9 November 2017

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

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

zbMATH Keywords

answer set programmingunsatisfiable coresweak constraints

Mathematics Subject Classification ID

Logic programming (68N17)

Abstract: Unsatisfiable core analysis can boost the computation of optimum stable models for logic programs with weak constraints. However, current solvers employing unsatisfiable core analysis either run to completion, or provide no suboptimal stable models but the one resulting from the preliminary disjoint cores analysis. This drawback is circumvented here by introducing a progression based shrinking of the analyzed unsatisfiable cores. In fact, suboptimal stable models are possibly found while shrinking unsatisfiable cores, hence resulting into an anytime algorithm. Moreover, as confirmed empirically, unsatisfiable core analysis also benefits from the shrinking process in terms of solved instances. This paper is under consideration for acceptance in TPLP.

Recommendations

• Unsatisfiable core analysis and aggregates for optimum stable model search
• Unsatisfiability-based optimization in clasp
• A Scalable Algorithm for Minimal Unsatisfiable Core Extraction
• Faster Extraction of High-Level Minimal Unsatisfiable Cores
• Anytime computation of cautious consequences in answer set programming

Cites work

• scientific article; zbMATH DE number 25190 (Why is no real title available?)
• Accelerated deletion-based extraction of minimal unsatisfiable cores
• Advances in WASP
• Answer Set Programming: A Primer
• Answer set programming based on propositional satisfiability
• Anytime computation of cautious consequences in answer set programming
• Complex optimization in answer set programming
• Complexity and compilation of GZ-aggregates in answer set programming
• Extending and implementing the stable model semantics
• Logic Programming and Nonmonotonic Reasoning
• Logic programs with abstract constraint atoms: the role of computations
• Logic programs with monotone abstract constraint atoms
• Logic programs with propositional connectives and aggregates
• Logic programs with stable model semantics as a constraint programming paradigm
• Multi-criteria optimization in answer set programming
• Progress in clasp series 3
• Rewriting recursive aggregates in answer set programming: back to monotonicity
• Semantics and complexity of recursive aggregates in answer set programming
• The Complexity Boundary of Answer Set Programming with Generalized Atoms under the FLP Semantics
• The Design of the Sixth Answer Set Programming Competition
• Theory and applications of satisfiability testing -- SAT 2006. 9th international conference, Seattle, WA, USA, August 12--15, 2006. Proceedings.
• Theory and applications of satisfiability testing -- SAT 2008. 11th international conference, SAT 2008, Guangzhou, China, May 12--15, 2008. Proceedings
• Theory and applications of satisfiability testing -- SAT 2009. 12th international conference, SAT 2009, Swansea, UK, June 30--July 3, 2009. Proceedings
• Unsatisfiability-based optimization in clasp
• Vicious circle principle and logic programs with aggregates

Cited in

(15)

• Model enumeration in propositional circumscription via unsatisfiable core analysis
• Better paracoherent answer sets with less resources
• Abstraction for non-ground answer set programs
• Abstract Solvers for Computing Cautious Consequences of ASP programs
• Cautious reasoning in ASP via minimal models and unsatisfiable cores
• Omission-based abstraction for answer set programs
• DynASP2.5: Dynamic Programming on Tree Decompositions in Action
• Debugging non-ground ASP programs: technique and graphical tools
• Technical note. Efficiently coupling the \(\mathscr{I}\)-DLV grounder with ASP solvers
• Unsatisfiable core analysis and aggregates for optimum stable model search
• Enhancing magic sets with an application to ontological reasoning
• Tunas -- fishing for diverse answer sets: a multi-shot trade up strategy
• Shared aggregate sets in answer set programming
• Strong inconsistency
• Unsatisfiability-based optimization in clasp

Describes a project that uses

Uses Software

• maxino
• WASP
• clasp
• DLV
• Cmodels

This page was built for publication: Anytime answer set optimization via unsatisfiable core shrinking

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