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

AbstractLocal search and its variants simulated annealing and tabu search are very popular meta-heuristics to approximatively solve NP-hard optimization problems. Several experimental studies in the literature have shown that in practice some problems (e.g. the Traveling Salesman Problem, Quadratic Assignment Problem) behave very well with these heuristics, whereas others do not (e.g. the Low Autocorrelation Binary String Problem). The autocorrelation function, introduced by Weinberger, measures the ruggedness of a landscape which is formed by a cost function and a neighborhood. We use a derived parameter, named the autocorrelation coefficient, as a tool to better understand these phenomena. In this paper we mainly study cost functions including penalty terms. Our results can be viewed as a first attempt to theoretically justify why it is often better in practice to enlarge the solution space and add penalty terms than to work solely on feasible solutions. Moreover, some new results as well as previously known results allow us to obtain a hierarchy of combinatorial optimization problems relatively to their ruggedness. Comparing this classification with experimental results reported in the literature yields a good agreement between ruggedness and difficulty for local search methods. In this way, we are also able to justify theoretically why a neighborhood is better than another for a given problem