Un Método Exacto para el Problema de Equiparticionamiento de Grafos en Componentes Conexas
##plugins.themes.bootstrap3.article.main##
Resumen
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.
Descargas
Descargas
Detalles del artículo
Citas
Alpert, C. J., Kahng, A. B., & Yao, S.-Z. (1999). Spectral partitioning with multiple eigenvectors. Discrete Applied Mathematics, 90(1-3), 3–26.
Buluç, A., Meyerhenke, H., Safro, I., Sanders, P., & Schulz, C. (2016). Recent advances in graph partitioning. In Algorithm Engineering, (pp. 117–158). Springer International Publishing.
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 bisection. Mathematical Programming, 153(2), 417–458.
Fan, N., & Pardalos, P. M. (2010). Linear and quadratic programming approaches for the general graph partitioning problem. Journal of Global Optimization, 48(1), 57–71.
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 Programming Computation, 13(1), 75–132.
Jünger, M., Reinelt, G., & Pulleyblank, W. R. (1985). On partitioning the edges of graphs into connected subgraphs. Journal of Graph Theory, 9(4), 539–549.
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, D., Cong, G., Hendrickson, B., Shalf, J., Donofrio, D., Rowen, C., Oliker, L., Wehner, M., & Gustafson, J. L. (2011). Graph partitioning. In Encyclopedia of Parallel Computing, (pp. 805–808). Springer US.
Karypis, G., & Kumar, V. (1998). A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal of Scientific Computing, 20(1), 359–392.
Kernighanm, B., & Lin, S. (1970). An effective heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49(2), 291–307.
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, 44(8), 1100–1114.
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, separation and experiments. European Journal of Operational Research, 293(3), 826–836.
Sanders, P., & Schulz, C. (2012). Distributed evolutionary graph partitioning. Proceedings of the Workshop on Algorithm Engineering and Experiments, (pp. 16–29).
Sotirov, R. (2014). An efficient semidefinite programming relaxation for the graph partition problem. INFORMS Journal on Computing, 26(1), 16–30.
Wang, Y., Buchanan, A., & Butenko, S. (2017). On imposing connectivity constraints in integer programs. Mathematical Programming, 166(1-2), 241–271.