Old resolution meets modern SLS

Anbulagan*, Due Nghia Pham, John Slaney, Abdul Sattar

*Corresponding author for this work

    Research output: Contribution to conferencePaperpeer-review

    28 Citations (Scopus)

    Abstract

    Recent work on Stochastic Local Search (SLS) for the SAT and CSP domains has shown the importance of a dynamic (non-markovian) strategy for weighting clauses in order to escape from local minima. In this paper, we improve the performance of two best contemprorary clause weighting solvers, PAWS and SAPS, by integrating a prepositional resolution procedure. We also extend the work to AdaptNovelty+, the best non-weighting SLS solver in the GSAT/WalkSAT series. One outcome is that our systems can solve some highly structured problems such as quasigroup existence and parity learning problems which were previously thought unsuitable for local search and which are completely out of reach of traditional solvers such as GSAT. Here we present empirical results showing that for a range of random and real-world benchmark problems, resolution-enhanced SLS solvers clearly outperform the alternatives.

    Original languageEnglish
    Pages354-359
    Number of pages6
    Publication statusPublished - 2005
    Event20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference, AAAI-05/IAAI-05 - Pittsburgh, PA, United States
    Duration: 9 Jul 200513 Jul 2005

    Conference

    Conference20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference, AAAI-05/IAAI-05
    Country/TerritoryUnited States
    CityPittsburgh, PA
    Period9/07/0513/07/05

    Fingerprint

    Dive into the research topics of 'Old resolution meets modern SLS'. Together they form a unique fingerprint.

    Cite this