On the classification of NP-complete problems in terms of their correlation coefficient

Local search and its variants simulated annealing and tabu search are very popular metaheuristics to approximatively solve NP-hard optimization proble ms. Several experimental studies in the literature have shown that in pract ice some problems (e.g. the Traveling Salesman Problem, Quadratic Assignmen t Problem) behave very well with these heuristics, whereas others do not (e .g. the Low Autocorrelation Binary String Problem). The autocorrelation fun ction, introduced by Weinberger, measures the ruggedness of a landscape whi ch is formed by a cost function and a neighborhood. We use a derived parame ter, named the autocorrelation coefficient, as a tool to better understand these phenomena. In this paper we mainly study cost functions including pen alty terms. Our results can be viewed as a first attempt to theoretically j ustify why it is often better in practice to enlarge the solution space and add penalty terms than to work solely on feasible solutions. Moreover, som e new results as well as previously known results allow us to obtain a hier archy of combinatorial optimization problems relatively to their ruggedness . Comparing this classification with experimental results reported in the l iterature yields a good agreement between ruggedness and difficulty for loc al search methods. In this way, we are also able to justify theoretically w hy a neighborhood is better than another for a given problem. (C) 2000 Else vier Science B.V. All rights reserved.