Abstract
This paper has two related themes. Firstly, artificial SAT problems are used to show that certain chains of variable dependency have a harmful effect on local search, sometimes causing exponential scaling on intrinsically easy problems. Secondly, systematic, local and hybrid SAT algorithms are evaluated on Hamiltonian cycle problems, exposing weaknesses in all three. The connection between the two themes is that some Hamiltonian cycle problems also cause local search to scale badly, indicating that pathological variable dependencies occur in more realistic applications. More generally, the results highlight the need for alternative models and search algorithms, and new examples of both are described.
| Original language | English |
|---|---|
| Pages (from-to) | 329-350 |
| Number of pages | 22 |
| Journal | Discrete Applied Mathematics |
| Volume | 130 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 15 Aug 2003 |
| Event | CMMSE 2002 - Alicante, Spain Duration: 20 Sept 2002 → 25 Sept 2002 |
UCC Futures
- Artificial Intelligence and Data Analytics
Keywords
- Hamiltonian path
- Satisfiability
- Search
- Variable dependencies
Fingerprint
Dive into the research topics of 'SAT problems with chains of dependent variables'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver