Characterizing neighborhoods favorable to local search techniques

NP-Complete problems are the most difficult problems to solve and polynomial time algorithms to solve these problems do not exist. One of the more powerful approaches for such problems are heuristic direct search techniques. For a given problem, a landscape is composed of (1) a solution space, (2) an objective function value defined at all elements of the solution space and (3) a direct search neighborhood defined for each element of the solution space. The goal of the research documented in this dissertation was to extend previous characterizations of landscapes conducive to the success of direct search methodologies. The primary contributions of this dissertation are as follows: (1) The extension of the characterization of AR(1) elementary landscapes to include arbitrary neighborhood definitions (2) The creation of an entirely new class of landscapes favorable to direct search methods, a subset of the AR(p) neighborhoods where p>1 (3) The development of a lower (upper) bound for a local minima (maxima) in AR(1) elementary landscapes using information stability (4) The characterization multistep composite AR(1) elementary landscapes