En matemáticas, la optimización es la disciplina encargada de encontrar entradas a una función que minimice o maximice su valor, en muchos casos sujeta a restricciones. La optimización combinatoria es una rama de la optimización con aspectos comunes de matemática aplicada, ciencias de la computación e investigación operativa que trata problemas cuyas soluciones son discretas. En la actualidad es posible resolver problemas de la vida real que en el pasado eran intratables gracias a los avances tecnológicos en algorítmica y en hardware de computación. La optimización computacional incluye las disciplinas de investigación operativa para modelar el sistema, matemáticas para formular el modelo, ciencias de la computación para el diseño y análisis de algoritmos, e ingeniería del software para implementar el modelo.
A la hora de seleccionar una técnica para resolver un determinado problema de optimización se debe tener en cuenta la complejidad algorítmica del problema, que viene determinada por criterios de espacio (cuánta memoria se necesita para resolver un problema) y tiempo (cuántos pasos se requieren para resolverlo). La categoría de problemas NP-duros son considerados los problemas más complejos, ya que cuando dicho tamaño aumenta, el problema se vuelve rápidamente inabordable. Por este motivo, la aplicación de técnicas deterministas no es eficiente para instancias de problemas de tamaño elevado, razón por la cual se han desarrollado técnicas heurísticas. Las heurísticas son métodos o algoritmos exploratorios que no aseguran soluciones óptimas, sino solamente soluciones válidas y aproximadas. Sin embargo, la calidad de las soluciones obtenidas puede ser mejorada mediante una adecuada combinación (hibridación) de diferentes métodos que permitan aprovechar las ventajas que ofrecen dichas técnicas de forma separada.
Hasta hace relativamente poco tiempo, la inmensa mayoría de problemas han sido modelados mediante una formulación mono-objetivo, incluyendo o no restricciones adicionales. Sin embargo, existe un elevado número de aplicaciones que requieren de la optimización simultánea de varios objetivos, que suelen estar en conflicto. Por esta razón, diversos autores han propuesto durante los últimos años diferentes procedimientos de optimización multi-objetivo, usualmente basados en el concepto de óptimo de Pareto. Tanto para el caso de tratar problemas mono-objetivo como multi-objetivo, y pese a las mejoras computacionales que han tenido las estaciones de trabajo, existen problemas de tal complejidad e instancias de problemas tan grandes que los métodos heurísticos pueden resultar ineficientes debido al elevado tiempo de ejecución que requieren para encontrar soluciones aceptables. Por este motivo, el procesamiento paralelo se convierte en la herramienta más adecuada para acotar dichos tiempos de respuesta sin deteriorar la calidad de las soluciones obtenidas.
En esta tesis doctoral se analizan dos problemas NP-duros: la repartición de grafos y el diseño óptimo de redes de distribución de agua malladas. El problema de repartición de grafos consiste en dividir un grafo en varios sub-grafos de forma que el número de aristas que conectan vértices pertenecientes a diferentes sub-grafos sea mínimo, manteniendo el desequilibrio entre la suma de pesos de cada sub-grafo por debajo de un cierto umbral (formulación mono-objetivo con restricciones), o también se minimiza (formulación multi-objetivo). Aunque la formulación multi-objetivo es más difícil de abordar, resulta más adecuada para aplicaciones realistas, como el balanceo de carga, el diseño VLSI, la planificación de tareas, etc. Por otro lado, el problema del diseño de redes de distribución de agua malladas consiste en encontrar la forma más económica de suministrar agua a los usuarios desde las fuentes, a la vez que se satisfacen unos requisitos establecidos, normalmente asociados a la fiabilidad. La fiabilidad hace referencia a la capacidad de la red de proveer un suministro adecuado a los consumidores bajo cualquier condición de operación en un periodo de tiempo dado.
Como resultado del trabajo de investigación, se han diseñado e implementado diferentes técnicas heurísticas simples e híbridas, mono-objetivo y multi-objetivo, secuenciales y paralelas, para solucionar problemas de optimización relevantes. Los algoritmos propuestos están basados en técnicas de búsqueda local como Enfriamiento Simulado, Búsqueda Tabú, Búsqueda Dispersa, etc. Además de los algoritmos propuestos, y con el objetivo de establecer comparaciones robustas entre técnicas, se han adaptado a ambos problemas diferentes técnicas encontradas en la literatura y propuestas previamente por otros autores. Los resultados obtenidos por los algoritmos propuestos en ambos problemas consiguen igualar e incluso mejorar en algunos casos los mejores resultados conocidos hasta el momento. Las conclusiones obtenidas en esta tesis contribuyen a abrir nuevas áreas potenciales de investigación dentro del campo de la optimización computacional.
