Optimization Strategies in Answer Set Programming, Enumerating Answer Sets by Optimality

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.