Skip to content
No description or website provided.
C C++ Python Makefile
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.gitignore
LICENSE
Makefile
README.md
experiment_runner.py
formula.cpp
formula.h
generate_xor_cnf.py
merge.cpp
queue.cpp
queue.h
random.c
random.h
sp.cpp
sp.h
verify.cpp
walksat.c

README.md

Streamlined Survey Propogation

This repository provides a reference implementation for solving constraint satisfaction problems via streamlined survey propogation as described in the paper:

Streamlining Variational Inference for Constraint Satisfaction Problems
Aditya Grover, Tudor Achim, Stefano Ermon
Advances in Neural Information Processing Systems (NeurIPS), 2018
Paper: http://arxiv.org/abs/1811.09813

General

The codebase has been built on top of the survey propogation implementation of A. Braunstein, M. Mezard, and R. Zecchina as described in the paper "Survey propagation: an algorithm for satisfiability". It is implemented in C/C++ and tested on Ubuntu 16.04.

Setup

To compile the binaries run the following command from the root directory

make all

This will create a binary file for sp in the root directory (and others which will be directly accessed by sp).

Options

For a full list of options, run:

./sp -h

Key options are described below:

  -l CSP in CNF representation (if none provided, random k-SAT instance is generated)
  -k length of each clause 
  -n number of variables 
  -m number of clauses 
  -a clause/variable ratio
  -s seed for reproducibility
  -% percentage of paired disjunctions (denoted as R in the paper)
  -t number of streamlining iterations (denoted as T in the paper)
  -d limit on the streamlined disjunctions per variable
  -p prefix path where all the generated files (cnf formula, streamlined formula etc.) are dumped
  

Examples

Baseline survey inspired decimation on a random 3-SAT instance with 50,000 variables and clause to variable ratio of 4.235:

./sp -n50000 -a4.235 -k3 -%1 -t0 -d2 -s1

Survey inspired streamlining for the same problem instance:

./sp -n50000 -a4.235 -k3 -%1 -t90 -d2 -s1

Survey inspired streamlining for an arbitrary CSP accessed via the filepath csp/1.cnf:

./sp -%1 -lcsp/1.cnf -t80

Citing

If you find this codebase useful in your research, please consider citing the following paper:

@inproceedings{grover2018streamlining,
title={Streamlining Variational Inference for Constraint Satisfaction Problems},
author={Grover, Aditya and Achim, Tudor and Ermon, Stefano},
booktitle={Advances in Neural Information Processing Systems},
year={2018}}

You can’t perform that action at this time.