% 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{amssymb}
\usepackage{array}
%\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{graphicx}
%\usepackage{setspace}

\begin{document}
\setcounter{page}{37}
\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{Optimization algorithms for the Max Edge Weighted Clique problem with Multiple Choice constraints}
% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author[DTI]{Alberto Ceselli \corauthref{corAC}}
\author[DTI]{Roberto Cordone}
\author[DTI]{Yari Melzani}
\author[DTI]{Giovanni Righini}
\address[DTI]
{Dipartimento di Tecnologie dell'Informazione, Universit\`a degli Studi di Milano\\
\texttt{\{alberto.ceselli,roberto.cordone,giovanni.righini\}@unimi.it, yari.melzani@gmail.com}
}
\corauth[corAC]{Corresponding author}
\begin{keyword}
Max Clique \sep semidefinite programming \sep tabu search \sep branch-and-bound % keywords here, in the form: keyword \sep keyword
\end{keyword}
\end{frontmatter}
\vspace{-1.2cm}
% main text
\section{Introduction}
\vspace{-0.5cm}
\label{sect:intro}
Many relevant problems can be described and successfully solved using graph-based models.
For instance, the side-chain placement problem in biology, the choice of efficient communication protocols in management science, backbone design 
in telecommunication networks and data mining applications share a common structure: they all require to find a maximum weighted clique in a suitable graph \cite{Yari}.\\
We tackle the \emph{Max Edge Weighted Clique problem with Multiple choice Constraints }(MEWCMC). Given a graph
with weights on both vertices and edges, and a partition of the vertex set, the MEWCMC asks to find a maximum weight clique,
choosing one vertex for each class of the partition.\\
%Despite its theoretical simplicity, the MEWCMC models many real-life problems in data mining, management, telecommunication networks design and computational biology \cite{MEWCP_Glover_data_mining} \cite{protein_side_chain}.
The classical Max Weighted Clique problem has been studied from many aspects. State of the art algorithms include \cite{MEWCP_recent1}, \cite{MEWCP_recent2} and \cite{MEWCP_recent3}.
The version of the problem involving multiple choice constraints, instead, has been tackled only recently \cite{Bosio}.\\
In this paper we first introduce models for the MEWCMC based on Binary Quadratic Programming (BQP) and Integer Linear Programming (ILP); we also introduce a model suitable to obtain a semidefinite relaxation of the MEWCMC.
Since using commercial solvers on these models allows to solve only small size instances, we present an exact algorithm exploiting a semidefinite relaxation of the MEWCMC, combinatorial bounding, rounding and problem reduction procedures in a branch-and-bound framework.
We also describe a Tabu Search heuristic, able to quickly find good quality solutions.
 
%\vspace{-1cm}
\section{Models}
%\vspace{-1cm}
It is given a graph $G(V,E)$, where $V$ is a set of $n$ vertices and $E\subseteq V\times V$ is a set of $\ell$ edges.
It is also given a partition $K=\{V_{1},V_{2},..,V_{m}\}$ of $V$.
Let $w_{E}:E\rightarrow\mathbb{R}$ and $w_{V}:V\rightarrow\mathbb{R}$ be two functions mapping respectively every edge and every vertex to a weight value.
The MEWCMC consists in finding a clique in $G$, that is finding a set of vertices $M \subseteq V$, such that 
$(i,j)\in E\,\,\,\forall i,j\in M$, having maximum weight $z(M)=\frac{1}{2}\sum_{v_{i}\in M}\sum_{v_{j}\in M}w_{ij}$.
Furthermore, in order to fulfill multiple choice constraints, $M$ has to include exactly $1$ vertex for each class, that is $|M\cap V_{k}|=1\,\forall V_{k}\in K$.\\
%
By introducing a binary variable $x_i$ for each vertex $i \in V$, such that $x_i$ takes value $1$ if vertex $i \in M$, $0$ otherwise, we can formulate the MEWCMC
as the following BQP problem:
%\vspace{-0.2cm}
%\begin{flushleft}
\begin{alignat}{2}
\text{maximize } &\sum_{i\in V}\sum_{j\in V}w_{ij}x_{i}x_{j}\label{eq:quadratic_z}\\
\text{s.t. } & \sum_{i\in V_{k}}x_{i}=1 & \forall k\in K\label{eq:quadratic_MC}\\
 & x_{i}\in\{0,1\} & \forall i\in V.\label{eq:quadratic_integrality}\end{alignat}
