Abstract
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 is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aarts E., Lenstra J.K. ed. (1997), Local Search in Combinatorial Optimization. John Wiley & Sons, Chichester
Armstrong D.E. (2002), A local search algorithm approach to analyzing the complexity of discrete optimization problems, Ph.D. Dissertation, University of Illinois, Urbana, IL
Armstrong D.E., Jacobson S.H. (2005), Data independent neighborhood functions and strict local optima. Discrete Applied Mathematics 143, 272–284
Armstrong D.E., Jacobson S.H. (2003), Studying the complexity of global verification for NP-hard discrete optimization problems. Journal of Global Optimization 27, 83–96
Ausiello G., D’Atri A., Protasi M. (1980), Structure preserving reductions among convex optimization problems. Journal of Computer and System Sciences 21, 136–153
Ausiello, G., Crescenzi P. and Protasi, M. (1995), Approximate solution of NP optimization problems, Theoretical Computer Science 150, 1–55.
Ausiello G., Crescenzi P., Gambosi G., Kann, Marchetti-Spaccamela A., Protasi M. (1999), Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag, Berlin
Ausiello G., Protasi M. (1995), Local search, reducibility and approximability of NP-optimization problems. Information Processing Letters 54, 73–79
Cook, S.A. (1971), The complexity of theorem-proving procedures, Proceedings of 3rd ACM Symposium on Theory of Computation, 151–158.
Crescenzi P., Trevisan L. (2000), On approximation scheme preserving reducibility and its applications. Theory of Computing Systems 33, 1–16
Garey M.R., Johnson D.S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, NY
Grotschel, M. and Lovasz, L. (1995), Combinatorial optimization, In: Graham, R., Grotschel, M. and Lovasz, L. (eds.), Handbook of Combinatorics, vol. II. pp. 1541–1597. North-Holland, Amsterdam.
Hoos H.H., Stutzle T. (2004), Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, San Francisco
Jacobson S.H., Solow D. (1993), The effectiveness of finite improvement algorithms for finding global optima. Methods and Models of Operations Research 37, 257–272
Johnson D.S., Papadimitriou C.H., Yannakakis M. (1988). How Easy is Local Search. Journal of Computer and System Sciences 37: 79–100
Papadimitriou C.H., Yannakakis M. (1991), Optimization, approximation, and complexity classes. Journal of Computer and System Sciences 43, 425–440
Pardalos P.M., Jha S. (1992), Complexity of uniqueness and local search in quadratic 0–1 programming. Operations Research Letters 11, 119–123
Prokopyev O.A., Huang H., Pardalos P.M. (2005), On complexity of unconstrained hyperbolic 0–1 programming problems. Operations Research Letters 33, 312–318
Rodl V., Tovey C.A. (1987), Multiple optima in local search. Journal of Algorithms 8, 250–259
Schulz, A.S. and Weismantel, R. (1999), An oracle-polynomial time augmentation algorithm for integer programming, Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, 967–968.
Schulz A.S., Weismantel R., Ziegler G.M. (1995). 0/1-Integer programming: optimization and augmentation are equivalent. In: Spirakis P. (eds). Lecture Notes in Computer Science. 979. Springer, Berlin, Germany, pp. 473–483
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is supported in part by the Air Force Office of Scientific Research (F49620-01-1-0007, FA9550-04-1-0110).
Rights and permissions
About this article
Cite this article
Armstrong, D.E., Jacobson, S.H. Analyzing the Complexity of Finding Good Neighborhood Functions for Local Search Algorithms. J Glob Optim 36, 219–236 (2006). https://doi.org/10.1007/s10898-006-9007-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-006-9007-2