ECAI 2004 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

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.

[prev] [tofc] [next]

ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).