Integrating Local Search Advice into Refinement Search (Or Not)

September 2003

Integrating Local Search Advice into Refinement Search (Or Not)

Authors:

A. Nareyek, S. F. Smith, and C. Ohler

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.
@workshop{Nareyek-2003-120528,
author = {A. Nareyek And S. F. Smith And C. Ohler},
title = {Integrating Local Search Advice into Refinement Search (Or Not)},
booktitle = {Proceedings of CP '03 3rd International Workshop on Cooperative Solvers in Constraint Programming},
year = {2003},
month = {September},
pages = {29 - 43},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.