Anytime answer set optimization via unsatisfiable core shrinking
From MaRDI portal
Publication:4593041
DOI10.1017/S147106841600020XzbMATH Open1379.68033DBLPjournals/tplp/AlvianoD16arXiv1608.00731OpenAlexW2505202112WikidataQ62043813 ScholiaQ62043813MaRDI QIDQ4593041
Publication date: 9 November 2017
Published in: Theory and Practice of Logic Programming (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1608.00731
Cites Work
- Title not available (Why is that?)
- Advances in WASP
- Extending and implementing the stable model semantics
- Semantics and complexity of recursive aggregates in answer set programming
- Logic programs with stable model semantics as a constraint programming paradigm
- Answer set programming based on propositional satisfiability
- Complex optimization in answer set programming
- Theory and applications of satisfiability testing -- SAT 2009. 12th international conference, SAT 2009, Swansea, UK, June 30--July 3, 2009. Proceedings
- Theory and applications of satisfiability testing -- SAT 2006. 9th international conference, Seattle, WA, USA, August 12--15, 2006. Proceedings.
- Unsatisfiability-based optimization in clasp
- Theory and applications of satisfiability testing -- SAT 2008. 11th international conference, SAT 2008, Guangzhou, China, May 12--15, 2008. Proceedings
- Logic Programming and Nonmonotonic Reasoning
- Logic programs with monotone abstract constraint atoms
- Logic programs with propositional connectives and aggregates
- Accelerated Deletion-based Extraction of Minimal Unsatisfiable Cores
- The Complexity Boundary of Answer Set Programming with Generalized Atoms under the FLP Semantics
- Vicious Circle Principle and Logic Programs with Aggregates
- The Design of the Sixth Answer Set Programming Competition
- Answer Set Programming: A Primer
- Logic programs with abstract constraint atoms: the role of computations
- Progress in clasp Series 3
- Multi-criteria optimization in answer set programming
- Rewriting recursive aggregates in answer set programming: back to monotonicity
- Complexity and compilation of GZ-aggregates in answer set programming
- Anytime Computation of Cautious Consequences in Answer Set Programming
Cited In (14)
- Omission-Based Abstraction for Answer Set Programs
- Model enumeration in propositional circumscription via unsatisfiable core analysis
- Efficiently Coupling the I-DLV Grounder with ASP Solvers
- Abstraction for non-ground answer set programs
- Debugging Non-ground ASP Programs: Technique and Graphical Tools
- Unsatisfiable Core Analysis and Aggregates for Optimum Stable Model Search
- Abstract Solvers for Computing Cautious Consequences of ASP programs
- Enhancing Magic Sets with an Application to Ontological Reasoning
- Cautious reasoning in ASP via minimal models and unsatisfiable cores
- DynASP2.5: Dynamic Programming on Tree Decompositions in Action
- Better Paracoherent Answer Sets with Less Resources
- Tunas -- fishing for diverse answer sets: a multi-shot trade up strategy
- Shared aggregate sets in answer set programming
- Strong inconsistency
Uses Software
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)
