---
title: "Improving the Effectiveness of SAT-Based Preprocessing for MaxSAT"
authors:
  - "Jeremias Berg"
  - "Paul Saikko"
  - "Matti Järvisalo"
doi: ""
url: "https://ijcai.org/proceedings/2015/40"
pdf: "https://ijcai.org/proceedings/2015/0040.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "239-244"
track: "Main Track"
keywords:
---

# Improving the Effectiveness of SAT-Based Preprocessing for MaxSAT

Jeremias Berg, Paul Saikko, Matti Järvisalo

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 239-244.

## Abstract

Solvers for the Maximum satisfiability (MaxSAT) problem find an increasing number of applications today. We focus on improving MaxHS — one of the most successful recent MaxSAT algorithms — via SAT-based preprocessing. We show that employing SAT-based preprocessing via the so-called labelled CNF (LCNF) framework before calling MaxHS can in some cases greatly degrade the performance of the solver. As a remedy, we propose a lifting of MaxHS that works directly on LCNFs, allowing for a tighter integration of SAT-based preprocessing and MaxHS. Our empirical results on standard crafted and industrial weighted partial MaxSAT Evaluation benchmarks show overall improvements over the original MaxHS algorithm both with and without SAT-based preprocessing.