Division of Informatics
Forrest Hill & 80 South Bridge
Research Paper #721 | |
|---|---|
| Title: | Unsatisfied Variables in Local Search |
| Authors: | Gent,I; Walsh,T |
| Date: | Dec 1994 |
| Presented: | Slightly expanded version of paper submitted to AISB-95 |
| Keywords: | |
| Abstract: | Several local search algorithms for propositional satisfiability have recently been proposed which are able to solve hard random problems beyond the range of conventional backtracking procedures. in this paper, we explore the impact of focusing search in these procedures on the "unsatisfied variables"; that is, those variables will appear in clauses which are not yet satisfied. For random problems, we show that such a focus reduces the sensitivity of these procedures to their input parameters. We also observe a simple scaling law in performance. for non-random problems, we show that whilst this focus can improve performance, many problems remain difficult. We speculate that such problems will remain hard for local search unless constraint propagation techniques can be combined with hill-climbing. |
| Download: | NO ONLINE COPY |
![[Search These Pages]](http://www.dai.ed.ac.uk/icons/dai_search.gif){kind=icon}
![[DAI Home Page]](http://www.dai.ed.ac.uk/icons/dai_home.gif){kind=icon}
![[Comment]](http://www.dai.ed.ac.uk/icons/dai_comment.gif){kind=icon}