Local Search on SAT-encoded Colouring Problems
作者： Steven Prestwich
DOI: 10.1007/978-3-540-24605-3_9
关键词: Algorithm 、 Search algorithm 、 Local search (optimization) 、 Constraint satisfaction 、 Constraint satisfaction problem 、 Search problem 、 Computer science 、 Boolean satisfiability problem 、 Propositional calculus
摘要: Constraint satisfaction problems can be SAT-encoded in more than one way, and the choice of encoding as important search algorithm. Theoretical results are few but experimental comparisons have been made between encodings, using both local backtrack algorithms. This paper compares performance on seven encodings graph colouring benchmarks. Two new them gives generally better known encodings. We also find expected for two variants log encoding, surprisingly poor support encoding.
springer.com
sci-hub.st 参考文章(124)
Andrew B. Philips, Steven Minton, Philip Laird, Mark D. Johnston, Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method national conference on artificial intelligence. pp. 17- 24 ,(1990)
Chu Min Li, Anbulagan Anbulagan, Heuristics based on unit propagation for satisfiability problems international joint conference on artificial intelligence. pp. 366- 371 ,(1997)
Thomas L. Dean, Michael P. Wellman, Planning and Control ,(1991)
Wolfgang Kunz, Dominik Stoffel, Reasoning in Boolean Networks Springer US. ,(1997) , 10.1007/978-1-4757-2572-8
Avi Wigderson, Russell Impagliazzo, Eli Ben-Sasson, Near-Optimal Separation of Treelike and General Resolution Electronic Colloquium on Computational Complexity. ,vol. 7, ,(2000)
Philippe Jégou, Richard Génisson, Davis and Putnam were Already Checking Forward. european conference on artificial intelligence. pp. 180- 184 ,(1996)
John L. Bresina, William R. Edgington, Robert A. Morris, Optimizing Observation Scheduling Objectives ,(1997)
Thomas Schiex, Gérard Verfaillie, Michel Lemaître, Russian doll search for solving constraint optimization problems national conference on artificial intelligence. pp. 181- 187 ,(1996)
Holger H. Hoos, SAT-encodings, search space structure, and local search performance international joint conference on artificial intelligence. pp. 296- 302 ,(1999)
Bart Selman, Henry Kautz, Domain-independent extensions to GSAT: solving large structured satisfiability problems international joint conference on artificial intelligence. pp. 290- 295 ,(1993)