2nd International ICST Conference on Bio-Inspired Models of Network, Information, and Computing Systems

Research Article

A Global Convexity Analysis on the MAX-SAT Domain

Download50 downloads
  • @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
Marcos Villagra1,*, Benjamín Barán1,*
  • 1: Politechnical School National University of Asuncion P.O. Box 2169, San Lorenzo, Paraguay
*Contact email: mvillagra@pol.una.py, bbaran@pol.una.py

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.