Local Search for Heuristic Guidance in Tree Search

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 sampling possible (but not necessarily feasible) variable assignments by local search. This information 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 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 biased by more classically motivated variable- and value-ordering heuristics (incorporating domain-specific knowledge) that are not based on local search. Our results indicate that - while probe-based search performs better than an uninformed search - use of domain-specific knowledge is 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. This paper provides only a brief overview. For a detailed presentation, please have a look at (2). strained regions of the underlying search space. In this paper, we focus specifically on use of the inconsistency measure of local search as guidance for determining which refinements to apply within a refinement search. First, we consider the added benefit of factoring information related to the local search's assignment history into search-control decisions. Second, we consider the relative strengths of probe-based heuristics in relation to uninformed refinement search and a search control bias that is provided by more classical heuristics that incorporate knowledge of the problem domain at hand. We investigate these issues in the application domain of job-shop scheduling.