Analyzing the Complexity of Finding Good Neighborhood Functions for Local Search Algorithms

A drawback to using local search algorithms to address NP-hard discrete optimization problems is that many neighborhood functions have an exponential number of local optima that are not global optima (termed L-locals). A neighborhood function η is said to be stable if the number of L-locals is polynomial. A stable neighborhood function ensures that the number of L-locals does not grow too large as the instance size increases and results in improved performance for many local search algorithms. This paper studies the complexity of stable neighborhood functions for NP-hard discrete optimization problems by introducing neighborhood transformations. Neighborhood transformations between discrete optimization problems consist of a transformation of problem instances and a corresponding transformation of solutions that preserves the ordering imposed by the objective function values. In this paper, MAX Weighted Boolean SAT (MWBS), MAX Clause Weighted SAT (MCWS), and Zero-One Integer Programming (ZOIP) are shown to be NPO-complete with respect to neighborhood transformations. Therefore, if MWBS, MCWS, or ZOIP has a stable neighborhood function, then every problem in NPO has a stable neighborhood function. These results demonstrate the difficulty of finding effective neighborhood functions for NP-hard discrete optimization problems.This research is supported in part by the Air Force Office of Scientific Research (F49620-01-1-0007, FA9550-04-1-0110).