nextthought.mosoi.ro
Next Thought: Improving Branching. Part. II: Polarity
http://nextthought.mosoi.ro/2011/02/improving-branching-part-ii-polarity.html
A blog about my CS adventures. Thursday, February 24, 2011. Improving Branching. Part. II: Polarity. I concluded that variable's polarity searched first affects the solving time of some instances (mostly of satisfiable instances of course). With this in mind I ran four tests with the branching heuristic modified as follows. Branch first on positive polarity. Branch first on polarity with the highest score. Branch first on polarity with the lowest score. Branch first on a random polarity. The current algo...
nextthought.mosoi.ro
Next Thought: Blocked Clause Elimination
http://nextthought.mosoi.ro/2011/02/blocked-clause-elimination.html
A blog about my CS adventures. Tuesday, February 22, 2011. I just finished implementing a technique Blocked Clause Elimination. BCE) The idea is that for a literal. R = C ⊗. Is a tautology (where. Is the resolution operator on literal. Can be eliminated. The removed clause. Is said to be blocked on literal. You can check Mate Soos' post. On the same topic. Before reasoning first time. Should speedup first node evaluation. The previous two combined. Was at least as good as. Posted by Alexandru Moșoi.
nextthought.mosoi.ro
Next Thought: Gasca (yet another CDCL sat solver)
http://nextthought.mosoi.ro/2012/01/gasca-yet-another-cdcl-sat-solver.html
A blog about my CS adventures. Monday, January 16, 2012. Gasca (yet another CDCL sat solver). I have release today another sat solver. Gasca is a pure CDCL (Conflict-Driven Clause-Learning) SAT solver written in Go. It was written before I joined Google in Oct. 2011 as a very short project to understand some alternatives to the ideas in my master thesis. Some pieces of code are inspired from Minisat. Though Gasca is not a port to Go of neither of them. Go ahead, clone my repository and try it out:. Impro...
nextthought.mosoi.ro
Next Thought: SAT Competition 2011
http://nextthought.mosoi.ro/2011/03/sat-competition-2011.html
A blog about my CS adventures. Wednesday, March 2, 2011. I've submitted the solver just now for SAT Competition 2011. The submission can be downloaded from here. And the sources from here. Note the git tag sc11). There is a huge gap between STRUCTure and CryptoMiniSat 2.6.0. As it turns out I had a bug that rendered extraction of XOR gates ineffective on my SAT Competition 2011 submission. No wonder why adjusting the coefficient for XOR gates in branching heuristic didn't influence the results. Improving...
nextthought.mosoi.ro
Next Thought: How fast can you sort 50,000,000 normal distributed doubles?
http://nextthought.mosoi.ro/2011/06/how-fast-can-you-sort-50000000-normal.html
A blog about my CS adventures. Thursday, June 16, 2011. How fast can you sort 50,000,000 normal distributed doubles? This is a post about a contest. You are given 50,000,000 real numbers (IEEE 794 doubles) normal distributed with mean 0 and standard deviation 1. Sort them as fast as possible. The target machine is a quad core cpu and with 4GB of RAM (thanks to static rtti for doing the measurements). Is to see if the distribution can be taken into account to improve sorting speed. Finalize sorting. I...
nextthought.mosoi.ro
Next Thought: March 2011
http://nextthought.mosoi.ro/2011_03_01_archive.html
A blog about my CS adventures. Thursday, March 10, 2011. Until recently STRUCTure handled binaries separetly using the implications graph. The problem with this scheme is that binaries need special attention which complicates the design and the implementation. I decided to give binaries a less special status and keep them both in the watch lists and implications graph. Needless to say, the code was greatly simplified. Posted by Alexandru Moșoi. Thursday, March 10, 2011. Sunday, March 6, 2011. This mornin...
nextthought.mosoi.ro
Next Thought: Dependent Variables
http://nextthought.mosoi.ro/2011/03/dependent-variables.html
A blog about my CS adventures. Wednesday, March 2, 2011. Let's talk a little about XOR clauses. If you have a variable that appears in a single XOR we can remove that clause because it always can be satisfied by setting the proper value of the chosen variable. Let's call this variable dependent. I was reading Mate Soos's paper. A b c d e f and = 1. Text{can be split into}. A b c z and = 0. Z d e f and = 1. With $z$ being a mutex. Posted by Alexandru Moșoi. Wednesday, March 02, 2011. This is a post about ...
nextthought.mosoi.ro
Next Thought: Tale about binaries
http://nextthought.mosoi.ro/2011/03/tale-about-binaries.html
A blog about my CS adventures. Thursday, March 10, 2011. Until recently STRUCTure handled binaries separetly using the implications graph. The problem with this scheme is that binaries need special attention which complicates the design and the implementation. I decided to give binaries a less special status and keep them both in the watch lists and implications graph. Needless to say, the code was greatly simplified. Posted by Alexandru Moșoi. Thursday, March 10, 2011. Subscribe to: Post Comments (Atom).
