Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems

@article{minconflicts-ai58,
   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.},
   apice = {MinconflictsAi58},
   author = {Steven Minton and Mark D. Johnston and Andrew B. Philips and Philip Laird},
   doi = {10.1016/0004-3702(92)90007-K},
   issn = {0004-3702},
   journal = {Artificial Intelligence},
   month = dec,
   number = {1-3},
   numpages = 45,
   openalex = {W2121766240},
   pages = {161--205},
   publisher = {Elsevier B.V.},
   title = {Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems},
   url = {https://www.sciencedirect.com/science/article/pii/000437029290007K},
   volume = 58,
   year = 1992
}