Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/85854029-9F0F-4C83-9CBA-F91FC42A21D0 | ||
| Year | 2001 | ||
| Type of Item | Conference Full Paper | ||
| License |
|
||
| Bibliographic Citation | M. G. Lagoudakis and M. L. Littman. (2001, June). Learning to select branching rules in the DPLL procedure for satisfiability. [Online]. Available: https://www.cs.ubc.ca/~hutter/EARG.shtml/earg/papers07/lagoudakis01learning.pdf | ||
| Appears in Collections |
The DPLL procedure is the most popular completesatisfiability (SAT) solver. While its worstcase complexity is exponential, the actual runningtime is greatly affected by the orderingof branch variables during the search. Severalbranching rules have been proposed, but noneis the best in all cases. This work investigatesthe use of automated methods for choosing themost appropriate branching rule at each node inthe search tree. We consider a reinforcementlearningapproach where a value function, whichpredicts the performance of each branching rulein each case, is learned through trial runs on atypical problem set of the target class of SATproblems. Our results indicate that, providedsufficient training on a given class, the resultingstrategy performs as well as (and, in some cases,better than) the best branching rule for that class.
Copyright © DIAS 2013