%\vspace{-0.2cm}
%
%\par\end{flushleft}
Multiple choice constraints (\ref{eq:quadratic_MC}) impose that exactly one vertex is selected for each class $V_{k}\in K$.
This model can be either directly used by general purpose BQP solvers, or linearized using
standard techniques, obtaining an ILP problem, suitable to be optimized by standard solvers. Both approaches, however, show
to fail as the size of instances increases, mainly due to the poor quality of the continuous relaxation of both models.\\
%
Hence, %following \cite{SDP_maxcut_Goemans95improvedapproximation}, 
we derive a matrix-based formulation of the problem as follows.
First we define a matrix $W$, where each element $w_{ij}$ with $i \neq j$ is the weight associated to edge $(i,j) \in E$ and each element $w_{ii}$ is the weight associated to vertex $i \in V$, and we
introduce a square matrix $Y$ of variables $y_{ij}$ of dimension $n$, where $y_{ij}=x_{i}x_{j}$ for
each $i,j\in V$. %Since variables are binary, matrix $Y$ can be obtained as $xx^T$, by exploiting the relation $x_i^2 = x_i$.
The MEWCMC can then be stated as follows:
%\vspace{-0.2cm}
\begin{alignat}{2}
 \text{maximize }  &  W\bullet Y\label{eq:sdp_z}\\
\text{s.t. } &   \text{rank}(Y)=1\label{eq:sdp_rango_X_1}\\
   & \sum_{k}S_{k}\bullet Y=1\,\,\,\,\, k=1,...,m\label{eq:sdp_smc}\\
   & Y\succeq0\label{eq:sdp_X_semidefinita}\\
   & y_{ij}\in\{0,1\}\label{eq:sdp_integralita_X}\end{alignat}
