The new decade has started well for me with two accepted publications already.
The first one, Preprocessing in Incomplete MaxSAT Solving is joint work with Marcus Leivo and Matti järvisalo, and is also Marcus first publication! The paper investigates the effect that preprocessing has on the non-optimal solutions of MAxSAT instances. The paper ties my recent work on incomplete MaxSAT solving with my earlier work on MaxSAT preprocessing and I am very excited to push this line of research further. It will be published in the proceedings of the 2020 ECAI conference. I will most likely be travelling there myself to present this work, we are also looking into proposing a tutorial for the conference.
The second paper, Core-Guided and Core-Boosted Search for CP, extends and generalises my work on incomplete MaxSAT solving to the more general finite domain constraint programming paradigm. The paper is joint work with Graeme Grange, Emir Demirovic and Peter Stuckey from Australia. I am surprised and pleased to see that our previous work on MaxSAT seems to work so well in CP solving as well. The paper will be published in the proceedings of the 2020 CPAIOR conference. I will most likely not travel there myself, but I am sure that my co-authors will do the paper justice.
I’d like to thank all my co-authors for their work, it’s been a pleasure collaborating and hopefully we can continue doing so. The papers will be added to this webpage when the publishing process is done. If you want to read them earlier, feel free to send me an e-mail.
My paper “Unifying Reasoning and Core-Guided Search for Maximum Satisfiability” got accepted for publication at JELIA 2019. The paper reports on a theoretical investigation of the correctness MaxSAT solving techniques that can be seen as instance transformations. In fact, many approaches to MaxSAT solving transform a MaxSAT instance to be solved while preserving an optimal solution until the optimal solution is in some sense “trivial” to find (details in the paper).
We show that previously established theoretical notions for establishing the correctness of such methods are not general enough to capture all modern MaxSAT solving techniques, thus making the development of solvers that combine different methods difficult. We also propose a new type of instance transformation that covers all previously proposed notions that we are aware off. Finally we also generalize some known results from reasoning techniques from SAT solving to MaxSAT, thus bridging the gap between SAT solving and MaxSAT solving.
I am exited about this line of work, it feels like there is more to understand in this direction, hopefully I can extend this work in the near future.
Our publication Solving Graph Problems via Potential Maximal Cliques: An Experimental Evaluation of the Bouchitté-Todinca Algorithm has been accepted for publication in the ACM Journal of Experimental Algorithmics. The article is currently in press, let me know if you are interested in reading it. I am the second author on this publication, with Tuukka Korhonen as the first and my PhD advisor Matti Järvisalo as the third.
The paper reports on an experimental evaluation of the so called Bouchitté-Todinca (BT) Algorithm for computing various graph parameters, including the treewidth and minimum fill of a graph. While the algorithm is the theoretically best known one for computing most of these parameters, there has not been many practical evaluations of it, most likely due to it being quite complicated to implement in practice. In this paper we provide an experimental evaluation of Tuukkas implementation that took second place in the minimum fill in track of the 2017 PACE challenge on 5 different graph problems. In the paper we show that Tuukas implementation of the BT algorithm is competitive with many previously proposed, problem specific algorithms, on all of the problems we consider. My role in this paper was to familiarize myself with and write about the theoretical foundations of the algorithm as well as provide input on what kind of experiments we should run. I liked working on this project as it allowed me to familiarize myself with something else than constraint programming.
Thanks to both Tuukka and Matti for their work in making this happen.