M.Sc. Paul Saikko succesfully defended his doctoral dissertation Implicit Hitting Set Algorithms for Constraint Optimization on December 2, 2019. The thesis work was conducted in the Constraint Reasoning and Optimization group of the Department of Computer Science at the University of Helsinki, with Associate Professor Matti Järvisalo as the main PhD supervisor. Professor Laurent Simon (University of Bordeaux, France) acted as the opponent, and Professor Martin Gebser (University of Graz and University of Klagenfurt, Austria) and Professor David Mitchell (University of Waterloo, Canada) as pre-examiners. Congratulations Paul!
An electronic version of the doctoral dissertation is available on the e-thesis site of the University of Helsinki at http://urn.fi/URN:ISBN:978-951-51-5669-3.
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 ∑P2-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.