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.
Symmetry is another characteristic of SAT problem. Jo @cite_10 present symmetric explanation learning (SEL), in which symmetric clauses are learned only when they are unit or conflicting. 1300 benchmark instances indicate that among GLUCOSE, BREAKID, SEL, SP, SLS, SEL outperforms other four solver configurations and as a dynamic symmetry handling technique, SEL is the first one competitive with static symmetry breaking which is known to the most effective way to handle symmetry. In terms of symmetry, C.K @cite_14 as well propose a method transforming unavoidable sub-graphs to SAT, which can make up for the shortcomings of SAT solvers.
@cite_14 @cite_10
1518653692 2742197492
Abstract We show that the maximum independent set problem on an n-vertex graph can be solved in 1.1996 n n O ( 1 ) time and polynomial space, which even is faster than Robson's 1.2109 n n O ( 1 ) -time exponential-space algorithm published in 1986. We also obtain improved algorithms for MIS in graphs with maximum degree 6 and 7, which run in time of 1.1893 n n O ( 1 ) and 1.1970 n n O ( 1 ) , respectively. Our algorithms are obtained by using fast algorithms for MIS in low-degree graphs in a hierarchical way and making a careful analysis on the structure of bounded-degree graphs. The presence of symmetry in Boolean satisfiability (SAT) problem instances often poses challenges to solvers. Currently, the most effective approach to handle symmetry is by static symmetry breaking, which generates asymmetric constraints to add to the instance. An alternative way is to handle symmetry dynamically during solving. As modern SAT solvers can be viewed as propositional proof generators, adding a symmetry rule in a solver’s proof system would be a straightforward technique to handle symmetry dynamically. However, none of these proposed symmetrical learning techniques are competitive to static symmetry breaking. In this paper, we present symmetric explanation learning, a form of symmetrical learning based on learning symmetric images of explanation clauses for unit propagations performed during search. A key idea is that these symmetric clauses are only learned when they would restrict the current search state, i.e., when they are unit or conflicting. We further provide a theoretical discussion on symmetric explanation learning and a working implementation in a state-of-the-art SAT solver. We also present extensive experimental results indicating that symmetric explanation learning is the first symmetrical learning scheme competitive with static symmetry breaking.