Faculty of Informatics, Kaunas University of Technology, Studentu 50-408, 51368 Kaunas, Lithuania
Copyright © 2013 Gintaras Palubeckis. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Given n objects and an symmetric dissimilarity matrix D with zero main diagonal
and nonnegative off-diagonal entries, the least-squares unidimensional scaling problem
asks to find an arrangement of objects along a straight line such that the pairwise distances
between them reflect dissimilarities represented by the matrix D. In this paper, we propose an improved branch-and-bound algorithm for solving this problem. The main
ingredients of the algorithm include an innovative upper bounding technique relying on
the linear assignment model and a dominance test which allows considerably reducing the
redundancy in the enumeration process. An initial lower bound for the algorithm is provided
by an iterated tabu search heuristic. To enhance the performance of this heuristic
we develop an efficient method for exploring the pairwise interchange neighborhood of a
solution in the search space. The basic principle and formulas of the method are also used
in the implementation of the dominance test. We report computational results for both
randomly generated and real-life based problem instances. In particular, we were able to
solve to guaranteed optimality the problem defined by a Morse code dissimilarity matrix.