Optimization Online


A Branch-and-Price Approach to the k-Clustering Minimum Biclique Completion Problem

Stefano Gualandi (stefano.gualandi***at***unipv.it)
Francesco Maffioli (maffioli***at***elet.polimi.it)
Claudio Magni (magni***at***mpi-inf.mpg.de)

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 k-clustering Minimum Biclique Completion Problem and has been shown strongly NP-hard. 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 non-trivial 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 Branch-and-Price Approach to the k-Clustering Minimum Biclique Completion Problem. International Transactions in Operational Research, 2012, Forthcoming.

Download: [PDF]

Entry Submitted: 12/09/2010
Entry Accepted: 12/09/2010
Entry Last Modified: 09/14/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society