Implicit Hitting Set Algorithms for Constraint Optimization

Show full item record



Permalink

http://urn.fi/URN:ISBN:978-951-51-5669-3
Title: Implicit Hitting Set Algorithms for Constraint Optimization
Author: Saikko, Paul
Contributor: University of Helsinki, Faculty of Science, Department of Computer Science
Doctoral Programme in Computer Science
Publisher: Helsingin yliopisto
Date: 2019-12-02
URI: http://urn.fi/URN:ISBN:978-951-51-5669-3
http://hdl.handle.net/10138/306951
Thesis level: Doctoral dissertation (article-based)
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.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.
Subject: Computer Science
Rights: This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.


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 full item record