Trap escape for local search by backtracking and conflict reverse

Huu Phuoc Duong, Thach Thao Duong, Duc Nghia Pham, Abdul Sattar, Anh Duc Duong

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


This paper presents an efficient trap escape strategy in stochastic local search for Satisfiability. The proposed method aims to enhance local search by providing an alternative local minima escaping strategy. Our variable selection scheme provides a novel local minima escaping mechanism to explore new solution areas. Conflict variables are hypothesized as variables recently selected near local minima. Hence, a list of backtracked conflict variables is retrieved from local minima. The new strategy selects variables in the backtracked variable list based on the clause-weight scoring function and stagnation weights and variable weights as tiebreak criteria. This method is an alternative to the conventional method of selecting variables in a randomized unsatisfied clause. The proposed tiebreak method favors high stagnation weights and low variable weights during trap escape phases. The new strategies are examined on verification benchmark and SAT Competition 2011 and 2012 application and crafted instances. Our experiments show that proposed strategy has comparable performance with state-of-the-art local search solvers for SAT.

Original languageEnglish
Title of host publicationTwelfth Scandinavian Conference on Artificial Intelligence. SCAI 2013
EditorsManfred Jaeger, Thomas Dyhre Nielsen, Paolo Viappiani
Place of PublicationAmsterdam
PublisherIOS PRESS
Number of pages10
ISBN (Electronic)9781614993308
ISBN (Print)9781614993292
Publication statusPublished - 2013
Externally publishedYes

Publication series

NameFrontiers in Artificial Intelligence and Applications
ISSN (Print)0922-6389


  • local search
  • SAT
  • Stagnation
  • Trap escape


Dive into the research topics of 'Trap escape for local search by backtracking and conflict reverse'. Together they form a unique fingerprint.

Cite this