Implicit Hitting Set Algorithms for Constraint Optimization

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