The Implicit Hitting Set Approach and Preprocessing for Maximum Satisfiability Solving

VCLA hosting a talk by Matti Järvisalo

ABSTRACT

The Boolean optimization paradigm of maximum satisfiability (MaxSAT) offers today a competitive approach to exactly solving various types of NP-hard optimization problems. This talk concerns algorithmic techniques for MaxSAT. The talk divides into two parts. In the first part, we overview the successful implicit hitting set approach to MaxSAT, and point out how the general framework can be applied to other beyond-NP reasoning problems. In the second part, we overview recent work on developing preprocessing techniques for MaxSAT, applied before search for an optimal solution.

Matti Järvisalo, University of Helsinki