A local search algorithm approach to analyzing the complexity of discrete optimization problems

This dissertation analyzes the complexity of constructing effective local search algorithms for intractable discrete optimization problems. Order transformations and neighborhood transformations between discrete optimization problems are introduced that preserve the objective function values over the problems' solution spaces. Several problems are shown to be complete with respect to these transformations. The key implications of these results are that finding effective neighborhood functions for certain problems is at least as hard as finding such neighborhood functions for any other problem. For example, it is shown that if maximum clause weighted satisfiability has a polynomially computable neighborhood function with a polynomial number of local optima that are not global optima, then every problem in NPO has a polynomially computable neighborhood function with a polynomial number of local optima that are not global optima.; A neighborhood function that is polynomial in size and independent of the problem data is said to be reasonable. In particular, the number of local optima that are not global optima is examined for reasonable neighborhood functions of a variety of discrete optimization problems. The (semi-) data independent order transformation is introduced to show how the properties of reasonable neighborhood functions can be transformed between discrete optimization problems. Other results show that many discrete optimization problems have the property that every reasonable neighborhood function has strict local optima that are not global optima. Many of these results demonstrate the drawbacks of using data independent neighborhood functions.; The properties of polynomially computable neighborhood functions are also examined. The global verification of several problems is proven to be NP-complete. These results are extended to show that polynomially computable neighborhood functions have arbitrarily poor local optima.