SAT 2004 START ConferenceManager    


UBCSAT: An Implementation and Experimentation Environment for SLS Algorithms for SAT and MAX-SAT

Dave A. D. Tompkins and Holger H. Hoos

Presented at The Seventh International Conference on Theory and Applications of Satisfiability Testing (SAT 2004), Vancouver, BC, Canada, 10-13 May 2004


Abstract

In this paper we describe the new UBCSAT software framework. Primarily, UBCSAT is an advanced tool for empirically evaluating Stochastic Local Search (SLS) algorithms on SAT and MAX-SAT instances. We describe some of the features available in UBCSAT for performing empirical analyses of SLS behaviour. Secondly, UBCSAT is a framework for developing and evaluating new SLS algorithms. We outline some of the resources available for developing new SLS algorithms and variants. And finally, UBCSAT includes fast implementations of many existing SLS algorithms, including various GSAT and WalkSAT variants, as well as the more recent Scaling and Probabilistic Smoothing (SAPS) algorithm. We demonstrate that the UBCSAT implementations of these algorithms behave identically to the original implementations, with improved speed performance. UBCSAT is publically and freely available; it is implemented in C and runs on numerous platforms and operating systems and can be easily modified and extended to fit specific needs.


  
START Conference Manager (V2.47.2)
Maintainer: rrgerber@softconf.com