Métodos de programación entera mixta y clustering espectral para el problema de particionamiento balanceado de hipergrafos en k componentes

Read full text Summarise with VIRAT
Authors: Karen Estefania Acosta Arias
Cited by: 0
References: 43

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Este trabajo estudia el problema de particionamiento de un hipergrafo en un número fijo de componentes bajo un objetivo de optimización. El objetivo consiste en dividir el conjunto de nodos en subconjuntos disjuntos, es decir, que cada nodo pertenezca a una única componente. Dado un hipergrafo ponderado y un número específico de particiones, se estudian dos variantes del problema: (1) particiones con restricciones de tamaño, y (2) particiones con restricciones de tamaño donde cada subconjunto de nodos debe estar cubierto por un subconjunto de hiperaristas totalmente contenidas en dicho subconjunto. Ambas variantes se rigen por una función objetivo que fomenta una alta conectividad dentro de cada componente y conexiones dispersas entre componentes. Para esto se definen las matrices relacionadas al hipergrafo que ayudan a capturar de mejor forma la estructura de las hiperaristas. Considerando que los algoritmos que se aplican en grafos no siempre escalan bien a hipergrafos, debido a la naturaleza combinatoria del problema, en este proyecto se proponen dos enfoques para abordar cada una de las variaciones del problema: primero, un modelo entero no lineal y segundo, un método de solución basado en el algoritmo de generación de columnas asistido con agrupamiento espectral. Ademas, el problema pricing asociado al algoritmo de generación de columnas para cada variación del problema es no lineal, por lo cual, se plantea un algoritmo heurístico para encontrar una solución aproximada del problema. El método de agrupamiento espectral propuesto en este trabajo utiliza una variante del algoritmo k medias con restricciones de tamaño. Los modelos y métodos propuestos se evalúan mediante experimentos computacionales sobre instancias simuladas, analizando la calidad de las soluciones y su desempeño computacional.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Advanced Optimization Algorithms Research Advanced Clustering Algorithms Research

Publication details

Journal / source
Repositorio Digital (Escuela Politécnica Nacional)
Publication date
23 March 2026
Language
ES
Document type
Thesis