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.
$\begingroup$
$\endgroup$
6
-
6$\begingroup$ Have you already implemented the DPLL algorithm? Have you fine-tuned and polished your implementation so that it runs extremely fast? $\endgroup$– Jukka SuomelaAug 3, 2011 at 8:10
-
5$\begingroup$ The Handbook of Satisfiability - amazon.co.uk/… (perhaps check a library, the cost is pretty high). $\endgroup$– MGwynneAug 3, 2011 at 14:23
-
1$\begingroup$ @Jukka: comment -> answer ? $\endgroup$– Suresh VenkatAug 3, 2011 at 16:26
-
4$\begingroup$ I disagree with Jukka. Why reinvent the wheel? There's no reason to redo what MiniSAT already provides open source. If you're interested in adding to the CDCL framework your addition will show in boosted MiniSAT performance. Also, DPLL by itself is not enough; a lot of improvements have been made. Basically, follow Mikolas' answer! $\endgroup$– Huck BennettAug 4, 2011 at 5:14
-
1$\begingroup$ See also related question cstheory.stackexchange.com/q/1988 $\endgroup$– András SalamonAug 6, 2011 at 16:05
|
Show 1 more comment
4 Answers
$\begingroup$
$\endgroup$
An excellent beginner overview is given by the following article from 2009.
- Boolean Satisfiability: From Theoretical Hardness to Practical Success, Sharad Malik, Lintao Zhang, Communications of the ACM, 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.
- A Computing Procedure for Quantification Theory, Martin Davis, Hilary Putnam, Journal of the ACM, 1960.
- A machine program for theorem-proving, Martin Davis, George Logemann, Donald Loveland, Communications of the ACM, 1962.
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.
- The Quest for Efficient Boolean Satisfiability Solvers, Lintao Zhang, Sharad Malik, Joint invited paper for CAV and CADE 2002.
- Handbook of Satisfiability, Edited by Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, 2009
- Anatomy and Empirical Evaluation of Modern SAT Solvers, Karem Sakallah, Joao Marques-Silva, Bulletin of the EATCS, 2011.
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
