Tailoring Local Search for Partial MaxSAT

Authors

  • Shaowei Cai Chinese Academy of Sciences
  • Chuan Luo Peking University
  • John Thornton Griffith University
  • Kaile Su Griffith University

DOI:

https://doi.org/10.1609/aaai.v28i1.9109

Keywords:

Partial MaxSAT, Local Search

Abstract

Partial MaxSAT (PMS) is a generalization to SAT and MaxSAT. Many real world problems can be encoded into PMS in a more natural and compact way than SAT and MaxSAT. In this paper, we propose new ideas for local search for PMS, which mainly rely on the distinction between hard and soft clauses. We use these ideas to develop a local search PMS algorithm called {\it Dist}. Experimental results on PMS benchmarks from MaxSAT Evaluation 2013 show that {\it Dist} significantly outperforms state-of-the-art PMS algorithms, including both local search algorithms and complete ones, on random and crafted benchmarks. For the industrial benchmark, {\it Dist} dramatically outperforms previous local search algorithms and is comparable with complete algorithms.

Downloads

Published

2014-06-21

How to Cite

Cai, S., Luo, C., Thornton, J., & Su, K. (2014). Tailoring Local Search for Partial MaxSAT. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.9109

Issue

Section

Main Track: Search and Constraint Satisfaction