Diversify intensification phases in local search for SAT with a new probability distribution

Thach Thao Duong, Duc Nghia Pham, Abdul Sattar

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


A key challenge in developing efficient local search solvers is to intelligently balance diversification and intensification. This study proposes a heuristic that integrates a new dynamic scoring function and two different diversification criteria: variable weights and stagnation weights. Our new dynamic scoring function is formulated to enhance the diversification capability in intensification phases using a user-defined diversification parameter. The formulation of the new scoring function is based on a probability distribution to adjust the selecting priorities of the selection between greediness on scores and diversification on variable properties. The probability distribution of variables on greediness is constructed to guarantee the synchronization between the probability distribution functions and score values. Additionally, the new dynamic scoring function is integrated with the two diversification criteria. The experiments show that the new heuristic is efficient on verification benchmark, crafted and random instances.

Original languageEnglish
Title of host publicationAI 2013
Subtitle of host publication26th Australasian Joint Conference Dunedin, New Zealand, December 1-6, 2013 Proceedings
EditorsStephen Cranefield, Abhaya Nayak
Place of PublicationCham, Switzerland
Number of pages12
ISBN (Electronic)9783319036809
Publication statusPublished - 2013
Externally publishedYes
Event26th Australasian Joint Conference on Artificial Intelligence, AI 2013 - Dunedin, Netherlands
Duration: 1 Dec 20136 Dec 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8272 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference26th Australasian Joint Conference on Artificial Intelligence, AI 2013


Dive into the research topics of 'Diversify intensification phases in local search for SAT with a new probability distribution'. Together they form a unique fingerprint.

Cite this