2004 · 399 citations · 15 references
ComputingComputer ScienceAlgorithmsKnowledge RepresentationOptimizationConstraint ProgrammingConstraint SatisfactionConstraint SolvingHeuristic SearchMetaheuristic OptimizationSearching AlgorithmsConstraint Conflict ResolutionConstraint Satisfaction SearchCsp Search AlgorithmsDynamic Constraint SatisfactionDynamic Variable OrderingOverconstrained ProblemsVariable Ordering Heuristics
In this paper, we present a dynamic and adaptive variable ordering heuristic which guides systematic search toward inconsistent or hard parts of a Constraint Satisfaction Problem (CSP). This generic heuristic is able to exploit information about previous states of the search process whereas traditional dynamic ones only exploit information about the current state. Intuitively, it avoids some trashing by first instantiating variables involved in the constraints that have frequently participated in dead-end situations. Such information is recorded by associating a weight with each constraint. This weight is increased whenever the associated constraint is violated during search. The extensive experiments that we have conducted prove that our conflict-directed approach is the most efficient current one with respect to significant and large classes of academic, random and real-world instances.
15
New methods to color the vertices of a graph
Daniel Brélaz · Communications of the ACM · 1979 · 1.6K citations · Full text
A Sufficient Condition for Backtrack-Free Search
Eugene C. Freuder · Journal of the ACM · 1982 · 656 citations · Full text