Morph-Based Local-Search Heuristics for Large-Scale Combinatorial Data Analysis

There are a variety of data analysis techniques in the social and behavioral sciences that require the solution of NP-complete optimization problems. Unfortunately, optimal solution methods are generally intractable for problems of practical size and thus there has been an emphasis on the development of heuristic procedures. Although local-search procedures, such as simulated annealing, have been tested on several combinatorial data analysis problems, they have frequently been criticized as computationally inefficient and therefore impractical for large problems. This paper presents a process called ‘morphing’ that can substantially increase the efficiency and effectiveness of local-search heuristics. The new procedure is compared to replications of a heuristic battery of local-operations across a set of large metric unidimensional scaling (seriation) problems. Generalizations of the morphing process to other problems in combinatorial data analysis are also discussed. Copyright Springer-Verlag New York Inc. 1999