  


A BranchandPrice Approach to the kClustering Minimum Biclique Completion Problem
Stefano Gualandi (stefano.gualandiunipv.it) Abstract: Given a bipartite graph G = (S , T , E ), we consider the problem of finding k bipartite subgraphs, called clusters, such that each vertex i of S appears in exactly one of them, 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 make each cluster complete (i.e., to become a biclique) is minimized. This problem is known as kclustering Minimum Biclique Completion Problem and has been shown strongly NPhard. It has applications in bundling channels for multicast transmissions. Given a set of demands of services from clients, the application consists of finding k multicast sessions that partition the set of demands. Each service has to belong to a single multicast session, while each client can appear in more sessions. We extend previous work by developing a Branch and Price algorithm that embeds a new metaheuristic based on Variable Neighborhood Infeasible Search and a nontrivial branching rule. The metaheuristic is also adapted to solve efficiently the pricing subproblem. In addition to the random instances used in the literature, we present structured instances generated using the MovieLens data set collected by the GroupLens Research Project. Extensive computational results show that our Branch and Price algorithm outperforms the approaches proposed in the literature. Keywords: Biclique, Branch and Price, Clustering, Local Search Category 1: Applications  OR and Management Sciences Category 2: Combinatorial Optimization (Graphs and Matroids ) Category 3: Integer Programming (Other ) Citation: S. Gualandi, F. Maffioli, C. Magni. A BranchandPrice Approach to the kClustering Minimum Biclique Completion Problem. International Transactions in Operational Research, 2012, Forthcoming. Download: [PDF] Entry Submitted: 12/09/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  