Problema de formação de equipes com caminhos positivos

Abstract

Information obtained from social networks has frequently been used to solve applications in Operations Research, such as the Team Formation Problem, whose goal is to find a group of the workers that collectively cover a set of skills and can work collaboratively and effectively. In the literature, different approaches have been used to assess the synergy between team members, giving rise to various versions of this problem. In this work, we used the Structural Balance Theory to define compatibility between pairs of individuals in a social network. Therefore, the social networks are represented by signed graphs, and the compatibility metric is calculated from the analysis of positive paths (with an even number of negative edges) between pairs of distinct vertices. With this, we introduced and studied a new version of the problem, to be called the Team Formation Problem with Positive Paths. As preliminary work, we revisited the Shortest Positive Path Problem in directed and undirected signed graphs, compiling and rewriting algorithms, complexity results and mathematical formulations. For the main problem, we presented two Integer Linear Programming formulations and a strategy for decomposing the formulations, which resulted in a significant gain in computational performance. In addition, we derived valid inequalities, some of which also contributed to improving the performance of the decomposed model. The methods, implemented using C++ language and CPLEX solver, were applied in a set of instances based on real or synthetic social networks. An analysis of the computational experiments carried out proves the potential efficiency of the proposed decomposition strategy and valid inequalities.