A framework for constructing complete algorithms based on local search

Abstract

Backtrack search enhanced by local consistency techniques can be effective at finding solutions for (or proving the infeasibility of) tightly-constrained problems with complex and overlapping constraints. By contrast, local search can be superior at optimizing problems that are loosely constrained, but is weaker on problems with a complex constraint satisfaction element, and cannot prove problem infeasibility. This paper describes local probing which marries the strengths of local search and backtrack search and is capable of finding a solution or proving that none exists. Local probing is a local search extension to an existing hybridization framework, probe backtrack search. Here, a master backtrack search algorithm hybridizes a slave local search algorithm, which solves dynamically created subproblems that are easier to solve than the original problem addressed. We present comparison results on resource constrained scheduling, showing how local probing successfully adds infeasibility proofs to its slave local search algorithm.