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 language | English |
---|---|
Pages (from-to) | 750-767 |
Number of pages | 18 |
Journal | THEORY AND PRACTICE OF LOGIC PROGRAMMING |
Volume | 21 |
Issue number | 6 |
Early online date | 10 Sept 2021 |
DOIs | |
Publication status | Published - Nov 2021 |
Publication type | A1 Journal article-refereed |
Keywords
- Answer Set Programming
- Optimization problems
- Solution enumeration
- Sampling
- Bayesian networks
Publication forum classification
- Publication forum level 2