Research Article
A Global Convexity Analysis on the MAX-SAT Domain
@INPROCEEDINGS{10.4108/ICST.BIONETICS2007.2424, author={Marcos Villagra and Benjam\^{\i}n Bar\^{a}n}, title={A Global Convexity Analysis on the MAX-SAT Domain}, proceedings={2nd International ICST Conference on Bio-Inspired Models of Network, Information, and Computing Systems}, proceedings_a={BIONETICS}, year={2008}, month={8}, keywords={Global Convexity Local Search Metaheuristics SAT}, doi={10.4108/ICST.BIONETICS2007.2424} }- Marcos Villagra
Benjamín Barán
Year: 2008
A Global Convexity Analysis on the MAX-SAT Domain
BIONETICS
ICST
DOI: 10.4108/ICST.BIONETICS2007.2424
Abstract
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 MAXSAT. 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 metaheuristic would be able to defeat an efficient local search algorithm, as experimentally proven in this work.
