Vidal's library
Title: Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems
Author: Steven Minton, Mark D. Johnston, Andrew B. Philips, and Philip Laird
Journal: Artificial Intelligence
Volume: 58
Pages: 161--205
Year: 1992
DOI: 10.1016/0004-3702(92)90007-K
Abstract: The paper describes a simple heuristic approach to solving large-scale constraint satisfaction and scheduling problems. In this approach one starts with an inconsistent assignment for a set of variables and searches through the space of possible repairs. The search can be guided by a value-ordering heuristic, the min-conflicts heuristic, that attempts to minimize the number of constraint violations after each step. The heuristic can be used with a variety of different search strategies. We demonstrate empirically that on the n-queens problem, a technique based on this approach performs orders of magnitude better than traditional backtracking techniques. We also describe a scheduling application where the approach has been used successfully. A theoretical analysis is presented both to explain why this method works well on certain types of problems and to predict when it is likely to be most effective.

Cited by 474  -  Google Scholar

@Article{minton92a,
  author =	 {Steven Minton and Mark D. Johnston and Andrew
                  B. Philips and Philip Laird},
  title =	 {Minimizing conflicts: a heuristic repair method for
                  constraint satisfaction and scheduling problems},
  journal =	 {Artificial Intelligence},
  year =	 1992,
  volume =	 58,
  pages =	 {161--205},
  abstract =	 {The paper describes a simple heuristic approach to
                  solving large-scale constraint satisfaction and
                  scheduling problems. In this approach one starts
                  with an inconsistent assignment for a set of
                  variables and searches through the space of possible
                  repairs. The search can be guided by a
                  value-ordering heuristic, the min-conflicts
                  heuristic, that attempts to minimize the number of
                  constraint violations after each step. The heuristic
                  can be used with a variety of different search
                  strategies. We demonstrate empirically that on the
                  n-queens problem, a technique based on this approach
                  performs orders of magnitude better than traditional
                  backtracking techniques. We also describe a
                  scheduling application where the approach has been
                  used successfully. A theoretical analysis is
                  presented both to explain why this method works well
                  on certain types of problems and to predict when it
                  is likely to be most effective.},
  keywords = 	 {multiagent dcsp distributed-search},
  doi = 	 {10.1016/0004-3702(92)90007-K},
  googleid = 	 {9ify1KjclpIJ:scholar.google.com/},
  url = 	 {http://jmvidal.cse.sc.edu/library/minton92a.pdf},
  cluster = 	 {10562872593729333238}
}
Last modified: Wed Mar 9 10:13:48 EST 2011