Asynchronous Team Algorithms for Boolean Satisfiability

Carlos Rodríguez; Marcos Villagra; Benjamín Barán

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

Research Article

Asynchronous Team Algorithms for Boolean Satisfiability

Download686 downloads

Cite: BibTeX Plain Text

@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íguez¹^,*, Marcos Villagra²^,*, Benjamín Barán³^,*

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.

Keywords: Asynchronous Team Local Search MAX-SAT SAT Team Algorithms

Published: 2008-08-29
Modified: 2011-07-10

: http://dx.doi.org/10.4108/ICST.BIONETICS2007.2425

Asynchronous Team Algorithms for Boolean Satisfiability

Abstract

About EAI

Community

Publish with EAI