www.ai-center.com

Reference	Nareyek, A.; Smith, S. F.; and Ohler, C. M. 2004. Integration of a Refinement Solver and a Local-Search Solver. Technical Report, TR-RI-04-33, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, USA. August 2004.
Abstract	We describe an integration of a refinement solver and a local-search solver for constraint satisfaction, with the goal to use information from the local-search solution process as a basis for directing a backtracking-based refinement search. In this approach, the decision about the next refinement step is based on an interposed phase of constructing/revising a complete (but not necessarily feasible) variable assignment by local search, i.e., as a kind of variable- and value-ordering strategy. The assignment generated by local search is called a "probe." We investigate the efficiency of this hybrid search approach in the combinatorial domain of job-shop scheduling. First, we evaluate methods for improving probe-based guidance, by basing refinement decisions not only on the final assignment of the probe-construction phase but also on information gathered during the probe-construction process. We show that such techniques can result in a significant performance boost. Second, we consider the relative strengths of probe-based search control and search control that is directly based on refinement search and biased by more classically motivated variable- and value-ordering heuristics (incorporating domain-specific knowledge). Our results indicate that - while probe-based search performs better than an uninformed search - use of domain-specific knowledge proves to be a much more effective basis for search control than information about constraint interactions that is gained by local-search probes, and leads to substantially better performance.
Download	Rules and Regulations     [PDF; 87 Kb]   [zipped PDF; 66 Kb]     [download viewer]