Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems

Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems

| Steven Minton¹, Mark D. Johnston², Andrew B. Philips¹, Philip Laird³
This paper presents a heuristic repair method for solving large-scale constraint satisfaction and scheduling problems. The method starts with an inconsistent assignment and searches for repairs that minimize constraint violations. It uses a min-conflicts heuristic, which selects a variable that is currently in conflict and assigns it a value that minimizes the number of conflicts. The method is effective for problems like the n-queens problem, where it outperforms traditional backtracking techniques. It has also been successfully applied to scheduling astronomical observations on the Hubble Space Telescope. The method is based on a neural network called the GDS network, which was developed by Adorf and Johnston. The GDS network is a modified Hopfield network that can rapidly find solutions for many problems. However, it may get stuck in local minima. The paper analyzes the GDS network and finds that its performance is influenced by the structure of the problem. It also introduces a symbolic method that uses the min-conflicts heuristic for hill climbing, which is effective for solving constraint satisfaction problems. The paper evaluates the performance of the min-conflicts heuristic on various tasks, including the n-queens problem, graph-coloring problems, and scheduling applications. It shows that the min-conflicts heuristic performs well on these tasks, especially when combined with other heuristics. The method is simple and efficient, making it suitable for practical applications. It is particularly effective for scheduling tasks, where it can be used for overconstrained problems and for rescheduling in a natural manner. The paper concludes that the min-conflicts heuristic is a promising approach for solving constraint satisfaction and scheduling problems.This paper presents a heuristic repair method for solving large-scale constraint satisfaction and scheduling problems. The method starts with an inconsistent assignment and searches for repairs that minimize constraint violations. It uses a min-conflicts heuristic, which selects a variable that is currently in conflict and assigns it a value that minimizes the number of conflicts. The method is effective for problems like the n-queens problem, where it outperforms traditional backtracking techniques. It has also been successfully applied to scheduling astronomical observations on the Hubble Space Telescope. The method is based on a neural network called the GDS network, which was developed by Adorf and Johnston. The GDS network is a modified Hopfield network that can rapidly find solutions for many problems. However, it may get stuck in local minima. The paper analyzes the GDS network and finds that its performance is influenced by the structure of the problem. It also introduces a symbolic method that uses the min-conflicts heuristic for hill climbing, which is effective for solving constraint satisfaction problems. The paper evaluates the performance of the min-conflicts heuristic on various tasks, including the n-queens problem, graph-coloring problems, and scheduling applications. It shows that the min-conflicts heuristic performs well on these tasks, especially when combined with other heuristics. The method is simple and efficient, making it suitable for practical applications. It is particularly effective for scheduling tasks, where it can be used for overconstrained problems and for rescheduling in a natural manner. The paper concludes that the min-conflicts heuristic is a promising approach for solving constraint satisfaction and scheduling problems.
Reach us at info@study.space