M.Sc. Paul Saikko defends his doctoral thesis Implicit Hitting Set Algorithms for Constraint Optimization on Monday the 2nd of December 2019 at 12 o'clock noon in the University of Helsinki Exactum building, Auditorium B123 (Pietari Kalmin katu 5, 1st floor). His opponent is Professor Laurent Simon (University of Bordeaux, France) and custos Associate Professor Matti Järvisalo (University of Helsinki). The defence will be held in English.
The thesis of Paul Saikko is a part of research done in the Department of Computer Science and in the Constraint Reasoning and Optimization research group at the University of Helsinki. His supervisors have been Associate Professor Matti Järvisalo and Professor Petri Myllymäki (University of Helsinki).
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.
Availability of the dissertation
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.
Printed copies will be available on request from Paul Saikko: paul.saikko@cs.helsinki.fi.