An Efficient Method to Transform SAT problems to Binary Integer Linear Programming Problem

Wenxia Guo, Jin Wang, Majun He, Xiaoqin Ren, Wenhong Tian, Qingxian Wang

TL;DR

This paper introduces LIMSAT, a novel method for transforming Boolean Satisfiability (SAT) problems into Binary Integer Linear Programming (ILP) problems. This approach aims to efficiently solve large-scale SAT instances by leveraging the power of ILP solvers, offering a promising alternative to traditional SAT-solving techniques.

What Problem Does This Paper Address?

Computational complexity theory classifies many important problems as NP-complete. While solutions to these problems can be verified quickly (in polynomial time), finding a solution is generally believed to require super-polynomial time. The Satisfiability (SAT) problem, a cornerstone of NP-completeness, asks whether a given Boolean formula can be satisfied. Existing methods to transform SAT problems into other forms, like Subset Sum Problems (SSP), often struggle with large instances due to computational complexity. This paper addresses the challenge of efficiently transforming large SAT problems into a format solvable by Integer Linear Programming (ILP) solvers, aiming to overcome the limitations of existing reduction techniques.

Methods

The paper proposes a new method called LIMSAT. It builds upon existing work that reduces SAT to Subset Sum Problems (SSP) but aims to improve efficiency for larger instances. Instead of directly reducing SAT to SSP, LIMSAT transforms SAT into a Binary Integer Linear Programming (ILP) problem. The core idea is to represent the SAT problem's constraints and variables within a linear inequality model. This involves constructing a specific matrix based on the CNF (Conjunctive Normal Form) of the SAT problem. The method then formulates an ILP problem with constraints of the form $xA \le b$, where $x$ is the decision variable vector, $A$ is a matrix derived from the SAT formula, and $b$ is a target vector. The goal is to find a binary solution ($x \in \{0,1\}$) that satisfies these inequalities, indicating the satisfiability of the original SAT problem.

Datasets

The paper evaluates its method on several datasets:

  • uf250-1065: A set of 100 instances with 250 variables and 1065 clauses, all known to be SAT.
  • SAT Competition 2016 Main-Crafted Benchmarks: A collection of instances from the SAT competition, used to test the algorithm's performance on challenging problems.

Key Insights and Ideas

  • Bridging SAT and ILP: The paper highlights the potential of ILP solvers as a powerful tool for tackling SAT problems, especially when traditional SAT solvers face scalability issues.
  • Efficient Matrix Construction: LIMSAT aims to create a more manageable ILP formulation compared to previous SSP reduction methods, particularly by avoiding slack variables and focusing on direct variable and clause representations.
  • Scalability Potential: By transforming SAT into ILP, the authors suggest a path towards solving larger and more complex SAT instances than previously feasible with certain reduction techniques.

Key Results

The experimental results demonstrate the effectiveness of the LIMSAT method.

  • The algorithm correctly identified the satisfiability of the 100 uf250-1065 instances.
  • When applied to SAT competition problems (specifically main-crafted instances), the Gurobi solver, utilizing the LIMSAT-generated ILP model, performed well. Out of the tested instances, 58 were solved.
  • The paper notes that the Gurobi solver, based on the 0-1 ILP model, shows good performance, even outperforming the best solver in the SAT competition 2016 for the main-craft category in terms of the number of instances solved.

Limitations and Future Work

  • Future Work: The authors plan to improve the efficiency of their implementation, specifically by exploring the use of parallel algorithms to further enhance performance in dealing with SAT problems.
  • Implicit Limitation: While the paper claims efficiency for "very large size problem with thousands of variables and clauses," the experimental results presented focus on specific benchmark sets. The full extent of its scalability across all types of large SAT instances is an area for continued investigation.

Summary updated

Abstract

In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard. Although a solution to a NP-complete can be verified quickly, there is no known algorithm to solve it in polynomial time. There exists a method to reduce a SAT (Satifiability) problem to Subset Sum Problem (SSP) in the literature, however, it can only be applied to small or medium size problems. Our study is to find an efficient method to transform a SAT problem to a mixed integer linear programming problem in larger size. Observing the feature of variable-clauses constraints in SAT, we apply linear inequality model (LIM) to the problem and propose a method called LIMSAT. The new method can work efficiently for very large size problem with thousands of variables and clauses in SAT tested using up-to-date benchmarks.
BibTeX
@misc{guo2018efficient,
  author = {Wenxia Guo and Jin Wang and Majun He and Xiaoqin Ren and Wenhong Tian and Qingxian Wang},
  title = {{An Efficient Method to Transform SAT problems to Binary Integer Linear Programming Problem}},
  year = {2018},
  eprint = {1803.09963},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1803.09963},
}
Figure