www.ai-center.com

Reference	Nareyek, A.; Smith, S. F.; and Ohler, C. M. 2003. Integrating Local-Search Advice Into Refinement Search (Or Not). In Proceedings of the CP 2003 Third International Workshop on Cooperative Solvers in Constraint Programming, 29-43.
Abstract	Recent work has shown the promise in using local-search "probes" 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 a complete (but not necessarily feasible) variable assignment. This assignment is then used to decide on which refinement to take, i.e., as a kind of variable- and value-ordering strategy. In this paper, we further investigate this hybrid search approach. 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. Second, we consider the relative strengths of probe-based search control and search control that is biased by more classically motivated variable- and value-ordering heuristics (incorporating domain-specific knowledge). The approaches are evaluated on various problems from the job-shop scheduling domain. 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; 166 Kb]   [zipped PDF; 142 Kb]     [download viewer]