A Variable Neighborhood Walksat-Based Algorithm for MAX-SAT Problems

Abstract EN

The simplicity of the maximum satisfiability problem (MAX-SAT) combined with itsapplicability in many areas of artificial intelligence and computing science made it one ofthe fundamental optimization problems.

This NP-complete problem refers to the task offinding a variable assignment that satisfies the maximum number of clauses (or the sumof weights of satisfied clauses) in a Boolean formula.

The Walksat algorithm is consideredto be the main skeleton underlying almost all local search algorithms for MAX-SAT.

Mostlocal search algorithms including Walksat rely on the 1-flip neighborhood structure.

Thispaper introduces a variable neighborhood walksat-based algorithm.

The neighborhoodstructure can be combined easily using any local search algorithm.

Its effectiveness iscompared with existing algorithms using 1-flip neighborhood structure and solverssuch as CCLS and Optimax from the eighth MAX-SAT evaluation.