%\VignetteIndexEntry{sdpt3r}
% JSS Article Template
\documentclass{article}


%%% Additional Packages %%%

% Algorithms
% http://tex.stackexchange.com/questions/229355/algorithm-algorithmic-algorithmicx-algorithm2e-algpseudocode-confused
\usepackage{algorithm}% http://ctan.org/pkg/algorithms
\usepackage{algpseudocode}% http://ctan.org/pkg/algorithmicx


% Font stuff
\usepackage[T1]{fontenc}% for correct hyphenation and T1 encoding
%\usepackage{lmodern}% latin modern font
\usepackage[american]{babel}% for American English

% Math fonts/symbols
\usepackage{amsmath}% sophisticated mathematical formulas with amstex (includes \text{})
\usepackage{mathtools}% fix amsmath deficiencies
\usepackage{amssymb}% sophisticated mathematical symbols with amstex
\usepackage{amstext}% ams mathematical fonts
\usepackage{amsfonts}% ams mathematical fonts

% Figures
\usepackage{graphicx}% for including figures

%%% Commands %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% vetors
\newcommand{\ve}[1]{\mathbf{#1}}           % for vetors
\newcommand{\sv}[1]{\boldsymbol{#1}}   % for greek letters
\newcommand{\m}[1]{\mathbf{#1}}               % for matrices
\newcommand{\sm}[1]{\boldsymbol{#1}}   % for greek letters
\newcommand{\tr}[1]{{#1}^{\mkern-1.5mu\mathsf{T}}}              % for transpose
\newcommand{\norm}[1]{||{#1}||}              % for transpose
\newcommand*{\mve}{\operatorname{ve}}
\newcommand*{\trace}{\operatorname{trace}}
\newcommand*{\rank}{\operatorname{rank}}
\newcommand*{\diag}{\operatorname{diag}}
\newcommand*{\vspan}{\operatorname{span}}
\newcommand*{\rowsp}{\operatorname{rowsp}}
\newcommand*{\colsp}{\operatorname{colsp}}
\newcommand*{\svd}{\operatorname{svd}}
\newcommand*{\edm}{\operatorname{edm}}  % euclidean distance matrix (D * D)


% statistical
\newcommand{\widebar}[1]{\overline{#1}}  

% 
% operators
\newcommand{\Had}{\circ}
\DeclareMathOperator*{\lmin}{Minimize}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\arginf}{arg\,inf}
\DeclareMathOperator*{\argsup}{arg\,sup}
%\newcommand*{\arginf}{\operatorname*{arginf}}
%\newcommand*{\argsup}{\operatorname*{argsup}}

% Sets
\newcommand*{\intersect}{\cap}
\newcommand*{\union}{\cup}
\let\oldemptyset\emptyset
\let\emptyset\varnothing

% Fields, Reals, etc. etc
\newcommand{\field}[1]{\mathbb{#1}}
\newcommand{\Reals}{\field{R}}
\newcommand{\Integers}{\field{Z}}
\newcommand{\Naturals}{\field{N}}
\newcommand{\Complex}{\field{C}}
\newcommand{\Rationals}{\field{Q}}

% Hyphenation
\hyphenation{Ar-chi-me-dean}

% Editorial
\newcommand*{\TODO}[1]{\textcolor{red}{TODO: #1}}
\newcommand*{\NOTE}[1]{\textcolor{blue}{Note: #1}}
\newtheorem{theorem}{Theorem}
\newtheorem{Proof}{Proof}

\usepackage[total={6.5in,8.75in}, top=0.9in, left=0.7in, right=0.7in, includefoot]{geometry}


% Misc
%\makeatletter
%\newcommand\myisodate{\number\year-\ifcase\month\or 01\or 02\or 03\or 04\or 05\or 06\or 07\or 08\or 09\or 10\or 11\or 12\fi-\ifcase\day\or 01\or 02\or 03\or 04\or 05\or 06\or 07\or 08\or 09\or 10\or 11\or 12\or 13\or 14\or 15\or 16\or 17\or 18\or 19\or 20\or 21\or 22\or 23\or 24\or 25\or 26\or 27\or 28\or 29\or 30\or 31\fi}% create iso date
\makeatother
%\newcommand*{\abstractnoindent}{}% define abstract such that it has no indent
%\let\abstractnoindent\abstract
%\renewcommand*{\abstract}{\let\quotation\quote\let\endquotation\endquote
%  \abstractnoindent}
%\deffootnote[1em]{1em}{1em}{\textsuperscript{\thefootnotemark}}% setting for footnote

\author{Adam Rahman}
\title{The Graph Partitioning Problem}


%% need no \usepackage{Sweave.sty}

\begin{document}
\SweaveOpts{concordance=FALSE}

\maketitle

The graph partitioning problem can be formulated as the following primal optimization problem

\[
\begin{array}{ll}
\underset{\m{X}}{\text{minimize}} & tr(\m{C}\m{X}) \\
\text{subject to} & \\
 & \begin{array}{rl}
tr(\ve{1}\tr{\ve{1}}\m{X}) &=~~ \alpha \\
diag(\m{X}) &=~~ \ve{1}
\end{array}
\end{array}
\]

Here, $\m{C} = -(diag(\m{B}\ve{1}) - \m{B})$, for an adjacency matrix $\m{B}$, and $\alpha$ is any real number. 

The function \verb!gpp!, takes as input a weighted adjacency matrix \verb!B! and a real number \verb!alpha! and returns the input necessary to solve the problem using \verb!sqlp!.

\begin{verbatim}
R> out <- gpp(B,alpha)
R> blk <- out$blk
R> At <- out$At
R> C <- out$C
R> b <- out$b

R> sqlp(blk,At,C,b)
\end{verbatim}

\section*{Numerical Example}

To demonstrate the output provided by \verb!sqlp!, we make use of the following adjacency matrix

\begin{verbatim}
R> data(Bgpp)
R> Bgpp

      V1 V2 V3 V4 V5 V6 V7 V8 V9 V10
 [1,]  0  0  0  1  0  0  1  1  0   0
 [2,]  0  0  0  1  0  0  1  0  1   1
 [3,]  0  0  0  0  0  0  0  1  0   0
 [4,]  1  1  0  0  0  0  0  1  0   1
 [5,]  0  0  0  0  0  0  1  1  1   1
 [6,]  0  0  0  0  0  0  0  0  1   0
 [7,]  1  1  0  0  1  0  0  1  1   1
 [8,]  1  0  1  1  1  0  1  0  0   0
 [9,]  0  1  0  0  1  1  1  0  0   1
[10,]  0  1  0  1  1  0  1  0  1   0
\end{verbatim}

Any value of $\alpha$ in $(0,n^{2})$ can be chosen, so without loss of generality, we choose a value of $n$ to solve the problem.

\begin{verbatim}
alpha <- nrow(Bgpp)

out <- gpp(Bgpp, alpha)
blk <- out$blk
At <- out$At
C <- out$C
b <- out$b

out <- sqlp(blk,At,C,b)
\end{verbatim}

As with the max-cut problem, the output of interest here is the primal objective function, keeping in mind that we have swapped the sign of the objective function so that the primal problem is a minimization.

\begin{verbatim}
out$pobj

[1] -57.20785
\end{verbatim}

Also like the maxcut problem, the set of feasible solutions are correlation matrices

\begin{verbatim}
out$X[[1]]     #Rounded to 3 decimal places
      [,1]   [,2]   [,3]   [,4]   [,5]   [,6]   [,7]   [,8]   [,9]  [,10]
V1   1.000  1.000  0.550 -0.604  0.702  0.895 -0.611  0.006 -0.920  0.741
V2   1.000  1.000  0.572 -0.583  0.721  0.907 -0.590 -0.020 -0.930  0.723
V3   0.550  0.572  1.000  0.333  0.981  0.865  0.325 -0.832 -0.834 -0.153
V4  -0.604 -0.583  0.333  1.000  0.143 -0.186  1.000 -0.800  0.243 -0.983
V5   0.702  0.721  0.981  0.143  1.000  0.946  0.135 -0.708 -0.926  0.043
V6   0.895  0.907  0.865 -0.186  0.946  1.000 -0.194 -0.440 -0.998  0.365
V7  -0.611 -0.590  0.325  1.000  0.135 -0.194  1.000 -0.796  0.251 -0.984
V8   0.006 -0.020 -0.832 -0.800 -0.708 -0.440 -0.796  1.000  0.387  0.676
V9  -0.920 -0.930 -0.834  0.243 -0.926 -0.998  0.251  0.387  1.000 -0.418
V10  0.741  0.723 -0.153 -0.983  0.043  0.365 -0.984  0.676 -0.418  1.000
\end{verbatim}

\end{document}