Matti Järvisalo
The Implicit Hitting Set Approach and Preprocessing for Maximum Satisfiability Solving
VCLA hosting a talk by Matti Järvisalo
DATE: | Friday, September 29, 2017 |
TIME: | 14:00 c.t. |
VENUE: | Seminarraum Goedel, Favoritenstrasse 9-11 |
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.