Nuevos algoritmos para la resolución aproximada y exacta del problema de minimización del ancho de banda en matrices

Resumen

La minimización del ancho de banda es un problema clásico de optimización, Tuvo su origen en los años 50 en el contexto de la manipulación computacional de matrices estructurales dentro del campo de la ingeniería. Este problema es equivalente al problema del ancho de banda para grafos. Entre sus aplicaciones cabe destacar: la simplificación del proceso de resolución de sistemas de ecuaciones mediante el método de eliminación de Gauss, el diseño de sistemas de transmisión de energía, el diseño de circuitos, la aproximación de soluciones de ecuaciones en derivadas parciales o la ordenación y recuperación de la información en hipertextos. Si definimos el ancho de banda de una fila cualquiera de una matriz como el máximo de las distancias de los elementos no nulos de dicha fila a la diagonal principal, el ancho de banda de una matriz queda definido como el máximo de los anchos de todas sus filas. El objetivo es reducir el ancho de banda de la matriz en la mayor medida posible, mediante permutaciones de filas y de columnas. En el capítulo 1 presentamos una descripción más detallada del problema y sus aplicaciones, así como de los esquemas generales de las metodologías utilizadas para la resolución del problema. En el capítulo 2 presentamos un algoritmo basado en las metodologías GRASP (Greedy Randomized Adaptive Search Procedure) y Path Relinking. El capítulo 3 se centra en la resolución exacta del problema. Por un lado presentamos algunos resultados teóricos (concretamente una formulación lineal entera del problema y algunas cotas para ordenaciones parciales), y, por otro, describimos el algoritmo que sigue la metodología Branch and Bound y que hemos diseñado específicamente para este problema. Por último hemos estudiado los métodos de exploración basados en el uso de la memoria. Para ello, hemos propuesto dos nuevos métodos, uno basado en Búsqueda Tabú y otro basado en la metodología de Búsqu