SoSAT

A SAT solver that uses different statistical optimization algorithms to solve SAT problems encoded in the DIMACS format. This solver is written in Python and uses Numpy to speed up calculations. The three main algorithms in this solver are a ant colony optimization algorithm, a genetic algorithm, and walkSAT. To support these algorithms, there are some preprocessing algorithms.

Features

• 3 optimization algorithms
  • ant colony optimization algorithm
  • genetic algorithm
  • walkSAT
• factorization, reduction and simulated annealing for preprocessing
• parallel evaluation from different starting points
• configurable profiles to parameterize the solver

See paper.pdf for more details about implementation details and an evaluation of the algorithms.

Installation

Create a virtual environment

virtualenv venv

Activate the virtual env

source venv/bin/activate

Install the solver

python setup.py install

Run it

sosat --help