Métodos exactos para el problema de k-particionamiento con restricciones de tamaño y peso

Abstract

Let G := (V, E) be a undirected graph with edge costs and node weigths. The partition problem over G is defined as finding a partition of V in a fixed number of subsets of nodes (or cliques), such that the sum of the cost of the edges with both ending nodes in the same subset is minimized. In this work an integer lineal programing model for the k− partition problem with size and weight restrictions is formulated, and this model is compared to the model proposed in Recalde et al. [2016]. For the two linear formulations, a Branch & Cut method will be used as an exact solving method. Furthermore, different types of cutting plane, such as triangular inequialities, 2-partition and cover planes will be included. Finally, computational results based upon both real and simulated instances are presented