Randomized Rules of Thumb

Many practical problems can be formulated as constraint satisfaction problems (CSPs), where the goal is to assign values to a set of variables subject to constraints between variables. Traditional CSP solution methods typically involve constructing a solution by assigning values one variable at a time, and then backtracking (i.e. replacing the values of some already assigned variable) when no consistent assignment can be found for the next variable. Recently, it has been discovered that simple randomized local repair techniques that work by repairing total assignments can solve instances of some well-known CSPs orders of magnitude larger than solvable by any other method. These localrepair algorithms are simple, fast, and effective, and so have spurred much recent research. This paper discusses one such technique, called the minconflicts heuristic. Along with a pair of algorithms applicable to general CSPs, new examples of problems solvable by the min-conflicts heuristic are given. I..