An improved exact algorithm for least-squares unidimensional scaling
type: Item
instance of: scholarly article
title: An improved exact algorithm for least-squares unidimensional scaling
zbMATH Open document ID: 1266.65072
DOI: 10.1155/2013/890589
published in: Journal of Applied Mathematics
publication date: 2013-06-14T00:00:00Z
review text: Summary: Given \(n\) objects and an \(n \times n\) 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 \(36 \times 36\) Morse code dissimilarity matrix.
Mathematics Subject Classification ID: 65F35
zbMATH DE Number: 6175972
Wikidata QID: Q59005050
author: Gintaras Palubeckis
describes a project that uses: pertsaus2
describes a project that uses: PermutMatrix
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2013/890589
OpenAlex ID: W1978677945
cites work: Modern multidimensional scaling. Theory and applications.
cites work: The antiferromagnetic transition for the square-lattice Potts model
cites work: Synergies of operations research and data mining
cites work: Possibilistic evidential clustering
cites work: Optimal least-squares unidimensional scaling: improved branch-and-bound procedures and comparison to dynamic programming
cites work: Linear unidimensional scaling in the \(L_2\)-norm: Basic optimization methods using MATLAB.
cites work: Q5706832
cites work: Metric unidimensional scaling and global optimization
cites work: A permutation-translation simulated annealing algorithm for \(L_{1}\) and \(L_{2}\) unidimensional scaling
cites work: On the performance of simulated annealing for large-scale \(L_{2}\) unidimensional scaling
cites work: Heuristic implementation of dynamic programming for matrix permutation problems in combinatorial data analysis
cites work: Iterated tabu search for the maximum diversity problem
cites work: A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
cites work: Multipath adaptive tabu search for a vehicle control problem
cites work: Bacterial foraging-tabu search metaheuristics for identification of nonlinear friction model
cites work: Dominance rules in combinatorial optimization problems
cites work: The tunneling method for global optimization in multidimensional scaling
cites work: Combinatorial data analysis. Optimization by dynamic programming
DBLP publication ID: journals/jam/Palubeckis13
description: scientific article