A branch-and-price approach to k-clustering minimum biclique completion problem

作者：Gualandi Stefano^*; Maffioli Francesco; Magni Claudio

来源：International Transactions in Operational Research, 2013, 20(1): 101-117.

DOI：10.1111/j.1475-3995.2012.00860.x

• biclique
• branch and price
• clustering
• local search

We consider the problem of finding k-bipartite subgraphs, called clusters, in a bipartite graph G=(S,T,E), such that each vertex i of S appears in exactly one of the subgraphs, every vertex j of T appears in each cluster in which at least one of its neighbors appears, and the total number of edges needed to complete each cluster (i.e. to become a biclique) is minimized. This problem has been shown to be strongly NP-hard and is known as the k-clustering minimum biclique completion problem. It has been applied to bundling channels for multicast transmissions. The application consists of finding k-multicast sessions that partition the set of demands, given a set of demands of services from clients. Each service should belong to a single multicast session, while each client can appear in more than one session. We extend previous work by developing a branch-and-price algorithm that embeds a new metaheuristic based on variable neighborhood infeasible search and a branching rule that exploits the problem structure. The metaheuristic can also efficiently solve the pricing subproblem. In addition to the random instances used in the literature, we present structured instances generated using the MovieLens dataset collected by the GroupLens Research Project. Extensive computational results show that our branch-and-price algorithm outperforms the approaches proposed in the literature.

• 出版日期2013-1