Combining simulated annealing with local search heuristic for MAX-SAT

摘要

The simplicity of the maximum satisfiability problem combined with its wide applicability in various 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 in a Boolean Formula. The present consensus is that the best heuristic that leads to the best solutions for the partitioning of generic (random) graphs is a variable depth search due to Kernighan and Lin algorithm hereafter referred to as KL. It suggests an intriguing idea which is based on replacing the search of one favorable move by a search for a favorable sequence of moves. In this paper, an adapted version of KL for the maximum satisfiability problem is introduced and embedded into the simulated annealing algorithm. Tests on benchmark instances and comparison with state-of-the-art solvers quantify the power of the method.