Proceedings

SAT-Encodings, Search Space Structure, and Local Search Performance

Download BibTeX Cite

Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Challenge Papers. Pages 296-302.

© 1999 International Joint Conferences on Artificial Intelligence

Abstract

Stochastic local search (SLS) algorithms for propositional satisfiability testing (SAT) have become popular and powerful tools for solving suitably encoded hard combinatorial from different domains like, e.g., planning. Consequently, there is a considerable interest in finding SAT-encodings which facilitate the efficient application of SLS algorithms. In this work, we study how two encodings schemes for combinatorial problems, like the well-known Constraint Satisfaction or Hamilton Circuit Problem, affect SLS performance on the SAT-encoded instances. To explain the observed performance differences, we identify features of the induces search spaces which affect SLS performance. We furthermore present initial results of a comparitive analysis of the performance of the SAT-encoding and -solving approach versus that of native SLS algorithms directly applied to the unencoded problem instances.

  1. [Cheeseman et al., 1991] P. Cheeseman, B. Kanefsky, and W. Taylor. Where the Really Hard Problems Are. In Proc. /JCA/ '91, pages 331-337, 1991. IJCAI
  2. [Clark et al., 1996] D. Clark, J. Frank, I. Gent, E. Macintyre, N. Tomov, and T. Walsh. Local Search and the Number of Solutions. In Proc. CP'96, LNCS, vol. 1118, pages 119- 133. Springer Verlag, 1996.
  3. [Dubois et al., 1993] Dubois, P. Andre, Y. Boufkhad, and J. Carlier. SAT versus UNSAT. In 2nd DIMACS Imple- mentation Challenge, 1993.
  4. [de Kleer, 1989] J. de Kleer. A Comparison of ATMS and CSP Techniques. In Proc. IJCA/'89. Morgan Kaufmann, 1989. IJCAI
  5. [Ernst et al., 1997] M. Ernst, T. Millstein, and D. Weld. Au- tomatic SAT-Compilation of Planning Problems. In Proc. /JCAI-97, 1997. IJCAI
  6. [Frank and Martel, 1995] J. Frank C. Martel. Phase Tran- sitions in the Properties of Random Graphs. In CP'95 Workshop on Studying and Solving Really Hard Problems, 1995.
  7. [Frank et al., 1997] J. Frank, P. Cheeseman, and J. Stutz. When Gravity Fails: Local Search Topology. lAIR, 7:249- 281 , 1997.
  8. [Galinier and Hao, 1997] P. Galinier and J. Hao. Tabu Search For Maximal Constraint Satisfaction Problems. In Proc. CP'97, LNCS, vol. 1330, pages 196--208. Springer Verlag, 1997.
  9. [Gu, 1992] J. Gu. Efficient Local Search for Very Large- scale Satisfiability Problems. ACM SIGART Bulletin, 3(1):8-12, 1992.
  10. [Hoos, 1998] Hoos, H. H. 1998. Stochastic Local Search- Methods, Models, Applications. Ph.D. Dissertation, Fach- bereich Informatik, Technische Universitiit Darmstadt.
  11. [Hoos and Sttitzle, 1998] H. H. Hoos and T. Sttitzle. Eval- uating Las Vegas algorithms -pitfalls and remedies. In Proc. UA/'98, 1998.
  12. [Iwama and Miyazaki, 1994] K. Iwama and S. Miyazaki. SAT-Variable Complexity of Hard Combinatorial Prob- lems. In Proc. IFIP World Computer Congress, pages 253-258. Elsevier Science B.V., North Holland, 1994. 302 CHALLENGE PAPERS [Kautz and Selman, 1996]
  13. H. Kautz and B. Selman. Pushing the Envelope: Planning, Propositional Logic, and Stochas- tic Search. In Proc. AAA/'96, volume 2, pages 1194-120 I, 1996.
  14. [Kautz and Selman, 1998] H. Kautz and B. Selman. The role of Domain-specific Knowledge in the Planning as Satisfi- ability Framework. In . Proc. AIPS-98, 1998.
  15. [McAllester et al., 1997] D. McAllester, B. Selman, and H. Kautz. Evidence for Invariants in Local Search. In Proc. AAA/'97, pages 321-326, 1997.
  16. [Minton et al., 1992] S. Minton, M.D. Johnston, A.B. Philips, and P. Laird. Minimizing Conflicts: A Heuri stic Repair Method for Constraint Satisfaction and Scheduling Problems. Artificial Intelligence, 52:161-205, 1992.
  17. [Prosser, 1996] P. Prosser. An Empirical Study of Phase Transitions in Binary Constraint Satisfaction Problems. Artificial Intelligence, 81:81-109, 1996.
  18. [Selman et al., 1992] B. Selman, H. Levesque, and D. Mitchell. A New Method for Solving Hard Satisfiability Problems. In Proc. AAA/'92, pages 440-446, 1992.
  19. [Selman et al., 1997] B. Selman, H. Kautz, and D. McAllester. Ten Challenges in Propositional Reasoning and Search. In Proc. /JCAI-97, 1997. IJCAI
  20. [Smith and Dyer, 1996] B. Smith and M . Dyer. Locating the Phase Transition in Binary Constraint Satisfaction Prob- lems. Artificial Intelligence, 81 :155-181, 1996.
  21. [Steinmann et al., 1997] Steinmann, A. Strohmaier, and T. Sttitzle. Tabu Search vs. Random Walk. In Advances in Artificial Intelligence (KI-97), LNAI, vol. 1303, pages 337-348. Springer Verlag, 1997.
  22. [Yokoo, 1997] M. Yokoo. Why Adding More Constraints Makes a Problem Easier for Hill-Climbing Algorithms: Analyzing Landscapes of CSPs. In Proc. CP'97, LNCS, vol. 1330, pages 357-370. Springer Verlag, 1997.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards