algorithms.txt

#
#     ##  ##  #####    #####   $$$$$   $$$$   $$$$$$    
#     ##  ##  ##  ##  ##      $$      $$  $$    $$      
#     ##  ##  #####   ##       $$$$   $$$$$$    $$      
#     ##  ##  ##  ##  ##          $$  $$  $$    $$      
#      ####   #####    #####  $$$$$   $$  $$    $$      
# ======================================================
# SLS SAT Solver from The University of British Columbia
# ======================================================
# ...Developed by Dave Tompkins (davet [@] cs.ubc.ca)...
# ------------------------------------------------------
#
#
# This file describes the algorithms currently available in UBCSAT
#
# You can view a more user-friendly and prettier version at:
# http://www.satlib.org/ubcsat/algorithms
#
# For entries such as {academic} in brace brackets, see the Notes at the bottom
#
To the best of our knowledge all algorithms in UBCSAT behave identically to their orginal implementation.  While the exact results may differ (because of different random search trajectories, etc.) over several runs the run-length distributions generated by UBCSAT are equivalent to those produced by the original algorithms.

For most algorithms the UBCSAT implementation is faster (or just as fast) as the original implementation.  In the few circumstances where UBCSAT is slower the difference is usually due to UBCSAT reporting overhead and can be eliminated by turning off reports (use parameters: -r out null -r stats null).

= Adaptive G2WSAT
> [LiWeiZha07]
* Uses Novelty+ as the WalkSAT algorithm and selects the oldest (not best) decreasing promising variable.
* {g2wsat}

= Adaptive G2WSAT+p
> [LiWeiZha07]
* Uses Novelty+p as the WalkSAT algorithm.
* {g2wsat}

= Adaptive Novelty+
> [Hoos02]
- -alg adaptnovelty+
* There was an typo in the paper for updating wp: It should be wp := wp - wp * phi / 2.  The results in the paper, the original implementation and the UBCSAT implementation are all based on this corrected value.
* In the paper, the noise being adapted is the novelty noise (-novnoise in the novelty algorithm), not the random walk parameter (-wp) which is set to 0.01 by default in Adaptive Novelty+.
* {adaptnoise}
- -alg adaptnovelty+ -v params
* This variant has 2 parameters (phi,theta) that allow you to adjust the algorithm's adaptivity.
- -alg adaptnovelty+ -w
* {weighted+wcs}

= Conflict-Directed Random Walk
> [Papadimitriou91]
- -alg crwalk
* Also known as Papadimitriou's algorithm.
- -alg crwalk -v schoening
> [Schoening99]
* Also known as Schöning's Algorithm.
* Is Papadimitriou's algorithm with a restart every 3n steps.
- -alg crwalk -w
* {weighted+wcs}
- -alg crwalk -v schoening -w
* {weighted+wcs}

= DDFW: Divide and Distribute Fixed Weights
> [IshEtAl05]
- -alg ddfw
* The original implementation from the authors has a parameter (-tl) that was not mentioned in the original paper: with probability (1-tl) a random neighbour (in lieu of the neighbour with maximum penalty) is selected to distribute weight from.  The UBCSAT implementation includes this parameter with a default setting of (0.99).

= Deterministic Conflict-Directed Random Walk
> [TomHoo06]
- -alg dcrwalk
* {academic}

= Deterministic Adaptive Novelty+
> [TomHoo06]
- -alg danov+
* {academic}

= G2WSAT: Gradient-based Greedy WalkSAT
> [LiHua05]
- -alg g2wsat
* Uses Novelty++ as the WalkSAT algorithm.
* Selects the best decreasing promising variable available, as per the paper and original implementation.
* {novnoise}
* {maxflips}
* {preproc}
* {preproc1}
- -alg g2wsat -v novelty+oldest
* Uses Novelty+ as the WalkSAT algorithm.
* Selects the oldest (not necessarily the best) decreasing promising variable.
* This is the algorithm variant used by Adaptive G2WSAT+.
- -alg g2wsat -w
* {weighted+wcs}
- -alg g2wsat -v novelty+oldest -w

= G2WSAT+p: Gradient-based Greedy WalkSAT with look-ahead
> [LiWeiZha07]
* Uses Novelty+p as the WalkSAT algorithm.

= GSAT: Greedy Search for SAT
> [SelLevMit92]
- -alg gsat
* {maxflips}
- -alg gsat -v simple
* This is a simpler variant that behaves the same as GSAT, but is implemented in a more striaghtforward manner, and is typically slower.
- -alg gsat -w
* {weighted}

= GSAT/TABU: GSAT with Tabu search
> [MazSaiGre97]
- -alg gsat-tabu
* Also known as TSAT.
* {maxflips}
- -alg gsat-tabu -w
* {weighted}

= GWSAT: GSAT with Random Walk
> [SelKau93]
- -alg gwsat
* Also known as GSAT-WALK, RWS-GSAT, GRSAT, GSATRW.
* The algorithm noise parameter p as described in the paper is implemented in UBCSAT as (-wp).
* {maxflips}
- -alg gwsat -w
* {weighted}

= HSAT: GSAT with History Information
> [GenWal93]
- -alg hsat
* {maxflips}
- -alg hsat -w
* {weighted}

= HWSAT: HSAT with Random Walk
> [GenWal95]
- -alg hwsat
* {maxflips}
- -alg hwsat -w
* {weighted}

