An improved exact algorithm for least-squares unidimensional scaling
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.
- Optimal least-squares unidimensional scaling: improved branch-and-bound procedures and comparison to dynamic programming
- A permutation-translation simulated annealing algorithm for \(L_{1}\) and \(L_{2}\) unidimensional scaling
- Metric unidimensional scaling and global optimization
- A nonlinear programming approach to metric unidimensional scaling
- Branch and bound algorithm for multidimensional scaling with city-block metric
- A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
- A permutation-translation simulated annealing algorithm for \(L_{1}\) and \(L_{2}\) unidimensional scaling
- Bacterial foraging-tabu search metaheuristics for identification of nonlinear friction model
- Combinatorial data analysis. Optimization by dynamic programming
- Dominance rules in combinatorial optimization problems
- Heuristic implementation of dynamic programming for matrix permutation problems in combinatorial data analysis
- scientific article; zbMATH DE number 2231543 (Why is no real title available?)
- Iterated tabu search for the maximum diversity problem
- Linear unidimensional scaling in the L₂-norm: Basic optimization methods using MATLAB.
- Metric unidimensional scaling and global optimization
- Modern multidimensional scaling. Theory and applications.
- Multipath adaptive tabu search for a vehicle control problem
- On the performance of simulated annealing for large-scale \(L_{2}\) unidimensional scaling
- Optimal least-squares unidimensional scaling: improved branch-and-bound procedures and comparison to dynamic programming
- Possibilistic evidential clustering
- Synergies of operations research and data mining
- The antiferromagnetic transition for the square-lattice Potts model
- The tunneling method for global optimization in multidimensional scaling
- A simulated annealing heuristic for unidimensional and multidimensional (city-block) scaling of symmetric proximity matrices.
- Optimal least-squares unidimensional scaling: improved branch-and-bound procedures and comparison to dynamic programming
- scientific article; zbMATH DE number 953048 (Why is no real title available?)
- Least squares metric, unidimensional scaling of multivariate linear models
- A permutation-translation simulated annealing algorithm for \(L_{1}\) and \(L_{2}\) unidimensional scaling
- Scaled AAN for fixed-point multiplier-free IDCT
This page was built for publication: An improved exact algorithm for least-squares unidimensional scaling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2375707)
