---
title: "An Exact Inference Scheme for MinSAT"
authors:
  - "Chu Min Li"
  - "Felip Manyà"
doi: ""
url: "https://ijcai.org/proceedings/2015/278"
pdf: "https://ijcai.org/proceedings/2015/0278.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "1959-1964"
track: "Main Track"
keywords:
---

# An Exact Inference Scheme for MinSAT

Chu Min Li, Felip Manyà

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

## Abstract

We describe an exact inference-based algorithm for the MinSAT problem. Given a multiset of clauses Φ, the algorithm derives as many empty clauses as the maximum number of clauses that can be falsified in Φ by applying finitely many times an inference rule, and returns an optimal assignment. We prove the correctness of the algorithm, describe how it can be extended to deal with weighted MinSAT and weighted partial MinSAT instances, analyze the differences between the MaxSAT and MinSAT inference schemes, and define and empirically evaluate the MinSAT Pure Literal Rule.