Reactive Tabu Search for MAX-SAT, an Analysis of Sampling Strategies

We revisit a reactive algorithm for MAX-SAT that was proposed almost 30 years ago [12]. In the meantime, a large number of heuristics have been developed, in some cases with many free parameters to be carefully chosen. Some of the winners of the recent MAX-SAT competitions combined a variety of different principles (building blocks) to beat the other candidates in a “horse-race” spirit. We modify the original Hamming-Reactive-TS by replacing the “best improvement” strategy in local (perturbative) search with one based on “first improvement” or on a sample of bit changes to evaluate. After studying the diversification-bias effect of the new choices we show an impressive acceleration. The measure of effort considered in the experiments is primarily the number of function evaluations (of tentative bit-flips tried before the Local Search heuristic applies a move) because it is related to the amount of information obtained on the function to be optimized, it is independent of the particular language and compiler, and roughly proportional to the CPU time. The experiments are run on a selection of many randomized instances intended to simulate hard problems (MAX-3SAT instances close to the boundary between solvable and unsolvable problems) and problems with different degrees of internal structure. A preliminary evaluation considering a current state-of-the-art algorithm concludes the work.