2007 · 37 citations · 16 references
ComputingComputer ScienceAlgorithmsData StructuresSchedulingRandomized AlgorithmsRandomized ComputationRandomized Computation ModelsRestartTree Search
Abstract. In this paper, nogood recording is investigated for CSP within the randomization and restart framework. Our goal is to avoid the same situations to occur from one run to the next one. More precisely, nogoods are recorded when the current cutoff value is reached, i.e. before restarting the search algorithm. Such a set of nogoods is extracted from the last branch of the current search tree and managed using the structure of watched literals originally proposed for SAT. Interestingly, the number of nogoods recorded before each new run is bounded by the length of the last branch of the search tree. As a consequence, the total number of recorded nogoods is polynomial in the number of restarts. Experiments over a wide range of CSP instances demonstrate the effectiveness of this approach. 1
16
Matthew W. Moskewicz, Conor Madigan, Ying Zhao et al. · 2001 · 2.9K citations
New methods to color the vertices of a graph
Daniel Brélaz · Communications of the ACM · 1979 · 1.6K citations · Full text
Using CSP look-back techniques to solve real-world SAT instances
Roberto J. Bayardo, Robert Schrag · 1997 · 598 citations
HYBRID ALGORITHMS FOR THE CONSTRAINT SATISFACTION PROBLEM
Patrick Prosser · Computational Intelligence · 1993 · 519 citations