Solution Enumeration by Optimality in Answer Set Programming
Pajunen,Jukka; Janhunen,Tomi (2021-09-10)
THEORY AND PRACTICE OF LOGIC PROGRAMMING
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited
Julkaisun pysyvä osoite on
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.
- TUNICRIS-julkaisut 
Näytetään aineisto, joilla on samankaltaisia nimekkeitä, tekijöitä tai asiasanoja.
Maggioni,Matteo; Sanchez-Monge,Enrique; Foi,Alessandro (2014)
Supramolecular hierarchy among halogen and hydrogen bond donors in light-induced surface patterning Saccone,Marco; Dichiarante,Valentina; Forni,Alessandra; Goulet-Hanssens,Alexis; Cavallo,Gabriella; Vapaavuori,Jaana; Terraneo,Giancarlo; Barrett,Christopher J.; Resnati,Giuseppe; Metrangolo,Pierangelo; Priimägi,Arri (28.01.2015)
/dk/atira/pure/researchoutput/researchoutputtypes/contributiontojournal/articleHalogen bonding, a noncovalent interaction possessing several unique features compared to the more familiar hydrogen bonding, is emerging as a powerful tool in functional materials design. Herein, we unambiguously show ...
Virkki,Matti; Tuominen,Ossi; Forni,Alessandra; Saccone,Marco; Metrangolo,Pierangelo; Resnati,Giuseppe; Kauranen,Martti; Priimägi,Arri (2015)
/dk/atira/pure/researchoutput/researchoutputtypes/contributiontojournal/articleWe demonstrate that halogen bonding strongly enhances the nonlinear optical response of poled supramolecular polymer systems. We compare three nonlinear optical chromophores with similar electronic structures but different ...