A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems

Steven Minton, Mark D. Johnston, Andrew B. Philips, and Philip Laird

One of the most promising general approaches for solving combinatorial search problems is to generate an initial, suboptimal solution and then to apply local repair heuristics. Techniques based on this approach have met with empirical success on many combinatorial problems, including the traveling salesman and graph partitioning problems[10]. Such techniques also have a long tradition in AI, most notably in problemsolving systems that operate by debugging initial solutions. In this paper, we describe how this idea can be extended to constraint satisfaction problems (CSPs) in a natural manner.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.