An Improved Exact Algorithm for Least-Squares Unidimensional Scaling

Given n objects and an symmetric dissimilarity matrix D with zero main diagonaland nonnegative off-diagonal entries, the least-squares unidimensional scaling problemasks to find an arrangement of objects along a straight line such that the pairwise distancesbetween them reflect dissimilarities represented by the matrix D. In this paper, we propose an improved branch-and-bound algorithm for solving this problem. The mainingredients of the algorithm include an innovative upper bounding technique relying onthe linear assignment model and a dominance test which allows considerably reducing theredundancy in the enumeration process. An initial lower bound for the algorithm is providedby an iterated tabu search heuristic. To enhance the performance of this heuristicwe develop an efficient method for exploring the pairwise interchange neighborhood of asolution in the search space. The basic principle and formulas of the method are also usedin the implementation of the dominance test. We report computational results for bothrandomly generated and real-life based problem instances. In particular, we were able tosolve to guaranteed optimality the problem defined by a Morse code dissimilarity matrix