An Analysis of Delayed Improvement Local Search Applied to the Max-SAT Problem

The Maximum Satisfiability Problem (Max-SAT) is widely addressed by local search methods based on 1-Flip moves. However, traditional pivoting strategies, such as Best Improvement Local Search (BILS) and First Improvement Local Search (FILS), tend to converge rapidly to low-quality local optima. In this work, we investigate the application of the Delayed Improvement Local Search (DILS) to Max-SAT, which employs local optimality preconditions to prioritize improving solutions potentially less associated with premature convergence. On 30 SAT and UNSAT instances from SATLIB, DILS achieved competitive and, in several cases, better solutions than traditional strategies, especially in UNSAT scenarios, although at the cost of higher computational effort per iteration.