Comparing Extremal and Hysteretic Optimization on the Satisfiability Problem

We apply physically inspired optimization methods to the classical combinatorial Satisfiablity problem. Treating the usual boolean variables as Ising spins and each clause as a p-spin interaction we can use the pre-existing physical intuition about spin glasses and magnetic systems to find the optimal solution for this problem (the ground state energy). We compare the performance of Extremal Optimization\footnote{PRL 23:5211, 2001} ($\tau EO$) and Hysteretic Optimization\footnote{PRL 89:150201, 2002} ($HO$) and determine the parameter values that provide the best results. Comparisons with previously published results on well known benchmarks\footnote{DIMACS 35:393, 1997} are also made.