Integrating Local Search Advice into Refinement Search (Or Not)

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.