El problema de minimización de la anchura de corte en ordenaciones lineales: resolución exacta y heurística

Abstract

La optimización es una disciplina que trata de encontrar solución a problemas de la vida cotidiana. Una gran cantidad de problemas que tienen interés en áreas científicas y tecnológicas pueden ser enunciados como problemas de optimización. Un problema de optimización es aquél en el que, habiendo muchas posibles soluciones y alguna forma clara de comparación entre ellas, se pretende encontrar la mejor de todas, es decir, la solución óptima. Los problemas de Optimización Combinatoria son un tipo de problemas de optimización cuyas soluciones están formadas por números enteros. Existen numerosos problemas de Optimización Combinatoria para los que no se conocen algoritmos capaces de resolverlos en tiempo polinómico. No obstante, dado el interés práctico de muchos de ellos, es necesario disponer de técnicas eficientes para abordarlos. Las técnicas existentes en la actualidad se podrían clasificar en exactas y aproximadas. Las técnicas exactas son capaces de encontrar la solución óptima, pero requieren un tiempo de cómputo elevado, por lo que son inviables cuando el tamaño del problema es grande. De entre las técnicas aproximadas destacan los algoritmos heurísticos, capaces de encontrar soluciones de alta calidad en un tiempo de cómputo razonable, pese a no poder certificar si la solución encontrada es óptima, ni cómo de lejos está de ella. El problema de la minimización de la anchura de corte en ordenaciones lineales es un problema NP-Difícil de Optimización Combinatoria y consiste en encontrar un etiquetado de los vértices de un grafo, de modo que se minimice el máximo número de aristas que sobrepasan el espacio entre cada dos vértices consecutivos, al ordenar los vértices del grafo sobre una línea recta. Este problema tiene aplicaciones en diseño de circuitos, migración y fiabilidad de redes de telecomunicaciones, representación automática de grafos y en recuperación de información. En esta Tesis Doctoral se proponen algoritmos exactos y heurísticos para la resolución del problema de la minimización de la anchura de corte en ordenaciones lineales. Los algoritmos exactos propuestos están basados en la técnica de Ramificación y Acotación, para la que se proponen distintas cotas inferiores y varios recorridos del árbol de exploración. Respecto a los algoritmos heurísticos, se proponen heurísticas constructivas, de mejora y de combinación de soluciones, que son embebidas dentro de un esquema híbrido GRASP con Búsqueda Dispersa. Tanto los algoritmos exactos, como los algoritmos heurísticos, mejoran los resultados obtenidos por los métodos existentes en el estado del arte, sobre los conjuntos de instancias evaluados.

Eduardo García Pardo

Full Professor

One of the founders of the investigation group GRAFO, whose main line of research is the development of algorithms to tackle optimization problems, the topic of the researcher’s Doctoral Thesis and which their most notable publications are framed.