Resumen

Dado un conjunto de objetos y una matriz de disimilitud simétrica con la diagonal principal igual a cero y entradas no negativas fuera de la diagonal, el problema de escalamiento unidimensional de mínimos cuadrados busca encontrar un arreglo de objetos a lo largo de una línea recta de manera que las distancias entre pares de objetos reflejen las disimilitudes representadas por la matriz. En este documento, proponemos un algoritmo mejorado de ramificación y acotamiento para resolver este problema. Los ingredientes principales del algoritmo incluyen una técnica novedosa de cota superior basada en el modelo de asignación lineal y una prueba de dominancia que permite reducir considerablemente la redundancia en el proceso de enumeración. Una cota inferior inicial para el algoritmo es proporcionada por una heurística de búsqueda tabú iterada. Para mejorar el rendimiento de esta heurística, desarrollamos un método eficiente para explorar el vecindario de intercambio de pares de una solución en el espacio de búsqueda. El principio básico y las fórmulas del método también se utilizan en la implementación de la

• Materias:Modelado matemático Modelo de red neuronal Tasa de convergencia Aritmética Ondículas libres
• Subjects:Mathematical modeling Neural network model Convergence rate Arithmetic Free wavelets
• Palabras claves:Objetos; Matriz de disimilitud simétrica; Problema de escalado unidimensional de mínimos cuadrados; Disposición; Distancias entre pares; Algoritmo de ramificación y acotación
• Keywords:Objects; Symmetric dissimilarity matrix; Least-squares unidimensional scaling problem; Arrangement; Pairwise distances; Branch-and-bound algorithm