Using quadratic assignment methods to generate initial permutations for least-squares unidimensional scaling of symmetric proximity matrices

Combinatorial solution procedures for least-squares unidimensional scaling of symmetric proximity matrices frequently consist of two integrated processes: (a) the identification of a permutation of objects, and (b) the estimation of coordinate values on the continuum. These procedures typically require an initial permutation of objects. It is generally known that their final unidimensional scaling solutions are often very sensitive to these starting permutations, particularly when the number of objects is large (> 20). This paper demonstrates that, relative to random starting permutations, substantial improvements in final seriation quality and computational efficiency can be realized by using starting permutations obtained via solution to a quadratic assignment problem (QAP). Three methods-locally-optimal pairwise interchange (LOPI), simulated annealing (SA) and a hybrid (LOPI-SA)-were evaluated regarding their effectiveness and efficiency for solving the QAP. The results revealed that SA and LOPI-SA efficiently provided very good QAP solutions that subsequently led to good least-squares solutions.