Team formation problems: an integer linear optimization approach

Abstract

Given a group of individuals, each one with a single skill, and a social network capturing the mutual affinity among them, the Team Formation Problem (TFP) aims to find a single team that meets the skills needed to perform a task while seeking to optimize the communication costs between the involved individuals. In the first part of this work, we study a generalized version of the TFP denominated as Multiple Team Formation Problem (MTFP), which allows distinct demands of workers per ability as well as multiple work teams and fractions of dedication time per team for each individual. In this case, the total communication cost is given by the sum of weighted pairwise relations between members within a same team. In the second part, we introduce a new variant of the TFP to be called Competitive Teams Formation Problem (CTFP). Using the theory of social balance, in this problem, we represent the social network that connects the involved individuals as a signed graph and consider both intra-team and inter-teams communication costs by asking to have only positive relationships between individuals of a same team and only negative relationships between individuals of different teams. For the MTFP, we propose an Integer Linear Programming (ILP) formulation and sets of valid inequalities. Computational experiments attest that the ILP model strengthened by valid inequalities consistently outperforms the existing quadratic formulation for MTFP. We also consider a generalized version of the MTFP where individuals may have multiple skills. To handle this version, we adapt the initial ILP model into two new models and present other valid inequalities. For the CTFP, we also propose an ILP formulation and valid inequalities derived from the structural balance theory that enhance the computational performance of the model. Finally, we close this work with general conclusions and directions for future works.