Optimization Strategies in Answer Set Programming, Enumerating Answer Sets by Optimality
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2020-06-16
Department
Major/Subject
Computer Science
Mcode
SCI3042
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
Language
en
Pages
76 + 14
Series
Abstract
Answer set programming (ASP) is a declarative programming paradigm that can be used to solve hard combinatorial problems. Optimization problems are one example of combinatorial problem that ASP has had success with. However, ASP solvers can be used only to find strictly optimal solutions while there are no guarantees about other solutions. Enumeration of answer sets in order of their optimality can give better insight to problem instance that is being solved while the enumeration can also be used for more specific use cases. Historically there has been little interest in developing general algorithms that can enumerate answer sets in order of their optimality. This thesis presents how to write implementations that can be used to solve this problem of optimal enumeration. Ultimately, this work hopes to provide motivation for further algorithms that enumerate optimal answer sets. Algorithms presented in this thesis are evaluated against general optimization problems to research viability of optimal answer set enumeration. It is found that the algorithms work well on general optimization problems and further research in enumerating optimal answer sets is reasonable. Enumeration algorithms are also tested in a special case study, namely for query answering in context of Bayes networks. It illustrates that the enumeration of optimal answer sets may have very special applications, giving more grounds for further development of such enumeration algorithms.Vastausjoukko-ohjelmointi on ongelmanratkontamenetelmä, jota voidaan käyttää ratkaisemaan vaikeita kombinatoorisia ongelmia. Optimointiongelmat ovat yksi esimerkki tällaisista vaikeista kombinatorisista ongelmista, joita voidaan ratkaista käyttämällä vastausjoukko-ohjelmointia. Vastausjoukko-ohjelma palauttaa tyypillisesti vain ongelman parhaan ratkaisun, mutta se ei ota kantaa muiden ratkaisujen hyvyyteen. Kuitenkin, vastausten läpikäyminen niiden paremmuusjärjestyksessä voi antaa paremman kuvan ongelmasta, jota ollaan ratkaisemassa. Vastausten läpikäymisellä optimaalisuusjärjestyksessä on olemassa myös muitakin ongelmakohtaisia käyttökohteita. Historiallisesti ottaen, vastausjoukkojen läpikäymistä paremmuusjärjestyksessä ei ole tutkittu. Tässä diplomityössä tutkimme eri tapoja, joilla näitä vastausjoukkoja voidaan käydä läpi. Diplomityön tarkoitus on kartoittaa vastausjoukkoja läpikäyvien algoritmien tarpeellisuutta ja suorituskykyä. Tällä diplomityöllä haluamme myös herättää kiinnostusta tällaisten algoritmien lisäkehitykseen. Diplomityötä varten kehitetyt algoritmit on arvioitu käyttäen erilaisia optimointiongelmia. Löytämämme tulokset viittaavat, että vastausjoukkojen läpikäynti on mahdollista ja parempien algoritmien kehitys on tarpeellista. Esitetyt algoritmit on myös testattu erityisessä ongelmakohtaisessa käytössä: Bayes-verkkoihin liittyvien kyselyjen evaluoinnissa. Työssä tehdyt kokeet tukevat näkemystä, että vastausjoukkojen läpikäymisellä optimaalisuusjärjestyksessä, on myös hyvin kiinnostavia sovelluksia.Description
Supervisor
Janhunen, TomiThesis advisor
Janhunen, TomiKeywords
answer set programming, answer set enumeration, optimization programs, sampling, vastausjoukkojen läpikäynti, vastausjoukko-ohjelmointi