A global convexity analysis on the MAX-SAT domain

To this day, there is little theoretical understanding on the mechanics of local search algorithms and metaheuristics. Therefore, this work studies the solution space of random MAX-SAT, which is a SAT variant. This analysis is focused on the study of global convexity, which may be exploited by some metaheuristics, as already observed in the literature. Understanding the structure of the solution space will give more insight on metaheuristics effectiveness for MAX-SAT. This paper presents experimental results suggesting that random MAX-SAT is not globally convex, except for some overconstrained instances. Consequently, for the latter case, it is possible to predict that a population-based meta-heuristic would be able to defeat an efficient local search algorithm, as experimentally proven in this work.