%\vspace{-0.2cm}
where $\bullet$ is the \emph{Frobenius} matrix product,
$rank(Y)$ is the rank of matrix $Y$, $Y\succeq0$ imposes
$Y$ to be positive semidefinite, $I$ is the identity matrix of dimension $n$.
Constraints (\ref{eq:sdp_rango_X_1}) and (\ref{eq:sdp_X_semidefinita})
guarantee that matrix $Y$ can be represented as the product $xx^{T}$,
and constraints (\ref{eq:sdp_integralita_X}) guarantee that each value in the matrix is binary.
Inequalities (\ref{eq:sdp_smc}) represent multiple choice constraints: matrices $S_k$ are built in such a way that
\[
\sum_{i\in V_{k}}Y_{ii}=\sum_{i\in V}\sum_{j\in V}(S_{k})_{ij}Y_{ij}=S_{k}\bullet Y=1\,\,\,\,\,\forall V_{k}\in K,\]
that is, having value $1$ only on some diagonal elements, and value $0$ elsewhere.
\vspace{-1.2cm}
\section{Algorithms}
\vspace{-0.7cm}
We devised an exact branch-and-bound algorithm
exploiting formulation (\ref{eq:sdp_z})--(\ref{eq:sdp_integralita_X}) and combinatorial arguments. 
In the remainder we sketch its main components.\\
{\bf Dual bounds.} By considering model (\ref{eq:sdp_z})--(\ref{eq:sdp_integralita_X}) and relaxing constraints (\ref{eq:sdp_rango_X_1}) and (\ref{eq:sdp_integralita_X}) we obtain a semidefinite programming problem; this is a special case of convex optimization problem, that can be solved very efficiently by special purpose algorithms \cite{SDP_IP}. %The value obtained in this way is an upper bound on the value of the optimal solution, and is used to prune nodes of the branching tree.
The relaxed model obtained in this way is strengthened in two ways. First, since one vertex has to be selected from each class of the partition, 
$m$ vertices have to be selected overall; therefore, the constraint $I\bullet Y=m$ can be added to the formulation.
%\begin{equation}
%I\bullet Y=m\label{eq:sdp_cardinalita}
%\end{equation}
Second, we state constraints %(\ref{eq:sdp_smc}) and (\ref{eq:sdp_cardinalita}) 
in stronger forms, by disaggregating and exploiting some properties of BQP problems.
At the same time, we consider the following value
\begin{equation}
DB_{c}=\frac{1}{2}\sum_{V_{s}\in K}\max_{i\in V_{s}}\{w_{ii}+\sum_{V_{t}\in K,t\neq s}\max_{j\in V_{t}}\{\frac{w_{jj}}{m-1}+w_{ij}\}\}\label{eq:bound_duale_combinatorio};
\end{equation}
and we prove by combinatorial arguments that expression (\ref{eq:bound_duale_combinatorio}) gives a valid dual bound to the MEWCMC.
The best of the two bounds is kept as the final dual bound.\\
%
{\bf Primal bounds. } %Tabu search and rounding heuristics.} 
At each node of the branch-and-bound tree we try to find good feasible solutions by (a) rounding the optimal solution of the semidefinite relaxation (b) correcting the solutions given by the combinatorial bounding procedure (\ref{eq:bound_duale_combinatorio}). Both methods are able to find good solutions in the early nodes of the branch-and-bound tree.
%
We also devised a Tabu Search heuristic; it works as follows. We start from a clique $M$ either corresponding to a known feasible solution or obtained by selecting a random vertex for each class of the partition $K$; at each step we explore the neighborhood given by all solutions obtained by replacing one the vertices in $M$ by a different vertex of the same class, moving to the best solution in the neighborhood. We keep two tabu lists: the first keeps track of vertices recently removed from $M$, that cannot be selected again; the second keeps track of vertices recently introduced in $M$, that cannot be removed. We stop after a fixed number of steps. Preliminary experiments shows that by setting the length of the first tabu list to $8$, that of the second tabu list to $1$ and the maximum number of steps to $1000$, this heuristic is able to produce optimal solutions on a large set of instances; besides being useful on its own, this heuristic is used to obtain tight primal bounds at the root node of the branching tree.\\
%
{\bf Branching.} 
The diagonal elements of $Y$ basically represent how much any vertex is (fractionally) selected in the semidefinite relaxation solution.
Therefore, when primal and dual bounds do not match, we perform binary branching by selecting the class $V_k$ having the highest number of these fractional entries;
then we try to partition the vertices of class $V_k$ in two subsets $V_k^l$ and $V_k^r$, having the most balanced sum of fractional entries. In the left branch and right branches we respectively forbid to choose in the clique any vertex of the set $V_k^l$, and any vertex of the set $V_k^r$. 
%These branching decisions can be enforced easily in all the above procedures; computing the semidefinite relaxations in the children nodes gets easier and easier, as rows and columns corresponding to forbidden vertices can be deleted from the matrix $Y$. 
We visit the branching tree in a best bound order.\\
%
{\bf Performance improving techniques.}
We improved the performances of our algorithm by (a) switching to complete enumeration when, due to the remotion of forbidden vertices, the size of the subproblem gets small enough (b) performing problem reduction tests, that is trying to fix each vertex to be part of the solution, computing the combinatorial dual bound on the remaining subproblem and removing from the problem such a vertex if the dual bound computed in this way is worse than the best known primal bound.
\vspace{-0.7cm}

