Approximation Strategies for Incomplete MaxSAT

Incomplete MaxSAT solving aims to quickly find a solution that attempts to minimize the sum of the weights of the unsatisfied soft clauses without providing any optimality guarantees. In this paper, we propose two approximation strategies for improving incomplete MaxSAT solving. In one of the strate...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-06
Main Authors: Joshi, Saurabh, Kumar, Prateek, Martins, Ruben, Rao, Sukrut
Format: Article
Language:English
Subjects:
Approximation
Mathematical analysis
Optimization
Solvers
Weight
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Incomplete MaxSAT solving aims to quickly find a solution that attempts to minimize the sum of the weights of the unsatisfied soft clauses without providing any optimality guarantees. In this paper, we propose two approximation strategies for improving incomplete MaxSAT solving. In one of the strategies, we cluster the weights and approximate them with a representative weight. In another strategy, we break up the problem of minimizing the sum of weights of unsatisfiable clauses into multiple minimization subproblems. Experimental results show that approximation strategies can be used to find better solutions than the best incomplete solvers in the MaxSAT Evaluation 2017.
ISSN:2331-8422