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

Research Article

Asynchronous Team Algorithms for Boolean Satisfiability

Download71 downloads
  • @INPROCEEDINGS{10.4108/ICST.BIONETICS2007.2425,
        author={Carlos Rodr\^{\i}guez and Marcos Villagra and Benjam\^{\i}n Bar\^{a}n},
        title={Asynchronous Team Algorithms for Boolean Satisfiability},
        proceedings={2nd International ICST Conference on Bio-Inspired Models of Network, Information, and Computing Systems},
        proceedings_a={BIONETICS},
        year={2008},
        month={8},
        keywords={Asynchronous Team  Local Search  MAX-SAT  SAT  Team Algorithms},
        doi={10.4108/ICST.BIONETICS2007.2425}
    }
    
  • Carlos Rodríguez
    Marcos Villagra
    Benjamín Barán
    Year: 2008
    Asynchronous Team Algorithms for Boolean Satisfiability
    BIONETICS
    ICST
    DOI: 10.4108/ICST.BIONETICS2007.2425
Carlos Rodríguez1,*, Marcos Villagra2,*, Benjamín Barán3,*
  • 1: Politechnical School National University of Asuncion San Lorenzo, P.O. Box 2169 Paraguay Tel: +595-(21)-585-599
  • 2: Science and Technology School-DEI Catholic University of Asuncion Asuncion, P.O. Box 1683, Paraguay Tel: +595-(21)-334-650
  • 3: Politechnical School National University of Asuncion San Lorenzo, P. O. Box 2169, Paraguay Tel: +595-(21)-585-599
*Contact email: crodriguez@cnc.una.py, marcos_villagra@uca.edu.py, bbaran@pol.una.py

Abstract

The Boolean Satisfiability Problem or SAT is one of the most important problems in computer science. Nowadays, there are different types of algorithms to solve instances with thousands of variables, and much research is being carried out looking for more efficient algorithms to solve larger and harder instances. This work proposes the utilization of a Team Algorithm (TA) strategy combining different local search algorithms for SAT as WalkSAT, R-Novelty+, Adaptive Novelty+, RSAPS, IROTS and SAMD. TAs allow the combination of different algorithms that interact with each other searching for a good global solution. Experimental results show that the proposed TA is a general strategy capable of obtaining promising results for a variety of instances.