Added algorithm lllwalk

18 views

Skip to first unread message

unread,

Mar 24, 2012, 9:01:57 PM3/24/12

to ubcsat

From a request from Dimitris Achlioptas, I added a new algorithm I called lllwalk.

it appears in 1.2 beta13

It's named aver the "Lovász Local Lemma" and it was prompted by a paper from Robin A. Moser.

In short, it selects an unsat clause and then flips each variable with some probability (default is 1/2).

The bigger issue for me how to handle algorithms with "multi-flip" steps.

For now, it just splits the single step into several smaller steps, but it's an issue I want to address in version 2.0.