Criticizing solutions to relaxed models yields powerful admissible heuristics

Branch-and-bound techniques allow intractable problems to be solved by using heuristics to bound the cost of partial solutions. The use of admissible heuristics can guarantee that the solutions found are optimal. This paper examines one paradigm-problem relaxation by constraint deletion-which has been used to develop many admissible heuristics. The paradigm suggests three steps: simplify (or relax) a problem, solve the simplified problem, and use that solution to guide the search for a solution to the original problem. We introduce the following extension to this methodology: by criticizing the feasibility of a relaxed solution, we arrive at a closer approximation of the solution to the original problem. We apply this methodology to two well-studied problems in operations research and artificial intelligence. For the traveling-salesman problem, iteration of our technique yields a series of novel heuristics, culminating in Held and Karp's minimum-spanning-tree heuristic. For the eight puzzle, it yields a heretofore undiscovered heuristic which is shown to perform significantly better than any previously known. © 1992.