Propuesta para abordar el problema de llenado mínimo mediante computo evolutivo.

Ponente(s): Luis Fernando Cuevas Munguía, Fernando Ignacio Becerra López

La programación semidefinida positiva (PSDP) permite que las variables de decisión se formulen como una matriz semidefinida positiva. Esta restricción es crucial en aplicaciones que modelan diversas condiciones físicas, estadísticas o estructurales, donde es común que las matrices involucradas sean dispersas. Un problema asociado es determinar eficientemente el número mínimo de aristas (fill-in) necesario para que el grafo asociado por la matriz dispersa sea cordal. Este problema es Np-completo, lo que implica que encontrar una solución global es complejo. En aplicaciones prácticas es suficiente tener una solución óptima. Una heurística ampliamente utilizada para encontrar soluciones es el algoritmo de mínimo grado. Aunque este método no garantiza agregar el número mínimo de aristas, ofrece una manera eficaz de resolver el sistema en un tiempo de complejidad acotado. Recientemente, se han utilizado métodos alternativos, principalmente estocásticos, para encontrar soluciones óptimas en un tiempo computacional viable. En este trabajo, se presenta una solución al problema de relleno mínimo mediante el uso de cómputo evolutivo.