Given a simple graph G = (V, E) with vertex set V and edge set E, the minimum biclique cover problem seeks to cover all edges of the graph with a minimum number of bicliques (i.e., complete bipartite subgraphs). This paper proposes two compact mixed integer programming (MIP) formulations for solving the minimum biclique cover problem on general graphs: (i) a natural formulation in the edge space and (ii) an extended formulation in the edge and vertex spaces. Despite the exponential-size natural MIP formulation of Cornaz and Fonlupt (Discrete Mathematics, 2006), our natural formulation employs only a polysize number of their exponential “no-good” cuts, along with another set of polysize valid inequalities. We also employ bounding and variable fixing procedures that help solve most of our social network instances, which are not solvable to optimality in a one-hour time limit without the bounding and fixing procedures.
Article
View Compact Mixed Integer Programming Formulations for the Minimum Biclique Cover Problem