I want to make a first SAT solver. I know the SAT competition and the SAT conference, and there are just so many papers on this subject. I'm a starter, an overwhelmed starter. Where should I begin? Eventually I want to push the state-of-the-art. I want some expert advice on how to start, so that I won't be wasting my time on the non-essentials too early. Many thanks.
Tell me more
×
Theoretical Computer Science Stack Exchange is a question and answer site for
theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
|
|
|||||||||||||||||||||
|
|
I suggest first understanding which techniques really advanced the solvers, for which I would suggest the following overview and analysis. Then I would recommend downloading the source code of minisat and read its description. It might of course be individual but I found looking at the source code most valuable. |
|||
|
|
|
An excellent beginner overview is given by the following article from 2009.
There are several ways to get into the technical aspects. You can even start with the original Davis-Putnam paper. It is extremely clear and has detailed examples. When discussing SAT optimizations in a course, we discovered that a few one may imagine are already there. The Davis-Logeman-Loveland paper is (I feel) less instructive, but it is so short you may as well read it.
There are may ways to catch up on the developments of the next 50 years. I would recommend lecture slides. Just searching for 'DPLL' will throw up many many tutorials. If you browse through them, I'm sure the mist will clear -- to some extent. There are also many useful surveys. The Zhang-Malik paper is a good place to start. There are several articles in the Handbook of Satisfiability you may find useful.
I second the suggestion of Mikolaos. The MiniSAT code is clean and of manageable size. You can play with it. There are several other solvers you can try. CryptoMiniSat is also quite clean. You should also consult the work of Armin Biere, who writes SAT solvers and writes about writing SAT solvers. |
|||
|
|
|
If you're overwhelmed by all of the work that's out there, why don't you start out pretending that nobody's worked on the problem before? If your goal is to eventually build a competitive SAT solver, it's going to be a fairly long journey. By starting out just playing around without 'checking the solutions', so to speak, you have more to gain than to lose. First build the simplest solver you can and make sure it works. This will probably be a brute force algorithm whose running time depends more or less only on the $n$, the number of variables, and $m$, the number of clauses. Then implement something a little bit smarter like branch-and-bound. Write (or find) a generator that will give you random instances for given values of $n$ and $m$. Do some benchmarking tests for your branch-and-bound solver. See how it does for varying values of $n$ and $m$. Then improve your solver to make it faster. See how far you can get without reading about other work. When you run out of ideas, do some of the reading suggested in the other answers. |
|||
|
|
|
Start with a good survey paper. It's easy to attack the subject piecemeal and get confused by different names in the literature for the same techniques and the same name used for different techniques. It's also easy to re-enact old algorithmic battles (occur lists vs. head-tail lists vs. two watched literals for DPLL implementations for instance) if you don't know what the state of the art is. Satisfiability Solvers by Gomes, et. al. will give you the rough lay of the land. Improving SAT Solvers Using State-of-the-Art Techniques by Manthey will bring you closer to the present. |
|||
|
|
