Resumen de Un esquema basado en multiprocesamiento para la resolución de problemas de optimización

José María Troya Linero , Manuel Ortega Cantero , Antonio Vaquero Sánchez

• español

  Existen muchos problemas de optimización que no pueden resolverse en tiempo polinomial, y por tanto, son intratables cuando su tamaño es grande. Dado el avance tecnológico registrado en los últimos años en el diseño VLSI, una posible solución podría ser utilizar sistemas no secuenciales. En este sentido, uno de los métodos más aplicados en la resolución de problemas de optimización, conocido como de ramificación y acotación, es suceptible de paralelización. En este artículo damos un esquema paralelo para este método, basado en la utilización de tantas listas de nodos activos, como procesadores compogan el sistema. El comportamiento del modelo es evaluado mediante la generación aleatoria de árboles de búsqueda.

• English

  There are many optimization problems that cannot be solved in the polynomial time, and then they are intractables when the problem size grows. With the technological advances in VSLI design, using parallel processing, would be a solution.

  In this paper we give a parallel scheme for one of the most used methods in optimization problems solving, the branch-and-bound method.

  This scheme is based in the use of as much list of active nodes as processors have the system. The performance of the model is evaluated for random generated search trees.