A Variable Neighborhood Walksat-Based Algorithm for MAX-SAT Problems
The simplicity of the maximum satisfiability problem (MAX-SAT) combined with its applicability in many areas of artificial intelligence and computing science made it one of the fundamental optimization problems. This NP-complete problem refers to the task of finding a variable assignment that satisf...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2014/798323 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832551810393440256 |
|---|---|
| author | Noureddine Bouhmala |
| author_facet | Noureddine Bouhmala |
| author_sort | Noureddine Bouhmala |
| collection | DOAJ |
| description | The simplicity of the maximum satisfiability problem (MAX-SAT) combined with its
applicability in many areas of artificial intelligence and computing science made it one of
the fundamental optimization problems. This NP-complete problem refers to the task of
finding a variable assignment that satisfies the maximum number of clauses (or the sum
of weights of satisfied clauses) in a Boolean formula. The Walksat algorithm is considered
to be the main skeleton underlying almost all local search algorithms for MAX-SAT. Most
local search algorithms including Walksat rely on the 1-flip neighborhood structure. This
paper introduces a variable neighborhood walksat-based algorithm. The neighborhood
structure can be combined easily using any local search algorithm. Its effectiveness is
compared with existing algorithms using 1-flip neighborhood structure and solvers
such as CCLS and Optimax from the eighth MAX-SAT evaluation. |
| format | Article |
| id | doaj-art-6898487b25184ed6a66089a4ea49738e |
| institution | Kabale University |
| issn | 2356-6140 1537-744X |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-6898487b25184ed6a66089a4ea49738e2025-02-03T06:00:28ZengWileyThe Scientific World Journal2356-61401537-744X2014-01-01201410.1155/2014/798323798323A Variable Neighborhood Walksat-Based Algorithm for MAX-SAT ProblemsNoureddine Bouhmala0Department of Maritime Technology and Innovation, Buskerud and Vestfold University, NorwayThe simplicity of the maximum satisfiability problem (MAX-SAT) combined with its applicability in many areas of artificial intelligence and computing science made it one of the fundamental optimization problems. This NP-complete problem refers to the task of finding a variable assignment that satisfies the maximum number of clauses (or the sum of weights of satisfied clauses) in a Boolean formula. The Walksat algorithm is considered to be the main skeleton underlying almost all local search algorithms for MAX-SAT. Most local search algorithms including Walksat rely on the 1-flip neighborhood structure. This paper introduces a variable neighborhood walksat-based algorithm. The neighborhood structure can be combined easily using any local search algorithm. Its effectiveness is compared with existing algorithms using 1-flip neighborhood structure and solvers such as CCLS and Optimax from the eighth MAX-SAT evaluation.http://dx.doi.org/10.1155/2014/798323 |
| spellingShingle | Noureddine Bouhmala A Variable Neighborhood Walksat-Based Algorithm for MAX-SAT Problems The Scientific World Journal |
| title | A Variable Neighborhood Walksat-Based Algorithm for MAX-SAT Problems |
| title_full | A Variable Neighborhood Walksat-Based Algorithm for MAX-SAT Problems |
| title_fullStr | A Variable Neighborhood Walksat-Based Algorithm for MAX-SAT Problems |
| title_full_unstemmed | A Variable Neighborhood Walksat-Based Algorithm for MAX-SAT Problems |
| title_short | A Variable Neighborhood Walksat-Based Algorithm for MAX-SAT Problems |
| title_sort | variable neighborhood walksat based algorithm for max sat problems |
| url | http://dx.doi.org/10.1155/2014/798323 |
| work_keys_str_mv | AT noureddinebouhmala avariableneighborhoodwalksatbasedalgorithmformaxsatproblems AT noureddinebouhmala variableneighborhoodwalksatbasedalgorithmformaxsatproblems |