We consider the k-Clustering Minimum Biclique Completion Problem (k-MinBCP), which has been shown strongly NP-hard. Given a bipartite graph G = (S, T, E), the objective is to find k bipartite subgraphs, called “clusters”, while minimizing the total number of edges needed to make each cluster complete (i.e. to become a biclique), such that each vertex i of S appears in exactly one cluster and every vertex j of T appears in each cluster in which at least one of its neighbors appears.
It has applications in telecommunications and, in particular, in bundling channels for multicast transmissions. We analyze several Integer Programming formulations and implement a Branch-and-Price algorithm, which features a non-trivial branching rule and takes advantage of a new metaheuristic based on Variable Neighborhood Unfeasible Search (VNUS). Computational results show that this approach outperforms other state of the art methods found in the literature, allowing to exactly solve larger instances of k-MinBCP.