A Branch-and-Bound Algorithm for Team Formation on Social Networks
Nihal Berktaş, Hande Yaman
Abstract
This paper presents an exact algorithm for the team formation problem, in which the aim is, given a project and its required skills, to construct a capable team that can communicate and collaborate effectively. This combinatorial optimization problem is modeled as a quadratic set covering problem. The study provides a novel branch-and-bound algorithm where a reformulation of the problem is relaxed so that it decomposes into a series of linear set covering problems, and the relaxed constraints are imposed through branching. The algorithm is able to solve instances that are intractable for commercial solvers. The study illustrates an efficient usage of algorithmic methods and modeling techniques for an operations research problem. It contributes to the field of computational optimization by proposing a new application and a new algorithm to solve a quadratic version of a classical combinatorial optimization problem.