Implicit Hitting Set Algorithms for Constraint Optimization

Show simple item record

dc.contributor Helsingin yliopisto, matemaattis-luonnontieteellinen tiedekunta fi
dc.contributor Helsingfors universitet, matematisk-naturvetenskapliga fakulteten sv
dc.contributor University of Helsinki, Faculty of Science, Department of Computer Science en
dc.contributor Tietojenkäsittelytieteen tohtoriohjelma fi
dc.contributor Doktorandprogrammet i datavetenskap sv
dc.contributor Doctoral Programme in Computer Science en
dc.contributor.author Saikko, Paul
dc.date.accessioned 2019-11-13T09:41:44Z
dc.date.available 2019-11-22
dc.date.available 2019-11-13T09:41:44Z
dc.date.issued 2019-12-02
dc.identifier.uri URN:ISBN:978-951-51-5669-3
dc.identifier.uri http://hdl.handle.net/10138/306951
dc.description.abstract Computationally hard optimization problems are commonplace not only in theory but also in practice in many real-world domains. Even determining whether a solution exists can be NP-complete or harder. Good, ideally globally optimal, solutions to instances of such problems can save money, time, or other resources. We focus on a particular generic framework for solving constraint optimization problems, the so-called implicit hitting set (IHS) approach. The approach is based on a theory of duality between solutions and sets of mutually conflicting constraints underlying a problem. Recent years have seen a number of new instantiations of the IHS approach for various problems and constraint languages. As the main contributions, we present novel instantiations of this generic algorithmic approach to four different NP-hard problem domains: maximum satisfiability (MaxSAT), learning optimal causal graphs, propositional abduction, and answer set programming (ASP). For MaxSAT, we build on an existing IHS algorithm with a fresh implementation and new methods for integrating preprocessing. We study a specific application of this IHS approach to MaxSAT for learning optimal causal graphs. In particular we develop a number of domain-specific search techniques to specialize the IHS algorithm for the problem. Furthermore, we consider two optimization settings where the corresponding decision problem is beyond NP, in these cases Σᴾ₂-hard. In the first, we compute optimal explanations for propositional abduction problems. In the second, we solve optimization problems expressed as answer set programs with disjunctive rules. For each problem domain, we empirically evaluate the resulting algorithm and contribute an open-source implementation. These implementations improve or complement the state of the art in their respective domains. en
dc.description.abstract Käytännön sovellutuksista kumpuavat optimointiongelmat ovat usein laskennallisesti haastavia. Deklaratiiviset menetelmät tarjoavat keskeisen tavan lähestyä erinäisiä laskennallisesti haastavia optimointiongelmia. Deklaratiivisissa lähestymistavoissa ratkaistavana oleva ongelma mallinnetaan yleisesti matemaattisina rajoitteina siten, että alkuperäisen ongelman instanssien rajoitekuvauksen rajoitteet voidaan toteuttaa jos ja vain jos ongelmainstanssille on olemassa ratkaisu. Ratkaisujen löytäminen rajoitekuvaukselle edellyttää yleisten algoritmisten ratkaisumenetelmien kehittämistä rajoitekuvauskielille. Tässä väitöskirjassa kehitetään uudentyyppisiä käytännöllisiä eksakteja deklaratiivisia ratkaisumenetelmiä jotka pohjautuvat ns. implicit hitting set (IHS) -optimointialgoritmiparadigmaan. Erityisesti työssä kehitetään ja toteutetaan IHS-pohjaisia menetelmiä neljälle laskennallisesti haastavalle, tekoälytutkimuksen näkökulmasta motivoidulle NP-kovalle optimointiongelmalle: lauselogiikan optimointilaajennukselle (MaxSAT), keskeiselle epämonotonisen päättelyn lähestymistavalle (answer set optimization, ASP), lauseloogiselle abduktiolle, sekä optimaalisten kausaaliverkkojen löytämisongelmalle. Työssä kehitetään sekä yleisiä että ongelmakohtaisia hakutekniikoita IHS-kontekstissa, kehitetään avoimen lähdekoodin implementaatioita, ja osoitetaan empiriisten evaluaatioiden kautta näiden olevan käytännössä varteenotettavia vaihtoehtoja kunkin ongelman tehokkaaseen ratkaisemiseen. fi
dc.format.mimetype application/pdf
dc.language.iso en
dc.publisher Helsingin yliopisto fi
dc.publisher Helsingfors universitet sv
dc.publisher University of Helsinki en
dc.relation.isformatof URN:ISBN:978-951-51-5668-6
dc.relation.isformatof Helsinki: Unigrafia, 2019, Department of Computer Science Series of Publications A. 1238-8645
dc.rights Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty. fi
dc.rights This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited. en
dc.rights Publikationen är skyddad av upphovsrätten. Den får läsas och skrivas ut för personligt bruk. Användning i kommersiellt syfte är förbjuden. sv
dc.subject Computer Science
dc.title Implicit Hitting Set Algorithms for Constraint Optimization en
dc.type.ontasot Väitöskirja (artikkeli) fi
dc.type.ontasot Doctoral dissertation (article-based) en
dc.type.ontasot Doktorsavhandling (sammanläggning) sv
dc.ths Järvisalo, Matti
dc.ths Myllymäki, Petri
dc.opn Simon, Laurent
dc.type.dcmitype Text

Files in this item

Total number of downloads: Loading...

Files Size Format View
implicit.pdf 408.8Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record