ENHANCING LOCAL-SEARCH BASED SAT SOLVERS WITH LEARNING CAPABILITY

Ole-Christoffer Granmo, Noureddine Bouhmala

2010

Abstract

The Satisfiability (SAT) problem is a widely studied combinatorial optimization problem with numerous applications, including time tabling, frequency assignment, and register allocation. Among the simplest and most effective algorithms for solving SAT problems are stochastic local-search based algorithms that mix greedy hill-climbing (exploitation) with random non-greedy steps (exploration). This paper demonstrates how the greedy and random components of the well-known GSAT Random Walk (GSATRW) algorithm can be enhanced with Learning Automata (LA) based stochastic learning. The LA enhancements are designed so that the actions that the LA chose initially mimic the behavior of GSATRW. However, as the LA explicitly interact with the SAT problem at hand, they learn the effect of the actions that are chosen, which allows the LA to gradually and dynamically shift from random exploration to goal-directed exploitation. Randomized and structured problems from various domains, including SAT-encoded Logistics Problems, and Block World Planning Problems, demonstrate that our LA enhancements significantly improve the performance of GSATRW, thus laying the foundation for novel LA-based SAT solvers.

Paper Citation

in Harvard Style

Granmo O. and Bouhmala N. (2010). ENHANCING LOCAL-SEARCH BASED SAT SOLVERS WITH LEARNING CAPABILITY . In Proceedings of the 2nd International Conference on Agents and Artificial Intelligence - Volume 1: ICAART, ISBN 978-989-674-021-4, pages 515-521. DOI: 10.5220/0002707505150521

in Bibtex Style

@conference{icaart10,
author={Ole-Christoffer Granmo and Noureddine Bouhmala},
title={ENHANCING LOCAL-SEARCH BASED SAT SOLVERS WITH LEARNING CAPABILITY},
booktitle={Proceedings of the 2nd International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,},
year={2010},
pages={515-521},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002707505150521},
isbn={978-989-674-021-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 2nd International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,
TI - ENHANCING LOCAL-SEARCH BASED SAT SOLVERS WITH LEARNING CAPABILITY
SN - 978-989-674-021-4
AU - Granmo O.
AU - Bouhmala N.
PY - 2010
SP - 515
EP - 521
DO - 10.5220/0002707505150521