Partición de Grafos con Restricciones de Tamaño, Peso y Pertenencia

Abstract

The main objective of this work is to develop an efficient algorithm to find an acceptable solution to the graph partitioning problem with restrictions of size, weight and membership in a reasonable computation time. The problem addressed here is related to a team’s group construction problem in the second category of the ecuadorian football championship. First, the problem is formulated as an integer linear programming problem. Second, the provincial grouping of the teams playing in the second category of the ecuadorian football championship is explained. Third, a new grouping methodology of the teams is proposed, along with an alternative championship scheme to make it more competitive. Moreover, Kernighan-Lin based heuristics are addressed to find good solutions in a reasonable computation time. Finally, some numerical experiments, obtained from the real world application, are shown to evaluate the heuristic’s performace.