Algoritmos paralelos de memoria compartida que determinan el menor tama˜no de un ´arbol binario al refinar un simplex regular

Abstract

En el ambito de la optimizacion global basada en tecnicas de ramificacion y acotacion, cuando el espacio de busqueda es un n-sımplex regular es habitual utilizar como regla de division la biseccion por el lado mayor, debido a que garantiza la convergencia del algoritmo. Cuando la dimension del n-sımplex es mayor de 2 existen varios lados mayores que pueden utilizarse para realizar la biseccion. La eleccion del lado mayor influye en el tamaño del arbol binario completo que se genera. Una seleccion eficiente del lado mayor puede reducir el coste computacional de los algoritmos de ramificacion y acotacion mencionados. En este estudio estamos interesados en conocer el tamaño del arbol o arboles mınimo(s). Para obtener una solucion de las instancias mas complejas del problema en un tiempo razonable es necesario el desarrollo de algoritmos paralelos. La complejidad del problema es debida a la necesidad de analizar todas y cada una de las posibles combinaciones de selecciones de los distintos lados mayores en el refinamiento. Aquí se comparan la eficiencia de distintas propuestas de algoritmos paralelos para sistemas de memoria compartida.