% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{url}

\newcommand{\myp}{{\sc $k$-MinBCP}}
\newcommand\tablesize{\small}
\newcommand\bad[1]{{\it #1}}
\newcommand\good[1]{{\bf #1}}
\newcommand{\reff}[1]{(\ref{#1})}


\begin{document}

\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{A Branch-and-Price Approach to the $k$-Clustering Minimum Biclique Completion Problem}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author[dei]{Stefano Gualandi\corauthref{cor1}}
\author[dei]{Francesco Maffioli}
\author[sas]{Claudio Magni}

\address[dei]{Politecnico di Milano,
   Dipartimento di Elettronica e Informazione \\
   Piazza Leonardo da Vinci 32, 20133 Milano, Italy}
 \ead{\{maffioli,gualandi\}@elet.polimi.it}

\address[sas]{SAS Institute, Analytic Innovation Center \\ via Darwin 20-22, 20143, Milano}
\ead{claudio.magni@ita.sas.com}

\corauth[cor1]{Corresponding author.}

\begin{keyword}
Biclique \sep Branch-and-Price \sep Meta-heuristic
% keywords here, in the form: keyword \sep keyword
\end{keyword}

\end{frontmatter}

% main text
\section {Introduction}
\label{}

Given a bipartite graph $G=(S,T,E)$, the $k$-clustering Minimum Biclique Completion Problem (\myp) consists of finding $k$ bipartite subgraphs (clusters), such that each vertex $i$ of $S$ appears in exactly one subgraph, every vertex $j$ in $T$ appears in each cluster in which at least one of its neighbors appears, and the total number of edges that would complete each subgraph into a complete bipartite subgraph, i.e., a biclique, is minimized. This problem was introduced in \cite{Faure2007}, as an application of the problem of bundling channels in multicast transmissions. \myp{} is NP-Hard, and its approximability, to the best of our knowledge, remains unknown. In the literature, \myp{ } is tackled with two approaches: in \cite{Faure2007}, it is solved with an Integer Programming approach, a Bilinear Programming formulation and its standard linearization; and in \cite{Gualandi2009}, it is solved with an hybrid Constraint Programming--Semidefinite programming approach. 

In this work, we present a Branch-and-Price algorithm that embeds a new meta-heuristic to find integer solutions, and a non-trivial branching rule. 
Computational results show that our algorithm outpeforms the state-of-the-art approaches to this problem.

\section {Problem Formulation}
In this work, we use a Column Generation formulation that is similar to the one proposed in \cite{Faure2007}: the master problem is a set partitioning problem where each column represents the subset of vertices of $S$ that induces a cluster $t$. The cost $c_t$ of each cluster $t$ is equal to the number of edges that would complete the corresponding subgraph into a biclique. Let $\lambda_t$ be a 0--1 variable, equal to 1 if the cluster $t$ is part of the solution, and 0 otherwise. Let $c_t$ be the cost of the $t$-th cluster. Let $\mathcal T$ be the collection of every possible cluster, and let $S_t$ be the subset of vertices of $S$ that form the $t$-th cluster. The master problem formulation is as follows:
\begin{align}
\min \quad & \sum_{t \in \mathcal{T} } c_t \lambda_t & \\
\label{c1:part}\mathrm{s.t.} \quad & \sum_{t \in \mathcal{T} \mid i \in S_t} \lambda_t = 1 & \forall \: i \in S \\
\label{c2:card} & \sum_{t \in \mathcal{T}} \lambda_t = k & \\
 & \lambda_t \in \{0, 1\} & \forall \: t \in \mathcal{T}
\end{align}
Constraints \reff{c1:part} is the partitioning constraints, one for each vertex in $S$. Constraint \reff{c2:card} is the cardinality constraint on the number of cluster to be selected. Let $\pi_i$ and $\nu$ be the dual multipliers of constraints \reff{c1:part} and \reff{c2:card}, respectively. Then, the pricing subproblem is the problem of finding a vertex-- and edge--weighted biclique of negative reduced cost. The vertex weights are given by the dual multipliers $\pi_i$, while the edge weights gives the number of edges that would complete the subgraph into a biclique. The pricing subproblem is as follows:
\begin{align}
\min \quad & \sum_{\{i,j\} \in \bar{E}} z_{ij} - \sum_{i \in I} \pi_ix_i - \nu \\
\label{c3:imply}\mathrm{s.t.} \quad & z_{ij} \geq x_i + x_l - 1 \quad \forall \{i,j\} \in \bar{E}, \, \forall \{l,j\} \in E \\
  & x_i, z_{ij} \in \{0,1\} \qquad \forall i \in I, \, \forall \{i,j\} \in \bar{E}
\end{align}
Constraints \reff{c3:imply} force the binary variable $z_{ij}$ to be 1 if the corresponding edge is part of the biclique, and 0 otherwise. Note that an edge belongs to a biclique if it exists at least a pair of vertices $i$ and $l$ both in $S$ such that a vertex $j \in T$ exists with $(i,j) \in \bar E$ and $(l,j) \in E$. 

\section {Branch-and-Price Implementation}
Differently from \cite{Faure2007}, that uses the column generation only to compute lower bounds, we have embedded the column generation into a branch-and-price exact algorithm. The branch-and-price we have implemented is based on three key feature: (i) a Variable Neighborhood Search (VNS) heuristic that computes very efficient primal solution, providing tight upper bounds; (ii) a slightly different VNS heuristic that compute nearly-optimal solutions for the pricing subproblem, and (iii) a non-trivial branching rule.

The VNS heuristic used to find integer solutions, hence yielding upper bounds, explores basically three different neighborhoods: (i) moving a single vertex from one subgraph to another subgraph, (ii) swapping two vertices in two different subgraphs, and (iii) selecting two vertices in two different subgraphs and moving them into new subgraphs. In addition, after each cycle of VNS, we perform a search in the space of the unfeasible solutions, by augmenting by one the number of clusters. Then, a greedy procedure is used to recover a feasible solution. Although the search in the unfeasible space is very simple, it does improve the performance of our meta-heuristic.

In our Column Generation approach to \myp{} the bottleneck is the solution of the pricing subproblem. We have implemented two methods for solving the pricing problem. The first method is again a VNS heuristic very similar to the heuristic used to find integer solutions to \myp{}: we basically look for a single subgraph with negative reduced cost. Whenever the heuristic is unable to find a negative reduced cost solution, we use an integer programming approach to find any solution of negative reduced cost, not necessarily the solution of minimum cost.

The meta-heuristic and the Column Generation are used to obtain upper and lower bounds within our branch-and-price algorithm. Though many instances are solved at the root node (the upper bounds obtained with our VNS heuristic are equal to the lower bounds obtained by Column Generation), this is not always the case. Therefore, we have devised a branching rule that exploits the problem structure. Once a pair of vertices $i$ and $j$ of $S$ appearing in a fractional solution of the restricted master problem are selected, the algorithm adds two branching constraints: either $i$ and $j$ must appear in the same cluster, or they cannot. In the first branch, we merge the two nodes in a single new node, obtaining a new instance of the same problem. In the second branch, in order to force two vertices to appear in different clusters, we add the corresponding constraints to the pricing subproblem. 

\section {Computational Results}
We tested our branch-and-price algorithm on two classes of instances: the first set of instances consists of random bipartite graphs, and the second set of instances extracted by the MovieLens data set (\url{http://movielens.umn.edu}). The branch-and-price algorithm is implemented in {\sc Comet} \cite{Comet}, using {\tt lp\_solve} as linear solver. Extensive computational results are reported in \cite{Magni2009}. 

Table \ref{t1} shows a summary of the comparison of the computational results obtained with our branch-and-price algorithm and with the ILP solver SCIP. The table gives the results for the most challenging instances, that are instances randomly generated with $|S|=|T|$. The first three columns give the $|S|$, $|T|$, and the number of required cluster $k$. Then, the table reports the {\bf UB} obtained with our VNS heuristic at the root node, the lower bound {\bf LB} obtained via column generation at the root node, the optimal solution {\bf Opt} obtained via Branch-and-Price, the number of branching nodes {\bf N}, and the computation time in seconds. For the SCIP solver, we just report the computation time in seconds. Note that our branch-and-price algorithm is able to solve instances of dimension up to $20 \times 20$. In addition, we remark that previous work solved only instances up to $10 \times 10$ in \cite{Faure2007} and  $12 \times 12$ in \cite{Gualandi2009}.

%The computational results shows that our branch-and-price algorithm outperforms the current state-of-the-art. On the most challenging instances, the approach in \cite{Faure2007} was able to solve random bipartite graphs of dimension up to $10 \times 10$ (i.e., $|S|=|T|=10)$,  and the approach in \cite{Gualandi2009} up to $12 \times 12$. With our approach we are able to solve to optimality random bipartite graphs of dimension up to $20 \times 20$.

\begin{table}
  \caption{ \label{t1}} 
  \centering
  \begin{tabular}{|lll|llll|l|l|}
    \hline 
    $|$\textbf{I}$|$ & $|$\textbf{J}$|$ & \textbf{k} & 
    \textbf{UB} & \textbf{LB} & \textbf{Opt} & \textbf{N} &
    \textbf{Time} & \textbf{SCIP}\\
    \hline
    15 & 15 & 3 & \textbf{72} & \textbf{72} & \textbf{72} & 0 & \good{6.38}s & 11s \\
    15 & 15 & 4 & \textbf{59} & \textbf{59} & \textbf{59} & 0 & \good{2.92}s & 370s \\
    15 & 15 & 5 & \textbf{50} & \textbf{50} & \textbf{50} & 0 & \good{4.14}s & \bad{--} \\
    \hline
    18 & 18 & 3 & \textbf{109} & \textbf{109} & \textbf{109} & 0 & \good{26}s & 137s \\
    18 & 18 & 4 & \textbf{96} & \textbf{96} & \textbf{96} & 0 & \good{20}s & \bad{--} \\
    18 & 18 & 5 & \textbf{86} & 85 & \textbf{86} & 8 & \good{47}s & \bad{--} \\
    \hline
    20 & 20 & 3 & \textbf{156} & 154 & \textbf{156} & 12 & \good{275}s & \bad{--} \\
    20 & 20 & 4 & \bad{139} & 137 & \textbf{138} & 8 & \good{206}s & \bad{--} \\
    20 & 20 & 5 & \textbf{123} & 121 & \textbf{123} & 38 & \good{175}s & \bad{--} \\
    \hline
  \end{tabular}
\end{table}


\begin{thebibliography}{00}

\bibitem{Faure2007} Faure, N., Chr{\'e}tienne, P., Gourdin, E., Sourd, F.: \newblock {Biclique completion problems for multicast network design}. \newblock Discr. Optim. \textbf{4}(3) (2007)  360--377 

\bibitem{Gualandi2009} Stefano Gualandi. \newblock k-clustering minimum biclique completion via a hybrid {CP} and {SDP}   approach. \newblock In {\em Proc Integration of {AI} and {OR} Techniques in {CP} for   Combinatorial Optimization}, LNCS 5547, pages 87--101. Springer, 2009. 

\bibitem{Magni2009} Claudio Magni. \newblock Biclique completion problem: models and algorithms. \newblock Master Project, Politecnico di Milano, September 2009. 

\bibitem{Comet}
Comet web site, Brown University,
\newblock {\url{http://comet-online.org}}

\end{thebibliography}

\end{document}

