A Branch-and-Bound Algorithm for Team Formation on Social Networks

Nihal Berktaş () and Hande Yaman ()
Additional contact information
Nihal Berktaş: Department of Industrial Engineering, Bilkent University, 06800 Çankaya/Ankara, Turkey
Hande Yaman: Research Centre for Operations Research and Statistics (ORSTAT), Faculty of Economics and Business, Katholieke Universiteit Leuven, Leuven 3000, Belgium

INFORMS Journal on Computing, 2021, vol. 33, issue 3, 1162-1176

Abstract: The team formation problem (TFP) aims to construct a capable team that can communicate and collaborate effectively. The cost of communication is quantified using the proximity of the potential members in a social network. We study a TFP with two measures for communication effectiveness; namely, we minimize the sum of communication costs, and we impose an upper bound on the largest communication cost. This problem can be formulated as a constrained quadratic set covering problem. Our experiments show that a general-purpose solver is capable of solving small and medium-sized instances to optimality. We propose a branch-and-bound algorithm to solve larger sizes: we reformulate the problem and relax it in such a way that it decomposes into a series of linear set covering problems, and we impose the relaxed constraints through branching. Our computational experiments show that the algorithm is capable of solving large-size instances, which are intractable for the solver. Summary of Contribution: This paper presents an exact algorithm for the Team Formation Problem (TFP), 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 modelling techniques for an operations research problem. It contributes to the field of computational optimization by proposing a new application as well as a new algorithm to solve a quadratic version of a classical combinatorial optimization problem.

Keywords: team formation problem; quadratic set covering; branch and bound; reformulation (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.1000 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:3:p:1162-1176

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().