= IRoTS: Iterated Robust TABU Search
> [SmyHooStu03]
- -alg irots
- -alg irots -w
* {weighted}

= Novelty
> [McaSelKau97]
- -alg novelty
* {novnoise}
- -alg novelty -w
* {weighted+wcs}

= Novelty+: Novelty with Random Walk
> [Hoos99b]
- -alg novelty+
- -alg novelty+ -w
* {weighted+wcs}

= Novelty++: Novelty with Diversification Probability
> [LiHua05]
- -alg novelty++
* {novnoise}
* {maxflips}
- -alg novelty++ -w
* {weighted+wcs}

= Novelty+p: Novelty+ with look-ahead
> [LiWeiZha07]
* {novnoise}

= PAWS: Pure Additive Weighting Scheme
> [ThoEtAl04]
- -alg paws

= RoTS: Robust Tabu Search
> [Taillard91]
- -alg rots
* The UBCSAT implementation is based on the software implementation provided by Thomas Stützle.
- -alg rots -w
* {weighted}

= R-Novelty
> [McaSelKau97]
- -alg rnovelty
* {novnoise}

= R-Novelty+: R-Novelty with Random Walk
> [Hoos99b]
- -alg rnovelty+

= RGSAT: Restarting GSAT
> [TomHoo04]
- -alg rgsat
* {academic}
- -alg rgsat -w
* {weighted}

= RSAPS: Reactive SAPS
> [HutTomHoo02]
- -alg rsaps
* {saps}

= SAMD: Steepest Ascent Mildest Descent
> [HanJau90]
- -alg samd
* very similar to GSAT-TABU, except the age of flipped variables are not changed (and hence not tabu) if they were flipped in an improving search step.
- -alg samd -w
* {weighted}

= SAPS: Scaling and Probabilistic Smoothing
> [HutTomHoo02]
- -alg saps
* The paper describes the clause weight update procedure to be: w_i := w_i * rho + (1 - rho) * w_avg, but in practice the first term (w_i * rho) is a scalar change that can be ignored.  However, this also means that setting rho = 0 may not achieve the desired effect.
* As a result the former change in the clause updates, clause weights can grow to be arbitrarily large and so UBCSAT (as did the original SAPS implementation) performs a re-normalization: whenever a clause weight exceeds the value of 1000, all clause weights are divided by 1000.
* The UBCSAT implementation has an additional parameter of a threshold (-sapsthresh) that is used to determine how much an improvement is considered to be an improvement.  The default parameter of (-0.1) is consistent with the value used in the original SAPS implementation.  This threshold was not mentioned in the paper.
- -alg saps -v winit -w
* {weighted}
* Clause penalties are initialized to the clause weights.
- -alg saps -v wsmooth -w
* {weighted}
* Clause penalties are initialized to the clause weights and smoothed back to their initial values.

= SAPS/NR: De-randomized version of SAPS
> [TomHoo04]
- -alg sapsnr
* {saps}

= Uniform Random Walk
- -alg urwalk
- -alg urwalk -w
* {weighted}

= VW1: Variable Weighting Scheme One
> [Prestwich05]
* {wp}

= VW2: Variable Weighting Scheme Two
> [Prestwich05]
* {wp}
* Variable Weights are implemented in UBCSAT with (double) floating point precision.
* In author's original source code, it exits on the first freebie variable it discovers, whereas in UBCSAT it uniformly randomly selects amongst all freebies randomly (as described in the paper) -- This is a very minor discrepency.


= WalkSAT
> [SelKauCoh94]
- -alg walksat
* Also known as WSAT and WalkSAT/SKC
- -alg walksat -w
* {weighted+wcs}

= WalkSAT/TABU: WalkSAT with TABU search
> [McaSelKau97]
- -alg walksat-tabu
- -alg walksat-tabu -v nonull
* Modified to take a random walk in lieu of a null flip.
- -alg walksat-tabu -w
* {weighted+wcs}

{academic} This algorithm was developed for acadameic interest, and is not recommended for practical applications.
{adaptnoise} The UBCSAT implementation uses a higher precision to store the adaptive noise parameter, which may cause slight algorithmic variations on longer runs.
{g2wsat} See the G2WSAT entry for additional implementation details.
{maxflips} The MAX-TRIES and MAX-FLIPS parameters correspond to UBCSAT parameters (-srestart MAX-FLIPS -cutoff MAX-TRIES * MAX-FLIPS).  See the online UBCSAT FAQ for more details.
{novnoise} The algorithm noise parameter p as described in the paper is implemented in UBCSAT as (-novnoise).
{preproc} The original algorithm software implementation performed some pre-processing, whereas UBCSAT does not.  See the online UBCSAT FAQ for more details.
{preproc1} The pre-processing was: duplicate literal elimination, pure literal elimination, true clause elimination and unit propagation.
{saps} See the SAPS entry for additional implementation details.
{weighted} This is a weighted variant that incorporates clause weights into the heuristic (i.e.: for Weighted MAX-SAT).
{weighted+wcs} This is a weighted variant that incorporates clause weights into the heuristic (i.e.: for Weighted MAX-SAT) including a weighted clause selection scheme.
{wp} The algorithm noise parameter p as described in the paper is implemented in UBCSAT as (-wp).