About | Contact Us | Register | Login
ProceedingsSeriesJournalsSearchEAI
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

Download896 downloads
Cite
BibTeX Plain Text
  • @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.

Keywords
Global Convexity Local Search Metaheuristics SAT
Published
2008-08-29
Modified
2011-07-10
http://dx.doi.org/10.4108/ICST.BIONETICS2007.2424
Copyright © 2007–2025 ICST
EBSCOProQuestDBLPDOAJPortico
EAI Logo

About EAI

  • Who We Are
  • Leadership
  • Research Areas
  • Partners
  • Media Center

Community

  • Membership
  • Conference
  • Recognition
  • Sponsor Us

Publish with EAI

  • Publishing
  • Journals
  • Proceedings
  • Books
  • EUDL