Unsatisfiable Core Shrinking for Anytime Answer Set Optimization

Unsatisfiable Core Shrinking for Anytime Answer Set Optimization

Mario Alviano, Carmine Dodaro

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Best Sister Conferences. Pages 4781-4785. https://doi.org/10.24963/ijcai.2017/666

Efficient algorithms for the computation of optimum stable models are based on unsatisfiable core analysis. However, these algorithms essentially run to completion, providing few or even no suboptimal stable models. This drawback can be circumvented by shrinking unsatisfiable cores. Interestingly, the resulting anytime algorithm can solve more instances than the original algorithm.
Keywords:
Artificial Intelligence: knowledge representation and reasoning
Artificial Intelligence: artificial intelligence