NDLI: More efficient two-mode stochastic local search for random 3-satisfiability

Content Provider	Springer Nature Link
Author	Luo, Chuan Su, Kaile Cai, Shaowei
Copyright Year	2014
Abstract	Stochastic local search (SLS) is a popular paradigm in incomplete solving for the Boolean satisfiability problem (SAT). Most SLS solvers for SAT switch between two modes, i.e., the greedy (intensification) mode and the diversification mode. However, the performance of these two-mode SLS algorithms lags far behind on solving random 3-satisfiability (3-SAT) problem, which is a significant special case of the SAT problem. In this paper, we propose a new hybrid scoring function called M C based on a linear combination of a greedy property m a k e and a diversification property C o n f T i m e s, and then utilize M C to develop a new two-mode SLS solver called CCMC. To evaluate the performance of CCMC, we conduct extensive experiments to compare CCMC with five state-of-the-art two-mode SLS solvers (i.e., Sparrow2011, Sattime2011, EagleUP, gNovelty+PCL and CCASat) on a broad range of random 3-SAT instances, including all large 3-SAT ones from SAT Competition 2009 and SAT Competition 2011 as well as 200 generated satisfiable huge random 3-SAT ones. The experiments illustrate that CCMC obviously outperforms its competitors, indicating the effectiveness of CCMC. We also analyze the effectiveness of the underlying ideas in CCMC and further improve the performance of CCMC on solving random 5-SAT instances.
Starting Page	665
Ending Page	680
Page Count	16
File Format	PDF
ISSN	0924669X
Journal	Applied Intelligence
Volume Number	41
Issue Number	3
e-ISSN	15737497
Language	English
Publisher	Springer US
Publisher Date	2014-06-22
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Local search Satisfiability Linear combination Greedy Diversification Property Artificial Intelligence (incl. Robotics) Mechanical Engineering Manufacturing, Machines, Tools
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Conditional and composite temporal CSPs

Local Search Genetic Algorithms for the Job Shop Scheduling Problem

An efficient algorithm for solving nonograms

Efficient GA Based Techniques for Classification

An Efficient Gradient Forecasting Search Method Utilizing the Discrete Difference Equation Prediction Model

State Space Search with Prioritised Soft Constraints

Boosting MUC extraction in unsatisfiable constraint networks

Multi-document summarization via submodularity

Characteristic Rule Discovery in Aurum-3

More efficient two-mode stochastic local search for random 3-satisfiability

Similar Documents

Conditional and composite temporal CSPs

Local Search Genetic Algorithms for the Job Shop Scheduling Problem

An efficient algorithm for solving nonograms

Efficient GA Based Techniques for Classification

An Efficient Gradient Forecasting Search Method Utilizing the Discrete Difference Equation Prediction Model

State Space Search with Prioritised Soft Constraints

Boosting MUC extraction in unsatisfiable constraint networks

Multi-document summarization via submodularity

Characteristic Rule Discovery in Aurum-3

More efficient two-mode stochastic local search for random 3-satisfiability