Solution Enumeration by Optimality in Answer Set Programming

Jukka Pajunen, Tomi Janhunen

Research output: Contribution to journalArticleScientificpeer-review

4 Citations (Scopus)
19 Downloads (Pure)

Abstract

Given a combinatorial search problem, it may be highly useful to enumerate its (all) solutions besides just finding one solution, or showing that none exists. The same can be stated about optimal solutions if an objective function is provided. This work goes beyond the bare enumeration of optimal solutions and addresses the computational task of solution enumeration by optimality (SEO). This task is studied in the context of answer set programming (ASP) where (optimal) solutions of a problem are captured with the answer sets of a logic program encoding the problem. Existing answer set solvers already support the enumeration of all (optimal) answer sets. However, in this work, we generalize the enumeration of optimal answer sets beyond strictly optimal ones, giving rise to the idea of answer set enumeration in the order of optimality (ASEO). This approach is applicable up to the best k answer sets or in an unlimited setting, which amounts to a process of sorting answer sets based on the objective function. As the main contribution of this work, we present the first general algorithms for the aforementioned tasks of answer set enumeration. Moreover, we illustrate the potential use cases of ASEO. First, we study how efficiently access to the next-best solutions can be achieved in a number of optimization problems that have been formalized and solved in ASP. Second, we show that ASEO provides us with an effective sampling technique for Bayesian networks.
Original languageEnglish
Pages (from-to)750-767
Number of pages18
JournalTHEORY AND PRACTICE OF LOGIC PROGRAMMING
Volume21
Issue number6
Early online date10 Sept 2021
DOIs
Publication statusPublished - Nov 2021
Publication typeA1 Journal article-refereed

Keywords

  • Answer Set Programming
  • Optimization problems
  • Solution enumeration
  • Sampling
  • Bayesian networks

Publication forum classification

  • Publication forum level 2

Fingerprint

Dive into the research topics of 'Solution Enumeration by Optimality in Answer Set Programming'. Together they form a unique fingerprint.

Cite this