Métodos de programación entera mixta y clustering espectral para el problema de particionamiento balanceado de hipergrafos en k componentes
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