Tuesday 28
Local search and decomposition
M. Basseur
› 9:40 - 10:00 (20min)
A Multilevel WalkSAT For The Maximum Satisfiability Problem
Noureddine Bouhmala  1@  
1 : Vestfold and Buskerud College  (HBV)

This paper introduces a multilevel Walksat algorithm for the Maximum Satisfiability Problem
 The approach suggests looking at the solution of the problem as a multilevel process operating in a coarse-to-fine strategy. This strategy involves recursive coarsening to create a hierarchy of increasingly smaller and coarser versions of the original problem. The reduction phase works by grouping the variables representing the problem into clusters. This phase is repeated until the size of the smallest problem falls below a specified reduction threshold. A solution for the problem at the coarsest level is generated, and then successively projected back onto each of the intermediate levels in reverse order. The solution at each child level is improved before moving to the parent level. Benchmark including various category of test cases are used to compare the effectiveness of the approach against state of arts algorithms.

Online user: 1 RSS Feed