Resumen de Un Método Exacto para el Problema de Equiparticionamiento de Grafos en Componentes Conexas

Estéfano Viteri Negrete, Ramiro Torres

• español

  En el presente trabajo, el problema de equiparticionamiento de grafos en componentes conexas es estudiado. El problema consiste en particionar un grafo no dirigido con costos sobre las aristas en un número fijo de componentes conexas, tal que el número de nodos en cada componente difiera en a lo más una unidad y el costo total de las aristas con nodos finales en la misma componente sea minimizado. Se presentan varios modelos de programación lineal entera usando diferentes enfoques (maximización de los costos de las aristas del corte y minimización de los costos de las aristas en cada componente conexa) y sus resultados son comparados. Además, se exponen varias familias de desigualdades válidas asociadas a los poliedros de estas formulaciones, junto con un algoritmo exacto tipo Branch & Cut. Finalmente, se reportan resultados computacionales basados en instancias simuladas de diferentes tamaños.

• English

  In the present work, the graph equipartitioning problem in connected components is studied. The problem consists of partitioning an undirected graph with cost on the edges into a fixed number of connected components, such that the number of nodes in each component differs in at most one unit and the total cost of the edges with end-nodesin the same connected component is minimized. Several integer linear programming models using different approaches (maximizing the edges in the cut or minimizing the edges in the connected components) are presented and the results are compared. Moreover, several families of valid inequalities associated to the polytope of these formulations, together with a Branch & Cut algorithm are exposed. Finally, computational results based on simulated instances of different sizes are reported.