ECAI 2004 Conference Paper

[full paper]

Integrating Local-Search Advice Into Refinement Search (Or Not)

Alexander Nareyek, Stephen F. Smith, Christian M. Ohler

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 investigate the efficacy 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). 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.

Keywords: Constraint Satisfaction, Constraint Programming, Meta-Heuristics, Scheduling, Search, Automated Reasoning

Citation: Alexander Nareyek, Stephen F. Smith, Christian M. Ohler: Integrating Local-Search Advice Into Refinement Search (Or Not). In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.1069-1070.