Team Formation Problems: an integer linear optimization approach

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 thesis, we study a generalized version of the TFP denominated as Multiple Team Formation Problem (MTFP), which allows multiple teams with distinct demands of workers per ability and fractions of dedication time per team for each individual. In the second part, we introduce a new variant of the TFP to be called Competitive Teams Formation Problem (CTFP). We use the theory of social balance to represent the social network as a signed graph and consider both intra-team and inter-teams communication costs. For the MTFP, we propose an Integer Linear Programming (ILP) model and sets of valid inequalities. Computational experiments attest that the ILP model strengthened by valid inequalities consistently outperforms the existing quadratic model 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 that strengthen them. For the CTFP, we propose an ILP model and valid inequalities that enhance the computational performance of the model. Finally, we close this thesis with general conclusions and future works.