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

• Viteri Negrete, Estéfano ^[1] ; Torres, Ramiro ^[1]
  1. [1] Escuela Politécnica Nacional

     Escuela Politécnica Nacional

     Quito, Ecuador

     
• Localización: Revista Politécnica, ISSN-e 2477-8990, Vol. 51, Nº. 1, 2023 (Ejemplar dedicado a: Revista Politécnica), págs. 103-116
• Idioma: español
• DOI: 10.33333/rp.vol51n1.09
• Títulos paralelos:
  • An Exact Approach for the Graph Equipartitioning Problem in Connected Components
• Enlaces
  • Texto completo
• Resumen
  • 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.

• Referencias bibliográficas
  • Alpert, C. J., Kahng, A. B., & Yao, S.-Z. (1999). Spectral partitioning with multiple eigenvectors. Discrete Applied Mathematics, 90(1-3),...
  • Buluç, A., Meyerhenke, H., Safro, I., Sanders, P., & Schulz, C. (2016). Recent advances in graph partitioning. In Algorithm Engineering,...
  • Camilus, K., & V K, G. (2012). A review on graph based segmentation. International Journal of Image, Graphics and Signal Processing, 4.
  • Chopra, S., & Rao, M. R. (1993). The partition problem. Mathematical Programming, 59(1-3), 87–115.
  • Delling, D., Fleischman, D., Goldberg, A. V., Razenshteyn, I., & Werneck, R. F. (2015). An exact combinatorial algorithm for minimum graph...
  • Fan, N., & Pardalos, P. M. (2010). Linear and quadratic programming approaches for the general graph partitioning problem. Journal of...
  • Grötschel, M., & Wakabayashi, Y. (1989). A cutting plane algorithm for a clustering problem. Mathematical Programming, 45, 59–96.
  • Gurobi Optimization, LLC (2021). Gurobi Optimizer Reference Manual. URL https://www.gurobi.com
  • Hendrickson, B., & Kolda, T. G. (2000). Graph partitioning models for parallel computing. Parallel Computing, 26(12), 1519–1534.
  • Hojny, C., Joormann, I., Lüthen, H., & Schmidt, M. (2021). Mixed-integer programming techniques for the connected max-k-cut problem. Mathematical...
  • Jünger, M., Reinelt, G., & Pulleyblank, W. R. (1985). On partitioning the edges of graphs into connected subgraphs. Journal of Graph Theory,...
  • Kahng, A. B., Lienig, J., Markov, I. L., & Hu, J. (2011). VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer Netherlands.
  • Kalyanaraman, A., Hammond, K., †, J. N., Krishnan, M., Palmer, B., Tipparaju, V., Harrison, R., Chavarria-Miranda, D., Makino, J., Bader,...
  • Karypis, G., & Kumar, V. (1998). A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal of Scientific...
  • Kernighanm, B., & Lin, S. (1970). An effective heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49(2),...
  • Labbé, M., & Özsoy, F. A. (2010). Size-constrained graph partitioning polytopes. Discrete Mathematics, 310(24), 3473– 3493.
  • Mehrotra, A., Johnson, E. L., & Nemhauser, G. L. (1998). An optimization based heuristic for political districting. Management Science,...
  • Mitchell, J. E. (2003). Realignment in the national football league: Did they do it right? Naval Research Logistics, 50(7), 683–701.
  • Miyazawa, F. K., Moura, P. F., Ota, M. J., & Wakabayashi, Y. (2021). Partitioning a graph into balanced connected classes: Formulations,...
  • Sanders, P., & Schulz, C. (2012). Distributed evolutionary graph partitioning. Proceedings of the Workshop on Algorithm Engineering and...
  • Sotirov, R. (2014). An efficient semidefinite programming relaxation for the graph partition problem. INFORMS Journal on Computing, 26(1),...
  • Wang, Y., Buchanan, A., & Butenko, S. (2017). On imposing connectivity constraints in integer programs. Mathematical Programming, 166(1-2),...