Tag Archives: MaxSAT

Excellent performance in the MaxSAT Evaluation

The MaxSAT Evaluation is an annual event meant to evaluate the state of the art in MaxSAT solving technology. The evaluation has two tracks: the complete track, where the goal is to find the provably optimal solution as fast as possible and the incomplete track where the goal is to find a solution which is as good as possible within a limited time.

This year we submitted a solver called Loandra to the incomplete track of the competition. Loandra implements core boosted linear search, an idea described in this paper that I worked on during my visit to Melbourne last fall. The results of the Evaluations were presented yesterday at the SAT conference, I’ve only seen a summary but I am happy to say that Loandra performed very well, achieving the highest score on the unweighted 300s track and the second to highest on the weighted 300s track. Overall a very nice result, I am very pleased.

I’d like to thank the organizers of the MaxSAT evaluation as well as my co-authors, Emir Demirovic and Peter Stuckey! I am currently on a holiday, but once I get back I will put up Loandra on github as well. It will also eventually be made available here.

EDIT: Loandra is now available at: https://github.com/jezberg/loandra

 

A new publication

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.