\section{Experimental results}
\vspace{-0.7cm}
We implemented our algorithms in C, we used ILOG CPLEX 11.2 as both ILP and BQP solver, and DSDP5 as semidefinite programming solver. We performed experiments on two datasets. Dataset S1 is drawn from \cite{Bosio}; it is composed by $168$ instances of four types, having weights on vertices and edges randomly drawn in different ranges. These instances require the optimization on graphs with up to $65$ vertices. %, partitioned in a number of classes ranging from $2$ to $5$; classes have equal size. 
Dataset S2, instead, consists of $165$ new instances of three types.%, 
%still having weights on vertices and edges randomly drawn in different ranges. 
The number of vertices of the graphs in these instances range from $30$ to $300$.
%, partitioned in a number of classes between $3$ and $150$. 
Our experiments ran on a Centrino Core 2 3GHz PC, equipped with 2GB of RAM, in Linux 32 bit environment.
A full description of Datasets and computational experiments is available online \footnote{http://www.dti.unimi.it/$\sim$ceselli/EWCMC.html}.\\
%
%We first performed a parameter fine tuning round, that also highlighted 
%As a first result, we could identify which types of instances are harder to solve, whi.
%
Our experimental campaign allowed us to find that (a) the tabu search algorithm is able to find the optimal solution on 79.76\% of the instances in Dataset S1, and on 88.48\% of the instances in Dataset S2; (b) the BQP solver of CPLEX using formulation (\ref{eq:quadratic_z})--(\ref{eq:quadratic_integrality}) is not competitive with other methods (c) the exact algorithm proposed in \cite{Bosio} is outperformed by both CPLEX and our algorithm on both datasets (d) using the best of our ILP formulations, CPLEX could solve only 44\% of the instances in Dataset S2 within a time limit of one hour, while our exact algorithm solved 77\% of them; when both CPLEX and our algorithm terminate within the time limit, our algorithm is up to three orders of magnitude faster, and when none of them terminates, the remaining gap between primal and dual bounds for our algorithm is a fraction of that of CPLEX. 
%
% The Appendices part is started with the command \appendix;
% appendix sections are then done as normal sections
% \appendix
%
% \section{}
% \label{}
%
\begin{thebibliography}{00}
%
%\bibitem{CPLEX}
%
\bibitem{Yari}
Y. Melzani (2009) ``Mathematical programming algorithms for the Max edge weighted clique problem with multiple choice constraints'',
Master thesis, Dipartimento di Tecnologie dell'Informazione, Universit{\`a} degli Studi di Milano.

\bibitem{Bosio}
A. Bosio (2005) ``A mathematical programming algorithm for the Max edge weighted clique problem with multiple choice constraints'',
Degree thesis, Dipartimento di Tecnologie dell'Informazione, Universit{\`a} degli Studi di Milano.

%\bibitem{DSDP5}
%\bibitem{MEWCP_Glover_origini}
%F. Glover, G. Hersh, C. McMillan (1977) ``Selecting subsets of maximum diversity'', MS/IS. Report No. 77-9, University of Colorado at Boulder.

\bibitem{MEWCP_recent1}
B. Alidaee, F. Glover, G. Kochenberger, H. Wang (2007) ``Solving the maximum edge weight clique problem via unconstrained quadratic programming'',
European Journal of Operational Research, 181(1): 592--597.

\bibitem{MEWCP_recent2}
M. M. S{\o}rensen (2004) ``New facets and a branch-and-cut algorithm for the weighted clique problem'',
European Journal of Operational Research, 154(1): 57--70.

\bibitem{MEWCP_recent3}
M. Hunting, U. Faigle, W. Kern (2001) ``A Lagrangian Relaxation Approach to the Edge-Weighted Clique Problem'',
European Journal of Operational Research, 131

%\bibitem{SDP_in_CO}
%M. X. Goemans (1997) ``Semidefinite programming in combinatorial optimization'',
%Mathematical Programming, 79(1): 143--161

\bibitem{SDP_IP}
S. J. Benson, Y. Ye (2005) ``DSDP5: Software for Semidefinite Programming'',
Technical report, Mathematics and Computer Science Division, Argonne National Laboratory.

% \bibitem{label}
% Text of bibliographic item

% notes:
% \bibitem{label} \note

% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}

\end{thebibliography}

\end{document}

