%\documentstyle[11pt]{article}
\documentclass{article}
\usepackage{latexsym}
\usepackage{amsfonts}
%\usepackage{epsfig}
\input epsf
\newtheorem{defi}{Definition}[section]
\newtheorem{example}{Example}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{lem}{Lemma}[section]
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}{Corollary}[section]
\newtheorem{rem}{Remark}[section]
\newtheorem{conj}{Conjecture}[section]
\newtheorem{alg}{Algorithm}[section]
\newtheorem{ex}{Exercise}[section]
\newcounter{count}
\newcommand{\bodiag}{{\rm b^0diag\,}}
\newcommand{\oodiag}{{\rm o^0diag\,}}
\newcommand{\assign}{{\rm assign\,}}
\newcommand{\BoDiag}{{\rm B^0Diag\,}}
\newcommand{\OoDiag}{{\rm O^0Diag\,}}
\newcommand{\trian}{{\rm trian\,}}
\newcommand{\Trian}{{\rm Trian\,}}
\newcommand{\bo}{{\rm b^0\,}}
\newcommand{\oo}{{\rm o^0\,}}
\newcommand{\Bo}{{\rm B^0\,}}
\newcommand{\Oo}{{\rm O^0\,}}
\newcommand{\ar}{{\rm ar\,}}
\newcommand{\Ar}{{\rm Ar\,}}
\newcommand{\tR}{{\rm tr\,}}
\newcommand{\TR}{{\rm Tr\,}}
\newcommand{\conv}{{\rm conv\,}}
\newcommand{\rint}{{\rm relint\,}}
\newcommand{\SRN}{{\Re^{\frac{n\times n}{2}}}}
\newcommand{\Reals}{{\mathbb R}}
%\newcommand{\mathcal}{\cal}
\newcommand{\sn}{{\mathcal S}_n}
\newcommand{\p}{{\mathcal P}}
\newcommand{\rr}{{\mathcal R}}
\newcommand{\n}{{\mathcal N}}
\newcommand{\q}{{\mathcal Q}}
\newcommand{\f}{{\mathcal F}}
\newcommand{\rank}{{\rm rank\,}}
\newcommand{\tr}{{\rm trace\,}}
\newcommand{\kvec}{{\rm vec\,}}
\newcommand{\kmat}{{\rm Mat\,}}
\newcommand{\arrow}{{\rm arrow\,}}
\newcommand{\Arrow}{{\rm Arrow\,}}
\newcommand{\relint}{{\rm relint\,}}
\newcommand{\lbr}{\left\langle}
\newcommand{\rbr}{\right\rangle}
\newcommand{\opA}{{\mathcal A}}
\newcommand{\opAt}{{\mathcal A}^*}
\newcommand{\opB}{{\mathcal B}}
\newcommand{\opBt}{{\mathcal B}^*}
\newcommand{\adj}{{\rm adj\,}}
\newcommand{\trace}{{\rm trace\,}}
\newcommand{\spanl}{{\rm span\,}}
\newcommand{\dom}{{\rm dom\,}}
\newcommand{\diag}{{\rm diag\,}}
\newcommand{\Diag}{{\rm Diag\,}}
\newcommand{\Nu}{{\cal N\,}}
\newcommand{\Ra}{{\cal R\,}}
\renewcommand{\theequation}{\thesection.\thecount}
\newcommand{\beq}{\addtocounter{count}{1} \begin{equation}}
\newcommand{\beqr}{\addtocounter{count}{1} \begin{eqnarray}}
\newcommand{\addc}{\addtocounter{count}{1} }
\newcommand{\bs}{\setcounter{count}{0} \section}
\newcommand{\fa}{~ \; \forall}
\newcommand{\req}[1]{(\ref{#1})}
\newcommand{\bpr}{{\bf Proof.} \hspace{1 em}}
\newcommand{\epr}{\\ \hspace*{4.5in}  $\Box$}
%   for Real number sign
\newcommand\C{\mathbb C}
%\newcommand\R{{\Re}}
\newcommand\R{{\mathbb R}}
%\newcommand\Z{\mathbb Z}
%\newcommand\Prj{\mathbb P}
\begin{document}
\bibliographystyle{plain}
\title{
Semidefinite Programming and Discrete Optimization:
A Survey
}
             \author{
  Abdo Alfakih
\and
      Panos Pardalos
    \thanks{E-mail pardalos@math.ufl.edu}
\and
Franz Rendl
                \thanks{Technische  Universit\"{a}t Graz,
Institut f\"{u}r Mathematik,
Kopernikusgasse 24, A-8010 Graz, Austria.
Research support by Christian Doppler
                        Laboratorium f\"{u}r Diskrete Optimierung
     (rendl@fmatbds01.tu-graz.ac.at).}
\and
          Henry Wolkowicz
    \thanks{Research supported by Natural Sciences Engineering Research
     Council Canada. E-mail henry@orion.uwaterloo.ca.}
~~\\
~~\\
          University of Waterloo\\
          Department of Combinatorics and Optimization\\
          Waterloo, Ontario N2L 3G1, Canada\\
          Research Report CORR 96-??
          }
\date{\today}
          \maketitle

{\bf Key words:} Semidefinite Programming, Relaxations,

\footnotetext{
  This report is
available by anonymous ftp at orion.uwaterloo.ca.}
\begin{abstract}
Many discrete optimization problems are very hard to solve to
optimality. Various relaxations are used to find approximate solutions.
Historically, linear relaxations have been the major tool. Though quadratic
approximations are better, and can often model the problem exactly, they
are usually too hard to solve.
However, semidefinite programming, SDP, provides an efficient way of
finding approximate solutions of quadratic constrained quadratic
programs. The SDP relaxation is obtained from 
the dual of the Lagrangian dual of quadratic constrained quadratic
programs. So, in fact, the SDP relaxation
is equivalent to Lagrangian relaxation of the quadratic model. 

This paper provides a survey of SDP relaxations for discrete
optimization problems. This includes a discussion of numerical solution
techniques.

\end{abstract}
\tableofcontents
\bs{INTRODUCTION}
 \label{sect:intro}
Discrete optimization problems are those
where the variables are restricted to discrete values.
These problems arise in many applications, e.g. production planning and
control, scheduling, location-allocation, and portfolio analysis.
However, discrete problems of modest size can prove to be very hard
to solve to optimality. Typically, relaxations are used to find
approximate solutions. The primary tool for these relaxations has been
linear programming, i.e. the functions in the discrete optimization
problem are approximated by linear functions. It is both easy to
formulate linear approximations as well as solve the resulting linear
programs using e.g. the simplex method; 
thus linear models and the simplex method enjoy great popularity.

In many cases, e.g. boolean quadratic programming, the
quadratic approximations are better than linear ones.  However, the
quadratic approximations are often equivalent to the original discrete
problem and are too hard to solve. As we show below, the
Lagrangian relaxation for quadratic constrained quadratic programs can
be solved efficiently using semidefinite programming, denoted
SDP. These relaxations
are usually much stronger than the linear ones.

We work according to the following theme: 
\begin{description}
\item
Linear relaxations have been the major tool used for discrete
optimization problems. This is due to simplicity of modelling
the relaxation and
the success in solving the relaxation.
\item
Various linear relaxations (to e.g. quadratic boolean programming)
have all been proved equal to the Lagrangian
dual (Lagrangian relaxation) of a linear model (e.g. \cite{AdDe:94}).
\item
Quadratic models are better than linear models but are too hard to
solve.
\item
SDP provides an efficient solution technique for the Lagrangian
relaxation of quadratic models.
\item
Many quadratic relaxations have been proved equivalent to the Lagrangian
relaxation, i.e. to the SDP relaxation. From this and the linear case,
we conclude that we cannot find a better tractable problem than
the Lagrangian relaxation, i.e. the SDP relaxation for the quadratic
model.
\end{description}



\subsection{Max-Cut and Boolean Quadratic Problems}
\label{sect:maxcut}
We illustrate the above discussion with one of the major success stories
for semidefinite relaxations.
\subsubsection{Application Areas - Real World Problem Source}
\label{sect:applmaxcut}
The max-cut problem is one of the earliest combinatorial problems known
to be NP-complete \cite{GJ:79}. In fact it was one of the 21 problems on
Karp's famous list \cite{Ka:72}. However, it is polynomially solvable for 
planar graphs \cite{Ha:75,OrDo:72}, for graphs not contractible to $K_5$
\cite{MR84k:90048}, and for weakly bipartite graphs 
when all the weights $c_{ij}$
are nonnegative \cite{GrPu:81}.  For an excellent survey  
on the max cut problem, the reader is referred to \cite{PoTu:95}.

The max cut problem has many practical applications. In solid-state physics, 
the problem of determining the ground state of spin glasses, using the 
Ising model, can be formulated as an optimization problem in $\pm 1$ variables. 
This problem easily reduces to a max cut problem \cite{BGJR:88}. 
The max cut problem also arises in the VLSI design of computer chips     
\cite{BGJR:88,Le:90} and in many other areas as well \cite{PoTu:95}.  



\subsubsection{Problem Definition}
\label{sect:probdef}
Suppose that $G=(V,E)$ is an undirected graph with
edge set $V = \{v_i\}_{i=1}^n$ and weights $w_{ij}$
on the edges $(v_i,v_j) \in E$.
The {\em max-cut problem} consists in finding
the index set ${\cal I} \subset \{1,2, \ldots n\},$
to maximize the weight of the edges
with one end point with index in ${\cal I}$ and the other in the
complement.
This is equivalent to the following discrete optimization problem with a
quadratic objective.
\[
(MC)~~~  \begin{array}{c}
    \max ~ \frac 12 \sum_{i<j} w_{ij}(1-x_ix_j),~~~x \in  \{ \pm 1 \}^n.
\end{array}
\]
We equate $x_i=1$ with $i \in \cal I$ and -1 otherwise.  Define the
quadratic objective
\[ q(x) := x^tQx-2c^tx, \]
where $Q$ is an $n \times n$ symmetric matrix.
Then, the boolean quadratic programming problem is
 equivalent to the
{\em $(\pm 1)$-quadratic programming problem}
\beq
\label{eq:homogquad}
\mu^*:=\max ~ q(x),~~~x \in \{ \pm 1 \}^n.
\end{equation}
The max-cut problem is obtained by setting $c=0$ in the above objective
function.


\subsubsection{Polyhedral Approach}
\label{sect:polappr}
A linear relaxation is obtained using ...???
give details of linear relaxation here ?????

see e.g. the vast
literature on roof duality for boolean quadratic programming
\cite{HaHaSi:84,HaRu:70,AdDe:94} and other linear based approximations,
e.g. \cite{AdJo:94}.

For 0-1 quadratic programming there have been many different linear
approximations derived and tested. In \cite{BoCrHa:90}, the authors
show that three seemingly different linear relaxations are all equal.
These linear relaxations are referred to as roof duality. Then in
\cite{AdDe:94} it is shown that roof duality is in fact equal to
Lagrangian duality, i.e. the roof relaxation is equivalent to the
Lagrangian relaxation. Thus, many attempts in improving linear
relaxations have all led to the Lagrangian relaxation for a linear
version of the problem.

Another approach is to start by relaxing the cut polytope, the convex
hull of all cut characteristic vectors, into the unit cube. Valid
inequalities, preferably facet-defining inequalities, for the cut polytope 
are added successively as needed to tighten the relaxed set. Various classes of
facet-defining inequalities are known for the cut polytope \cite{PoTu:95}.
One such class of facet-defining inequalities is the class of triangle 
inequalities
  \[ x_{ij} +x_{ik} +x_{jk} \leq 2.\]
For a computational study of the max cut problem using such cutting plane
algorithm see \cite{DeRi:92}. 


\subsubsection{SDP Relaxation}
\label{sect:sdprelax}
Can we find a better approximation?
We can start by replacing the $(\pm 1)$ 
constraints with the quadratic constraints
\[  x_i^2=1,~i=1,\ldots,n. \]
This of course is an equivalent representation of the $\pm 1$
constraints. Thus this equivalent problem is just as hard to solve.
However, we can use Lagrangian relaxation to get an upper bound.
We delete the quadratic constraints and add them to the objective
function with Lagrange multipliers $\lambda_i.$
We then solve an unconstrained problem to get an upper bound
for the original constrained problem.
\begin{eqnarray*}
\mu^* \leq 
 \max_{x} x^tQx + \sum_i \lambda_i (1-x^2_i).
\end{eqnarray*}
Since the above is an upper bound for any choice of $\lambda_i$, we get
the following Lagrangian relaxation bound.
\begin{eqnarray*}
\mu^* \leq 
B_{mc} &:=& \min_{\lambda} \max_{x} x^tQx + \sum_i \lambda_i (1-x^2_i) \\
       & =& \min_{\lambda} \max_{x} x^t\left(Q-\Diag (\lambda) \right)x 
           + \lambda^te.
\end{eqnarray*}
First, we remark that the above min-max problem reduces to a tractable
convex minimization problem, since the {\em dual functional}
\[ 
  h(\lambda) := \max_{x} x^tQx + \sum_i \lambda_i (1-x^2_i) 
\]
is the maximum of linear functions and so is convex. In fact, the
Lagrangian dual is always a nice tractable problem.
We now note that the inner maximization problem is infinite valued
unless the Hessian of the Lagrangian is negative semidefinite, i.e. we
have the {\em hidden semidefinite constraint}
\[ Q - \Diag (\lambda) \preceq 0.  \]
Moreover, once we add this semidefinite constraint to the outer
minimization problem, the inner maximization is attained at $x=0.$ We
have eliminated the $x$ variable and the maximization part of the
problem.

Therefore the upper bound for MC can be obtained by solving the following SDP.
\beq
\label{eq:mcD}
\begin{array}{cc}
\min & \left<\lambda ,e\right> \\
\mbox{subject to} & Q-\Diag (\lambda) \preceq 0,
\end{array}
\end{equation}
where $\Diag ( \lambda)$ is the diagonal matrix formed using the vector
$\lambda.$
We can then treat this program as if it were an LP and note that the
adjoint operator $\Diag^*(Y)=\diag(Y),$ the vector of the matrix $Y.$
Moreover, the semidefinite cone is
self polar. We then get the following dual SDP to the above Lagrangian
dual.
\beq
\label{eq:mcP}
\begin{array}{cc}
\max & \tr QX \\
\mbox{subject to} & \diag(X) = e\\
      & X \succeq 0.
\end{array}
\end{equation}
The above is the SDP relaxation of MC. This can be obtained directly by
noting that $x_i^2=1$ is equivalent to
\[  \diag(xx^t) = e  \]
and $x^tQx= \tr Qxx^t.$ Therefore the relaxation is obtained by
replacing $xx^t$ by the symmetric positive semidefinite matrix $X$, i.e.
we relax the rank-1 requirement when $X=xx^t.$




\subsubsection{SDP Algorithm}
We can derive very efficient primal-dual
interior-point (p-d i-p) algorithms. For example, we start
with the dual problem and formulate the log-barrier problem with fixed
parameter $\mu >0$
\beq
\label{eq:duallogbar}
\begin{array}{cc}
\min & \left<\lambda ,e\right> + \tr Y\left(Q-\Diag (\lambda) + Z \right) 
             - \mu \log \det Z\\
\mbox{subject to} & Z \succ 0.
\end{array}
\end{equation}
We now solve this unconstrained problem by differentiation.

We get the dual and primal feasibility and complementary slackness.

change to get more linearity - apply  Newton step. Different
directions???

\subsubsection{Theoretical Error Bounds}
\label{sect:approxsol}
(Franz working on this)
We now discuss Goemans-Williamson and the approximate solution - start
with Poljak conjecture.

\subsection{Historical Notes}
Semidefinite matrices have been studied extensively for a long time. The
geometry of the cone of semidefinite matrices is well known, see e.g.
the unpublished paper by
Bohnenblust ????? and the comments in Barker-Carlson ??????
Duality for SDP also known for a long time e.g. Duffin ??? Wolkowicz
???? currently Ramana-Tuncel-Wolkowicz.

However, applications and algorithms for SDP relaxations are more recent.
- Lovacz-Schreijver - Balas ????
- Adams-Sherali reformulation ???
Shor paper on hidden
semidefinite constraint ???? PoReWo ??? independently ???
-Poljak conjecture - eigenvalue relationships - Goemans-Williamson
breakthrough randomized algorithms Williamson thesis ???
Nesterov and Nemirovski framework for algorithms.
Alizadeh survey paper  on applications  and algorithms?????


\subsection{Outline of Paper}
In summary, we see that if we try to obtain an upper bound for a quadratic
program, then we have a hidden semidefinite constraint and we end up
with a primal-dual pair of SDP's. We can then use an
p-d i-p approach to solving the relaxation.
Thus we have a scheme to find tractable relaxations.
In addition, the resulting bounds are in general very strong.
approximation.

In this paper we show that SDP relaxation works for many discrete
optimization problems.

The outline of the paper follows. Next, in Section \ref{sect:prelims},
we present preliminary results and notations.

We begin the applications in Section \ref{sect:assgnprobs} with assignment
type problems, e.g. the quadratic assignment problem, graph
partitioning, and set partitioning (covering). The SDP approach has been
very successful and has improved existing bounds????

Several graph problems are described in Section 
\ref{sect:graphprobs}

We continue with ???? engineering applications????

\section{PRELIMINARIES}
\label{sect:prelims}
Semidefinite programming, SDP, is a relatively new area and notation has
not yet been standardized. The constraints in SDP are typically linear
operator constraints on matrix variables; however, there is a reluctance
to use linear operators. We present both types of notation but use the
linear operator equations in this paper.

We work with the space of 
$t \times t$ {\em real matrices} denoted 
${\mathcal M}_t$, and the space of
$t \times t$ {\em symmetric matrices} denoted 
${\mathcal S}_t$. $\Diag(v)$ denotes the diagonal matrix formed from the vector 
$v$ and conversely, (the adjoint of $\Diag(v)$) $\diag(M)$ is the vector 
of the diagonal elements of the matrix $M$; ${\mathcal R}(M)$, ${\mathcal N}(M)$ 
denote the {\em range space} and {\em null space}, respectively;
$e$ is the vector of ones and $e_i$ is the 
i-th unit vector; $E$ denotes the matrix of ones and $E_{ij} := e_i e_j^T$;
$M_{:,t:j}$ refers to the columns $t$ to $j$ of $M$ and
$M_{i:s,:}$ refers to the rows $i$ to $s$ of $M.$
The set of matrices with row and column sums one, 
is denoted by
${\mathcal E} := \{ X : Xe=X^Te=e \}$ and  
is called the set of {\em assignment constraints};
the set of (0,1)-matrices is denoted by
${\mathcal Z} := \left\{ X : X_{ij} \in \{0,1\} \right\}$;  
the set of {\em nonnegative matrices} is denoted by
${\mathcal N} := \left\{ X : X_{ij} \geq 0 \right\}$;  
while the set of orthogonal matrices is
denoted by ${\mathcal O} := \{ X : XX^T=X^TX=I \},$ where $I$ is the identity
matrix. 

For symmetric matrices $M_1 \preceq M_2 ~(M_1 \prec M_2 )$ refers to the 
L\"{o}wner partial order, i.e.  that $M_1 - M_2$ is negative semidefinite
(negative definite, respectively); similar definitions hold for positive 
semidefinite and positive definite; $V \leq W,~(V<W)$ refers to
elementwise ordering of the matrices. The space of symmetric 
matrices is considered with the trace inner product $<M,N> = \trace MN.$

We use the {\em Kronecker product}, or tensor product, of two matrices, 
$A \otimes B$, when discussing the quadratic assignment problem QAP; 
$\kvec(X)$ denotes the vector formed from the columns of the matrix $X$, 
while $\kmat(x)$ denotes the matrix formed from the vector $x$. 
Note that, see e.g.  \cite{HoJo:85},
\begin{enumerate}
\item
$ (A \otimes B) (U \otimes V) = AU \otimes BV. $
\item
$ \kvec (AYB)=(B^T \otimes A) \kvec (Y). $
\item
$ (A \otimes B)^T = A^T \otimes B^T. $
\end{enumerate}
The {\em Hadamard product} or elementwise product of two matrices $A$ and 
$B$ is denoted $A \circ B.$ 

We partition a symmetric matrix $Y \in {\cal S}_{n^2+1}$ 
into blocks as follows.
\beq \label{eq:blocknot}
Y =
\left[ \begin{array}{c|c} y_{00} & Y_0^T \\ \hline Y_0^{} & Z \end{array}
\right] =
\left[ \begin{array}{c|cccc} 
y_{00} & Y^{01} & \ldots & Y^{0n} \\ \hline
Y^{10} & Y^{11} & \ldots & Y^{1n} \\
\vdots & \vdots & \ddots & \vdots \\
Y^{n0} & Y^{n1} & \ldots & Y^{nn} \\
\end{array} \right],
\end{equation}
where we use the index 0 for the first row and column. Hence 
$Y_0\in\Re^{n^2}$, $Z\in{\cal S}_{n^2}$, $Y^{p0}\in\Re^n$, and $Y^{pq}\in
{\cal M}_n$. When referring to entry $r,s \in \{1,2,\ldots,n^2\}$ of
$Z$, we also use the pairs $(i,j),(k,l)$ with 
$i,j,k,l \in \{1,2,\ldots,n\}$. This identifies the element in row 
$r=(i-1)n+j$ and column $s=(k-1)n+l$ by $Y_{(i,j),(k,l)}$. This 
notation is going to simplify both the modeling and the presentation of 
properties of the relaxations. If we consider $Z$ as 
a matrix consisting of $n \times n$ blocks $Y^{ik}$, then
$Y_{(i,j),(k,l)}$ is just element $(j,l)$ of block $(i,k)$. 


\bs{ASSIGNMENT PROBLEMS}
\label{sect:assgnprobs}
We begin with the class of assignment problems, in particular, 
We begin with the quadratic assignment problem (QAP) and continue with
graph partitioning and set partitioning.

\subsection{The Quadratic Assignment Problem}
\label{sect:qap}

\subsubsection{Problem Background and Applications}
\label{sect:probdefqap}
The QAP in the trace formulation is
\[
(QAP)~~ \begin{array}{ccc}
\mu^*:= &\min\limits_{X \in \Pi} & \tr AXBX^T - 2CX^T, \\
\end{array}
\]
where $A, B$ are real symmetric $n\times n$ matrices, $C$ is a  
real $n\times n$ matrix, and $\Pi$ denotes the
set of permutation matrices. (We assume $n \geq 4$ to avoid
trivialities.) QAP is used to model the problem of
allocating a set of $n$ facilities to a set of $n$ locations while
minimizing the quadratic objective arising from the distance between the
locations in combination with the flow between the facilities.
The QAP is well known to be $N\!P$-hard and, in practice, problems of 
moderate sizes, such as $n=16$, are still considered very hard. 

The QAP is an important problem in that it has many important
applications. These include many problems where there is a quadratic
objective. One Example is facility location problems where one has to
contend with the distance between facilities as well as with the flow,
i.e. the actual distance is flow times physical distance. This includes
typewriter design, VLSI design, etc...

references - surveys - URL for bib file.????

\subsubsection{Polyhedral Approach}
Linear Model for QAP is ... ?????
Linear relaxations mainly Gilmore-Lawler bound ... Adams paper .... ???

\subsubsection{SDP Relaxation for QAP} \label{sect:sdprelaxqap}
Bounds for QAP using SDP relaxations have recently been presented in
\cite{KaReWoZh:94,zhao:96}.
These relaxations have proven to be very successful and interesting.
The relaxation of the linear 
equality constraints, corresponding to the doubly stochastic property of
permutation matrices,  implies that the
SDP relaxation does not satisfy the Slater constraint qualification. 
Although there is no duality gap in theory,
since the dual does satisfy Slater's constraint
qualification, this leads to an unbounded dual optimal solution set.
Numerical difficulties can arise when trying to implement
interior-point methods. However, 
the {\em minimal face} of the semidefinite cone can be found using the
structure of the barycenter of the convex hull
of the permutation matrices. In fact, the minimal face is completely
defined by the row and column sum property of permutation matrices.
Surprisingly, the 0,1 property does not change the minimal face.
Then, the
primal problem can be projected onto the minimal face. This yields a
regularized SDP of smaller dimension.

Just as was done for the max-cut problem, we can present a quadratic
model for the QAP and find a SDP relaxation directly or by using the
dual of the Lagrangian dual. 
There are several choices for the quadratic
model since many redundant quadratic constraints can be added.
It is interesting to note that though these constraints may be redundant
in the quadratic model, they are not necessarily redundant in the SDP
relaxation of the quadratic model.
A quadratic model can be  found from
using the fact that the set of permutation matrices 
$\Pi$ can be characterized 
as the intersection of (0,1)-matrices with ${\mathcal E}$ and ${\mathcal O}$,
i.e.
\beq
\label{eq:qapequivs}
 \Pi = {\mathcal E} \cap {\mathcal Z} = {\mathcal O} \cap {\mathcal Z}, 
\end{equation}
see e.g. \cite{HaReWo:89}. Therefore, we can rewrite QAP as
\[
(QAP_{\mathcal E})~~
\begin{array}{ccl}
\mu^*:=
&\min & \tr AXBX^T - 2CX^T \\
&\mbox{~s.t.~} & XX^T =  X^TX = I \\
              && Xe = X^Te = e \\
        && X_{ij}^2 - X_{ij} = 0,~~ \forall i,j.
\end{array}
\] 


Alternativel, the SDP relaxation can be obtained
directly from QAP. This involves {\em lifting} the vector
$x=\kvec(X)$ into the matrix space $S_{n^2+1}.$
We now outline this for the quadratic constraints that arise from the
fact that $X$ is a $(0,1)$, orthogonal matrix .
Let $X \in \Pi_n$ be a permutation matrix and, again, let $x=\kvec(X)$
and $c=\kvec(C).$ Then the objective function for QAP is
\begin{eqnarray*}
  q(X) &=& \tr AXBX^T - 2CX^T \\
       &=& x^T (B \otimes A) x -2c^Tx \\
       &=& \trace xx^T (B \otimes A)  -2c^Tx \\
       &=& \trace L_Q Y_X,
\end{eqnarray*}
where we define the $(n^2+1) \times (n^2+1)$ matrices
\beq \label{eq:lq}
L_Q := \left[ \begin{array}{cc}
0 & - \kvec (C)^T \\
-\kvec (C) & B \otimes A
\end{array} \right],
\end{equation}
and
\beq
\label{eq:yx}
Y_X := \left[
\begin{array}{cc}
x_0& x^T \\
x & xx^T
\end{array}
\right].
\end{equation}


Note that the barycenter $\hat{Y}$ is in the relative interior of the feasible
set. Therefore the null space of $\hat{Y}$ determines
the dimension of the minimal face which
contains the feasible set. However, the dimension of the feasible set
can be (and is) smaller. We now take a closer look at the structure 
of $\hat{Y}$ to determine the $0$ entries. The relaxation is obtained from 
\begin{eqnarray*}
 Y &=& 
  \left(
  \begin{array}{c}
   1 \\ \kvec(X)
   \end{array}   \right)
( 1~~\kvec(X)^T)  \\
   &=& 
\begin{array}{cc}
   \left(
  \begin{array}{c}
   1 \\ 
   X_{:1}\\ 
   X_{:2}\\ 
   \vdots \\ 
   X_{:n}\\ 
   \end{array}   \right)
   (1 ~~  
   X_{:1}^T~~ 
   X_{:2}^T~~ 
   \vdots ~~ 
   X_{:n}^T)
\end{array}\\
\end{eqnarray*}
which contains the $n^2$ blocks
\[
  (X_{:i}X_{:j}^T).
\]
We then have
\[  \diag(X_{:i}X_{:j}^T)=X_{:i} \circ X_{:j} = 0, ~ \mbox{if}~ i \neq j,
\]
and
\[ X_{i:} \circ X_{j:} = 0, ~ \mbox{if}~ i \neq j,
\]
i.e. the diagonal of the off-diagonal blocks are identically zero and
the off-diagonal of the diagonal blocks are identically zero. These are
exactly the zeros of the barycenter $\hat{Y}.$

The above description defines the so-called gangster operator. Let 
$J \subset \{(i,j):1\le i,j \le n^{2}+1\}$. 
The operator 
${\mathcal G}_{J}:  {\mathcal S}_{n^2+1} \rightarrow {\mathcal S}_{n^2+1}$ is
called the {\em Gangster} operator.
For matrix $Y$, 
and $i,j=1,\ldots,n^{2}+1,$
the $ij$
component of the image of the gangster operator is defined as
\beq \label{eq:gangster}
({\mathcal G}_{J}(Y))_{ij}:=\left\{\begin{array}{ll}
                      Y_{ij} & \mbox{if}~ (i,j) \in J\\
                      0     & \mbox{otherwise.}
                    \end{array}
                    \right.
\end{equation}
The subspace of $(n^{2}+1)\times
(n^{2}+1)$ symmetric matrices with nonzero index set $J$ is denoted
${\mathcal S}_{J}$, i.e.,
\[
{\mathcal S}_{J}:=\{X \in {\mathcal S}_{n^2+1}: X_{ij} =0
~~\mbox{if}~~(i,j) \not \in J\}.
\]
{From} the definition of the gangster operator, we can easily see the following.
\[
{\cal R}({\mathcal S}_{J}) = {\mathcal S}_{J}
\]
and
\[
{\cal N}({\mathcal S}_{-J}) = {\mathcal S}_{-J},
\]
where $-J$ is denoted as the complementary set of $J$.
Therefore, let $J=\{(i,j): \hat{Y}_{ij}=0\}$, be the zeros found above 
using the Hadamard product, we have
\beq \label{eq:Ghaty}
{\mathcal G}_{J}(\hat{Y})=0.
\end{equation}
Thus the gangster operator, acting on a matrix $Y$, 
shoots holes (zeros) through the matrix $Y$ in
the positions where $\hat{Y}$ is not zero.
For any permutation matrix $X \in \Pi$, the matrix
$Y_{X}$ has all its entries
either $0$
or $1$; and $\hat{Y}$ is just a convex combination of all these matrices
$Y_{X}$ for $X \in \Pi$. Hence, from (\ref{eq:Ghaty}), we have
\[
{\mathcal G}_{J}(Y_{X})=0, ~~\mbox{for all}~~X \in \Pi.
\]
Therefore, we can further tighten our relaxation by adding the
constraint 
\beq \label{eq:gangconstr}
{\mathcal G}_{J}(Y)=0.
\end{equation}

Note that the adjoint equation
\[
\trace({\mathcal G}^{*}_{J}(Z)Y)=\trace(Z {\mathcal G}_{J}(Y)),
\]
implies that the gangster operator is self-adjoint,
i.e.\
\[
    {\mathcal G}_{J}^{*}={\mathcal G}_{J}.
\]

 We can now get
a very simple projected relaxation.

\beq \label{eq:relax2}
(QAP_{R2})~~~~
\begin{array}{lll}
\mu_{R2} := & \min & \tr (\hat{V}^TL_Q\hat{V})R   \\
 & \mbox{~s.t.}
 & {\mathcal G}_{\bar{J}}(\hat{V}R\hat{V}^T) = 0  \\
 &&  R \succeq 0.  
\end{array}
\end{equation}
The dimension of the range space is
determined by the cardinality of the set $\bar{J},$ i.e. there are
$n^{3}-2n^{2}+1$ constraints.

The dual problem is
\[
\begin{array}{lll}
\mu_{R2} := & \max & -Y_{00} \\
& \mbox{~s.t.}
&\hat{V}^{T}(L_{Q}+{\mathcal G}^{*}_{\bar{J}}(Y))\hat{V} \succeq 0.
\end{array}
\]
Note ${\cal R}({\mathcal G}^{*}_{\bar{J}})={\cal R}({\mathcal G}_{\bar{J}})
= {\cal S}_{bar{J}}$. The dual problem can be expressed as follows
\[
\begin{array}{lll}
\mu_{R2} := & \max & -Y_{00} \\
& \mbox{~s.t.}
&\hat{V}^{T}(L_{Q}+Y)\hat{V} \succeq 0\\
&& Y\in {\cal S}_{\bar{J}}.
\end{array}
\]

 

We now consider generic inequality constraints to further tighten the
derived relaxations. These constraints come from the relaxation of the
(0,1)-constraints of the original problem. For $Y = Y_X,$ with $X\in\Pi,$
the simplest inequalities are of the type
$$
Y_{(i,j),(k,l)} \geq 0, \mbox{~~since~~} x_{ij} x_{kl} \geq 0.
$$
Helmberg et al.\ \cite{HePoReWo:95} show that the 
so called triangle inequalities of the general integer quadratic 
programming problem in the (-1,+1)-model are also generic inequalities 
for the (0,1)-formulation. Nevertheless, we are going to restrict 
ourselves to the simplest type of inequalities, which are facet defining
for the QAP polytope, as shown in \cite{JuKa:96,Rijal:95}. Beside 
the nonnegativity
constraints one can also impose nonpositivity constraints on the zero 
elements of $\hat{Y}$. Together with the gangster operator, these 
inequalities and the corresponding nonnegativity constraints
are clearly redundant.
But for the basic relaxation $(QAP_{R1})$ we can use both
nonnegativity and nonpositivity constraints to approximate the gangster
operator. This leads to the following semidefinite relaxation of QAP.

\subsubsection{P-D I-P Algorithm} \label{sect:pdalgor}
The algorithm used follows the
p-d i-p method of
Helmberg et al.\ \cite{Helmberg:94,HeReVaWo:93}.
We also address practical and 
computational aspects for their solution.
However, the resulting linear system for the Newton direction is very
large and very costly to form. Therefore a
preconditioned conjugate gradient method is used
to solve the  system inexactly.
The diagonal of the matrix representation is used as the preconditioner.
The special structure of the gangster 
operator makes it relatively cheap to construct the preconditioner.

In this Section we present the results of our numerical experiments. The
experiments are divided into two parts. First we investigate the quality of
the new bounds compared to bounds from the literature. Then, we look at the 
applicability of bounds based on semidefinite relaxation to branch and bound, 
see Table \ref{tab:branch}.

The results of the comparisons are summarized in the following tables. 
Tables \ref{tab:tests1} and \ref{tab:tests1a} contain instances from the 
current version of QAPLIB \cite{BuKaRe:91} while Table \ref{tab:tests2} 
consists of data of a previous version of the library. The tables read as 
follows. The first column indicates the problem instance 
and its size, e.g.\ Nug$xx$ refers to the Nugent example of size $xx$. 
For references of the problem instances we refer to QAPLIB
\cite{BuKaRe:91}. The following columns contain the best known feasible 
solution (which is optimal for all $n\leq 22$); the Gilmore-Lawler bound 
GLB \cite{Gil:62,Law:63}; the projection or elimination bound ELI of 
\cite{HaReWo:89}; the linear programming bound RRD obtained in 
\cite{ResRamDre95}, and an improved eigenvalue bound EVB3 from \cite{ReWo:89}.
For EVB3 we performed 100 iterations of the underlying bundle trust code.
The last three columns contain the bounds obtained in this paper, 
$\mu_{R1}$, $\mu_{R2}$ and $\mu_{R3}$. An `n.a.' means that the 
value of the bound is not available.

Due to the restriction on the number of inequalities in the cutting plane
approach to $m_b\leq 2000$ we do not report $\mu_{R3}$ for instances larger 
than $n=22$. One can observe that this restriction on the size of the model 
does not allow for large improvements within the cutting plane approach for 
instances of size $n\geq 15$. In this case the gangster model $(QAP_{R2})$ 
provides stronger bounds than $(QAP_{R3})$. But the block model provides 
at least a primal feasible approach from the beginning and the 
less expensive basic relaxation $(QAP_{R1})$ is competitive with respect
to RRD for the Nug$xx$ instances of dimension $n\geq 20$.

\begin{table} 
\begin{center}
\begin{tabular}{|l|rrrrr|rrr|} \hline 
        & Sol. &  GLB &  ELI &  RRD & EVB3 &$\mu_{R1}$
                                               &$\mu_{R2}$&$\mu_{R3}$\\
\hline
 Esc16a &   68 &   38 &   47 &  68  &   50 &    47 &  50  &   47 \\
 Esc16b &  292 &  220 &  250 & 278  &  276 &   250 & 276  &  277 \\ 
 Esc16c &  160 &   83 &   95 & 118  &  113 &    95 & 113  &  110 \\
 Esc16d &   16 &    3 &  -19 &   4  &  -12 &   -19 & -12  &   -6 \\
 Esc16e &   28 &   12 &    6 &  14  &   13 &     6 &  13  &    9 \\
 Esc16g &   26 &   12 &    9 &  14  &   11 &     9 &  11  &   10 \\
 Esc16h &  996 &  625 &  708 & 704  &  708 &   708 & 909  &  806 \\
 Esc16i &   14 &    0 &  -25 &   0  &  -21 &   -25 & -21  &   -6 \\
 Esc16j &    8 &    1 &   -6 &   2  &   -4 &    -6 &  -4  &   -4 \\
\hline
 Had12  & 1652 & 1536 & 1573 & n.a. & 1595 &  1604 & 1640 & 1648 \\
 Had14  & 2724 & 2492 & 2609 & n.a. & 2643 &  2651 & 2709 & 2703 \\
 Had16  & 3720 & 3358 & 3560 & n.a. & 3601 &  3612 & 3678 & 3648 \\
 Had18  & 5358 & 4776 & 5104 & n.a. & 5176 &  5174 & 5286 & 5226 \\
 Had20  & 6922 & 6166 & 6625 & n.a. & 6702 &  6713 & 6847 & 6758 \\ 
\hline
 Kra30a &88900 &68360 &63717 &76003 & n.a. & 69736 & & --~ \\
 Kra30b &91420 &69065 &63818 &76752 & n.a. & 70324 & & --~ \\
\hline
 Nug12  &  578 &  493 &  472 &  523 &  498 &   486 & 530  &  547 \\
 Nug14  & 1014 &  852 &  871 & n.a. &  898 &   903 & 959  &  967 \\
 Nug15  & 1150 &  963 &  973 & 1041 & 1001 &  1009 & 1060 & 1075 \\
 Nug16a & 1610 & 1314 & 1403 & n.a. & 1455 &  1461 & 1527 & 1520 \\
 Nug16b & 1240 & 1022 & 1046 & n.a. & 1081 &  1082 & 1138 & 1132 \\
 Nug17  & 1732 & 1388 & 1487 & n.a. & 1521 &  1548 & 1621 & 1604 \\
 Nug18  & 1930 & 1554 & 1663 & n.a. & 1707 &  1723 & 1801 & 1776 \\
 Nug20  & 2570 & 2057 & 2196 & 2182 & 2290 &  2281 & 2385 & 2326 \\
 Nug21  & 2438 & 1833 & 1979 & n.a. & 2116 &  2090 & 2252 & 2157 \\
 Nug22  & 3596 & 2483 & 2966 & n.a. & 3174 &  3140 & 3394 & 3234 \\
 Nug24  & 3592 & 2676 & 2960 & n.a. & 3074 &  3068 &      & --~  \\
 Nug25  & 3800 & 2869 & 3190 & n.a. & 3287 &  3305 &      & --~  \\
 Nug30  & 6124 & 4539 & 5266 & 4805 & 5448 &  5413 &      & --~  \\
\hline
\end{tabular}
\caption{QAPLIB instances 1} \label{tab:tests1}
\end{center}
\end{table}

\begin{table} 
\begin{center}
\begin{tabular}{|l|rrrrr|rrr|} \hline
        & Sol. &  GLB &  ELI &  RRD & EVB3 &$\mu_{R1}$
                                               &$\mu_{R2}$&$\mu_{R3}$\\
\hline
 Rou12  &235528&202272&200024&224278&201337& 208685&220991&227986\\
 Rou15  &354210&298548&296705&324869&297958& 306833&323141&324900\\
 Rou20  &725522&599948&597045&643346& n.a. & 615549&642448&631680\\
\hline
 Scr12  & 31410& 27858&  4727& 29872& n.a. &  11117&24230 & 27183\\
 Scr15  & 51140& 44737& 10355& 49264& n.a. &  17046&42094 & 40821\\
 Scr20  &110030& 86766& 16113& 95113& n.a. &  28535&83026 & 59780\\
\hline
 Tai12a & 224416 & 195918 & 193124 & n.a. &195673 &203595&215377&220938\\
 Tai15a & 388214 & 327501 & 325019 & n.a. &327289 &333437&349476&347908\\
 Tai17a & 491812 & 412722 & 408910 & n.a. &410076 &419619&441238&435675\\
 Tai20a & 703482 & 580674 & 575831 & n.a. & n.a.  &591994&618720&606228\\
 Tai25a &1167256 & 962417 & 956657 & n.a. & n.a.  &974004 &   & --~ \\
 Tai30a &1818146 &1504688 &1500407 & n.a. & n.a.  &1529135&   & --~ \\
\hline
 Tho30  & 149936 &  90578 & 119254 & 100784 & n.a. &125972& & --~ \\
\hline
\end{tabular}
\caption{QAPLIB instances 2} \label{tab:tests1a}
\end{center}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}{|l|rrrrr|rrr|} \hline
        & Sol. &  GLB &  ELI &  RRD & EVB3 &$\mu_{R1}$
                                               &$\mu_{R2}$&$\mu_{R3}$\\
\hline
 Car10ga& 4954 & 3586 & 4079 & n.a. & 4541 &  4435 &  4853 &4919 \\
 Car10gb& 8082 & 6139 & 7211 & n.a. & 7617 &  7600 &  7960 &8035 \\
 Car10gc& 8649 & 7030 & 7837 & n.a. & 8233 &  8208 &  8561 &8612 \\
 Car10gd& 8843 & 6840 & 8006 & n.a. & 8364 &  8319 &  8666 &8780 \\
 Car10ge& 9571 & 7627 & 8672 & n.a. & 8987 &  8910 &  9349 &9473 \\
 Car10pa&32835 &28722 & -4813& n.a. & n.a. &  1583 & 12492 &30359 \\ 
 Car10pb&14282 &12546 &-14944& n.a. & n.a. & -5782 & 9934  &13361 \\
 Car10pc&14919 &12296 &-17140& n.a. & n.a. & -8040 & 2473  &13655 \\
\hline
 Esc08a &    2 &    0 &   -2 &   0  & n.a. &    -2 &     0 &   2 \\
 Esc08b &    8 &    1 &   -2 &   2  & n.a. &    -2 &     3 &   6 \\
 Esc08c &   32 &   13 &    8 &  22  & n.a. &     9 &    18 &  30 \\
 Esc08d &    6 &    2 &   -2 &   2  & n.a. &    -2 &     2 &   6 \\
 Esc08e &    2 &    0 &   -6 &   0  & n.a. &    -6 &    -4 &   1 \\
 Esc08f &   18 &    9 &    8 &  18  & n.a. &     9 &    13 &  18 \\
\hline
 Nug05  &   50 &   50 &   47 &   50 &   50 &    49 &    50 &  50 \\
 Nug06  &   86 &   84 &   69 &   86 &   70 &    74 &    85 &  86 \\
 Nug07  &  148 &  137 &  125 &  148 &  130 &   132 &   144 & 148 \\
 Nug08  &  214 &  186 &  167 &  204 &  174 &   179 &   197 & 210\\
\hline
\end{tabular}
\caption{Numerical Results for old instances} \label{tab:tests2}
\end{center}
\end{table}

The comparison with bounds from the literature shows that our bounds compare 
favorable on instances Had$xx$, Nug$xx$, Rou$xx$, and Tai$xx$. These 
instances have in common that their matrices are rather dense. On the other
hand, for sparse instances as most of Esc$xx$ and Scr$xx$ are, RRD dominates
the bounds based on semidefinite relaxation. ELI seems to be a good indicator
of when to expect the semidefinite bounds to be stronger than the ones based
on linear relaxation. It seems as if the nonnegativity constraints are more
important than the semidefinite ones on sparse instances. In this case ELI
even becomes negative. Note that on the Esc16$x$ problems ELI and $\mu_{R1}$
coincide.

The implementation of our bounds was done in MATLAB using CMEX interfaces.
Even though there is still room for improvement into this direction, our 
running times are comparable to the ones for RRD \cite{ResRamDre95}. For
the Nug20 problem instance, Resende et al.\ needed 60.19 minutes of CPU-time
to obtain their bound on a Silicon Graphics Challenge computer (150-MHz with
1.5 Gbytes of RAM). The implementation of their bounding technique was done 
in FORTRAN and C. The calculation of $\mu_{R1}$ and $\mu_{R2}$ on DEC 
3000-900 Alpha AXP computers (275-MHz with 256 Mbytes and 64 Mbytes of RAM) 
took 19.93 and 316.17 minutes of CPU-time, respectively. 

Table \ref{tab:nosymm} contains instances whose inherent symmetry was
destroyed by introducing a linear term. For instance, the distance matrices 
of the Nug$xx$ problems contain the distances of rectangular 
grids. The grid on which the locations of Nug12 are placed is given by
$$
G = 
\begin{array}{|c|c|c|c|}
\hline
~~1~~ & ~~2~~ & ~~3~~ & ~~4~~ \\ \hline
~~5~~ & ~~6~~ & ~~7~~ & ~~8~~ \\ \hline
~~9~~ & ~~10~~ & ~~11~~ & ~~12~~ \\ \hline
\end{array}.
$$
In this case, an assignment of any facility, say facility 1, to other 
locations but 1, 2, 5 and 6, can not result in a solution which is not
obtained by the restricted solution $1 \rightarrow \{1,2,5,6\}$. For
restricting the solution set to such a subset, we introduce a linear
cost matrix $C$ whose elements are all 0 expect $c_{1j}, j\in\{3,4,7,8,
9,10,11,12\}$. These nonzero entries of $C$ are sufficiently large numbers.
The resulting instances are marked with a `C', e.g.\ Nug12C, and are 
equivalent to the originals. Table \ref{tab:nosymm} shows that our bounds 
improve when this is done. We point out that symmetries can also be found 
in the Esc$xx$ data but we do not specify this here.

\begin{table} 
\begin{center}
\begin{tabular}{|l|rrrr|} \hline
        & Sol. &  $\mu_{R1}$ &$\mu_{R2}$ & $\mu_{R3}$ \\
\hline
 Nug12C &  578 &  492 & 534  &  545 \\
 Nug15C & 1150 & 1012 & 1075 & 1081 \\
 Nug20C & 2570 & 2292 & 2396 & 2335 \\
 Nug30C & 6124 & 5424 & 5648 &  --~ \\
\hline
\end{tabular}
\caption{Instances for which symmetry is destroyed} \label{tab:nosymm}
\end{center}
\end{table}

\begin{table} 
\begin{center}
\begin{tabular}{|lc|rrr|rrrrrr|} \hline
        & $n$ & Sol. &  GLB & ($ir$) &  $\mu_{R1}$ & ($ir$) &
                                  $\mu_{R2}$ & ($ir$) &$\mu_{R3}$ & ($ir$)\\
\hline
 Nug12   & 12 & 578 & 493 &      & 486 &       & 530 &      & 547 & \\
 Nug12.1 & 11 & 586 & 496 & (0.6)& 514 & (5.4) & 551 & (3.9)& 574 & (4.9)\\
 Nug12.2 & 11 & 578 & 495 & (0.4)& 514 & (5.4) & 553 & (4.3)& 571 & (4.3)\\
 Nug12.5 & 11 & 578 & 494 & (0.2)& 524 & (7.8) & 552 & (4.1)& 570 & (4.2)\\
 Nug12.6 & 11 & 586 & 499 & (1.2)& 530 & (9.0) & 561 & (5.8)& 578 & (5.6)\\ 
\hline
 Nug15   & 15 & 1150 & 963 &     & 1009&     & 1060&     & 1075& \\
 Nug15.1 & 14 & 1150 & 967 &(0.4)& 1049&(4.0)& 1104&(4.2)& 1114&(3.6)\\
 Nug15.2 & 14 & 1166 & 974 &(1.1)& 1076&(6.6)& 1124&(6.0)& 1135&(5.6)\\
 Nug15.3 & 14 & 1200 & 987 &(2.5)& 1075&(6.5)& 1133&(6.9)& 1145&(6.5)\\
 Nug15.6 & 14 & 1152 & 968 &(0.5)& 1056&(4.7)& 1106&(4.3)& 1118&(4.0)\\
 Nug15.7 & 14 & 1166 & 979 &(1.7)& 1052&(4.3)& 1112&(5.2)& 1125&(4.7)\\
 Nug15.8 & 14 & 1168 & 983 &(2.1)& 1063&(5.4)& 1118&(5.5)& 1133&(5.4)\\
\hline
 Nug20   & 20 & 2570 & 2057&     & 2281&     & 2385&     & 2326 & \\
 Nug20.1 & 19 & 2628 & 2082&(1.2)& 2358&(3.4)& 2449&(2.7)& 2414 &(3.8) \\
 Nug20.2 & 19 & 2600 & 2130&(3.6)& 2401&(5.3)& 2489&(4.4)& 2464 &(6.0) \\
 Nug20.3 & 19 & 2588 & 2067&(0.5)& 2331&(2.2)& 2428&(1.8)& 2392 &(2.8) \\
 Nug20.6 & 19 & 2570 & 2064&(0.3)& 2341&(2.6)& 2431&(1.9)& 2403 &(3.3) \\
 Nug20.7 & 19 & 2634 & 2105&(2.3)& 2387&(4.6)& 2479&(3.9)& 2436 &(4.7) \\
 Nug20.8 & 19 & 2636 & 2127&(3.4)& 2381&(4.4)& 2485&(4.2)& 2438 &(4.8) \\
\hline
\end{tabular}
\caption{Results for first level in branching tree} \label{tab:branch}
\end{center}
\end{table}

We also investigate whether the new bounds are candidates to be used within 
a branch and bound algorithm. Therefore we need to look at their
quality in lower levels of the branching tree, i.e., we want to see how fast 
the lower bounds can be increased by branching. Table \ref{tab:branch}
gives the results for the first level, when one partial assignment is made.
As pointed out above, for the Nug12 example there are only four subproblems 
in the first level. The partial assignments of facility 1 are
indicated by the entry after the dot in the name of the instance. To measure
the increasing rate ($ir$) of the lower bound ($lbd$) by branching, we 
define the rate in percent as follows.
%\[
%\mbox{increasing rate}:= 
%\frac{\mbox{lowerbound}_{\mbox{child}}-
%\mbox{lowerbound}_{\mbox{parent}}}{\mbox{lowerbound}_{\mbox{parent}}}
%\]
\[
ir := \frac{lbd_{\mbox{child}}- lbd_{\mbox{parent}}}{lbd_{\mbox{parent}}}
* 100 \mbox{\%}
\]
In Table \ref{tab:branch}, the increasing rates are shown by the numbers in 
the bracket. The numerical results in Table \ref{tab:branch} indicate that 
the lower bounds given by the SDP relaxations increase much faster than the
Gilmore-Lawler bounds 
in the first level of
the branching tree.

This and the results for the Car$xx$ data also show that the semidefinite 
bounds perform well for instances with linear terms.
\subsubsection{Theoretical Bounds} \label{sect:qaptheory}
On average bounds converge to ... no epsilon bound for SDP unless P=NP
since TSP is a special case of SDP ??? refs ????

\subsection{The Graph Partitioning Problem}
We now present a semidefinite programming, SDP,
relaxation for the graph partitioning, GP, problem. 
This relaxation provides strengthened bounds for this NP-hard problem.
We exploit the special structure of this
relaxation and find the minimal face of the
cone of $n \times n$
positive semidefinite matrices, $\p$, which contains the feasible set.
We then consider the SDP in the span of this minimal face. This
guarantees that the Slater constraint qualification (strict feasibility)
holds; this, in turn, allows us to use a primal-dual
interior-point, p-d i-p,  approach to solve the SDP.
The Newton equation which arises in each iteration
can be very large. We solve
these large linear systems using an incomplete conjugate gradient method.

\subsubsection{Background and Applications}
GP can best be described as follows.
\begin{quote}
Given: an undirected graph $G =({\cal V}, {\cal E})$ having nodes ${\cal V}$
and edges ${\cal E}$ and a
weight, $a_{ij},$ for each edge. 
We consider the problem of partitioning ${\cal V}$
into k disjoint subsets ${\cal V}_{1}, \ldots, {\cal V}_{k}$ of given sizes
$m_{1}, \ldots, m_{k}$ in such a way that the sum of weights
of edges that connect nodes in different subsets (cut edges) is minimized.
\end{quote}
We use $a_{ij}$ for the weight for the edge between node $i$ and node $j$,
where $a_{ij}=0$ if there is no edge between node $i$ and node $j$.
The symmetric matrix $ A=\left\{ a_{ij} \right\},$  with 0 on the
diagonal, is the {\em adjacency matrix} of the graph.
For a given partition of the graph into $k$ subsets, 
let $X = (x_{ij})$ be the $n\times k$  matrix
($n=\sum_i m_i$ is the cardinality
of ${\cal V}$) defined by
\[
x_{ij} = \left \{ \begin{array}{ll}
                   1 & \mbox{if node i is in the $j$th subset} \\
                   0 & \mbox{if node i is not in the $j$th subset}
                  \end{array}
         \right.
\] 
Thus the $j$th column $X_{:j}$ is the indicator set for the $j$th subset.
Such an $X$ can represent the partition.
For each such partition $X$,
\[
\frac{1}{2} \trace X^{t}AX = \frac{1}{2} \tr AXX^{t}
\] 
gives the total weight for the uncut edges. As a result, the total weight
for the cut edges is
\[
w(E_{cut}):= \frac{1}{2} (e^{t}Ae -\trace\left(X^{t}AX)\right).
\] 
Note that for any partition matrix $X$, we have 
\[
\tr X^{t}\Diag(Ae)X = e^{t}Ae,
\] 
where $\Diag$ is the diagonal matrix formed from the vector.
Therefore, the minimal weight of cut edges
can be obtained by solving the graph partitioning
problem in the trace formulation.
\[
(GP)
\begin{array}{ccc}
  &w^*(E_{cut}):=\min& \frac{1}{2} \tr X^{t}LX \\
&\mbox{subject to} & X ~\mbox{is a partition matrix},
\end{array}
\]
where the matrix
\[
L:=\Diag(Ae)-A
\]
is called the {\em Laplace matrix of the graph}.

The graph partitioning problem is 
well known to be NP-hard and therefore finding
an optimal solution is likely very difficult. Yet
this problem has many applications. One
important application is VLSI design; see e.g. \cite{Le:90} for a 
survey of Integrated Circuit Layout. One popular and very successful 
heuristic for finding "good" partitions was proposed by Kernighan and Lin
\cite{KeLi:70} in 1970. See also \cite{HaMaVa:92} for its application on
netlist partitioning.  

In the early 70's Donath and Hoffman \cite{DoHo:73} provided an 
eigenvalue-based bound for (GP). 
Several new eigenvalue-based bounds were presented
by F. Rendl and H. Wolkowicz in \cite{ReWo:90}; a computational study
showed these bounds to be very good, see e.g \cite{FaReWo:92}. 
A semidefinite relaxation technique for the equal-partitioning problem has been 
successfully developed in \cite{KaRe:95dec}.

\subsubsection{Outline}
The main result in this paper is the application of an incomplete
conjugate gradient approach within a p-d i-p method that solves a SDP
relaxation for GP.

The SDP relaxation is presented in Section Therein it
is noted that the standard Slater CQ fails. The geometry of the
relaxation is studied in Section The minimal face of
$\p$ that contains the feasible set is characterized. This
characterization is used in Section to project the
problem onto the span of the minimal face. Moreover, redundant
constraints are eliminated resulting in a very efficient SDP
relaxation.

We conclude with numerical results  in Section \ref{sect:numerics}.

\subsection{The Set Covering Problem}
Semidefinite programming (SDP) is an extension of linear programming (LP)
where the nonnegativity constraints are replaced by positive semidefiniteness
constraints on matrix variables.
SDP has proven to be very successful in
providing tight relaxations for hard combinatorial problems,  such as the
max-cut problem. The set partitioning problem (SP) is a well known NP-hard
combinatorial optimization problem. We study SDP relaxations for SP. For
large sparse problems, we propose a Mixed SDP-LP relaxations.  
\subsubsection{Semidefinite Programming}
SDP has been shown to be a very powerful
tool in several different areas, e.g.\ positive definite completion
problems, maximum entropy estimation, and bounds for hard combinatorial
problems, see e.g.\ the survey of Vandenberghe and Boyd \cite{VanBoy:94}.

Though SDP has been studied in the past, as part of the more general
cone programming problem, see e.g.\ \cite{Duff:56,w11}, there has been a
renewed interest due to the successful applications to discrete optimization
\cite{LoSc:91,GoWi:93} and to systems theory \cite{BoGhFeBa:94}.
In addition, the relaxations are equivalent to the reformulation and
linearization technique, see e.g. the survey discussion in \cite{ShAd:96},
which provides further evidence of successful applications.



\subsubsection{Introduction}
The set partitioning problem, SP, can be described by the following
problem:
\begin{quote}
Suppose we are given a set $M$ with $m$ elements and let 
\[
{\cal M} = \{M_{1}, \ldots, M_{n} \}
\]
be a given collection of subsets of $M$ such
that $\cup_{j \in N} M_{j} = M$. Let $N=\{1,2,\ldots,n\}$.  
For each $M_{j}$, there is a cost $c_{j} \geq 0$. We want to find 
a subset $F$ of
$N$ such that 
\[
\cup_{j\in F} M_{j} = M,~~~~M_{k} \cap M_{j} = \phi ~~\mbox{for}~k\neq j \in F
\] 
and the sum of the costs $\sum_{i\in F} c_{j}$ is minimized.
\end{quote} 
The collection of sets $\{M_{j}, j\in F\}$ is called a {\em set-partition}
of the set $M$. For a given set-partition, 
let $x \in \{0,1\}^{n}$ defined by  
\[
x_{j} = \left \{ \begin{array}{ll}
                  1 & \mbox{if}~~j \in F\\ 
                  0 & \mbox{otherwise}.
                 \end{array}
        \right.
\]
Such an $x$ can represent the set-partition.
We construct an $m \times n$ 0-1 matrix $A=(a_{ij})$ in the following way.
\[
a_{ij} = \left \{ \begin{array}{ll}
                  1 & \mbox{if}~~i \in M_{j}\\
                  0 & \mbox{otherwise}.
                 \end{array}
        \right.
\]
The matrix $A$ is called the {\em incidence matrix} of the family ${\cal M}$. 
Then the set partitioning problem can be formulated as the following 0-1 
integer programming problem 
\[
(SPT)~~ \begin{array}{ccl}
\mu^*:= &\min & c^tx \\
 &  \mbox{~subject to~} & Ax = e\\
  &&  x \in \{0,1\}^n.
\end{array}
\]
 Without loss generality, we assume that $A$ has full row rank. 
For each $i \in \{1,2,\ldots,m\}$, we denote
\[
a_{i} = (a_{i1}, a_{i2}, \ldots, a_{in}).
\]
Thus,  
\[
A = \left ( \begin{array}{c}
              a_{1}\\
              \vdots\\
              a_{m}
            \end{array}
    \right )
=  \left[ \begin{array}{ccc}
             a_{11} & \ldots & a_{1n} \\
             \vdots & \ddots & \vdots \\
             a_{m1} & \ldots & a_{mn} 
           \end{array}
    \right].
\] 

The set partitioning problem has been extensively investigated because of its 
special structure and its numerous practical applications. Among its 
well-known applications are: air crew scheduling; truck scheduling; bus 
scheduling;
facility location; circuit design and capital investment. (See e.g
Garfinkel and Nemhauser \cite{GarNem:69}, Marsten \cite{Mar:74}, Balas and 
Padberg \cite{BalPad:76}, Balas \cite{Bal:77}, Nemhauser
and Weber \cite{NemWeb:79}, Fisher and Kedia \cite{FisKed:90} Chan and Yano
\cite{ChaYan:92} and Hoffman and Padberg \cite{HofPad:92}.) 
Since the set partitioning problem is well-known to be NP-hard, the
current popular approaches are focused on finding a ``near optimal''
solution using various heuristic techniques and branch and bound techniques. 
It has been understood that a good lower bound (that can be computed 
efficiently) with high quality is essential 
to the
success of these approaches. A natural candidate for generating a lower bound 
is the linear programming relaxation. The linear
programming relaxation is as follows
\[
(SPS)~~ \begin{array}{ccl}
\mu_{LP}^*:= &\min & c^tx \\
 &  \mbox{~subject to~} & Ax = e\\
  &&  x \geq 0.
\end{array}
\]
In order
to find a better ``near-optimal'' solution for (SPT), a 
lot of current work  
focuses on  tightening the
linear programming relaxation. In this chapter, we  
develop an SDP relaxation for the set partitioning problem. In our approach,
in addition to
taking care of all the linear programming relaxation constraints, 
a feasible solution 
of the SDP relaxation also has to satisfy some other constraints like
the ``gangster operator'' which takes care of the special 0-1 structure of
(SPT). By this SDP approach we can generate a better lower bound 
for the set partitioning problem. 

\bs{GRAPH PROBLEMS}
\label{sect:graphprobs}
\subsection{The Maximum Clique and Related Problems}
\label{sect:maxclique}
Consider a graph $G = G (V,E,w)$,
where $V = \{1,\ldots,n\}$ denotes the set of vertices, $E$
denotes the set of edges ($|E|=m$), and  $w \geq 0$ is the weight vector
on the vertices of the graph. 
A clique of $G$ is a subset $C$
of vertices with the property that every pair of vertices in $C$
is joined by an edge. In other words, $C$ is a clique if the subgraph $G(C)$
induced by $C$ is complete.  The maximum clique problem is the problem of
finding a clique set $C$ of maximum weight (if all weights are equal,
then $C$ willahve the maximal cardinality).

Let $\omega(G)$ and $\chi(G)$ be, respectively, the weighted
clique number and the weighted chromatic number of graph $G$.
Lov\'asz \cite{Lo:79} introduced the following invariant of graphs
which we refer to as the Lov\'asz number of graphs $\theta(G)$.

Let $\cal M$ be a set of
matrices $X\in\SRN$ whose $i,j$ entries are zero whenever $i=j$ or $i,j$
is an edge in $G$. Thus $\cal M$ is an affine set of $n\times n$ matrices
of dimension $n(n-1)/2-m$. Let $\lambda_1(X)$ be the largest eigenvalue
of the symmetric matrix $X$. Then
\begin{equation}\label{theta}
\theta(G):=\min_{X\in {\cal M}}\lambda_1(X+W)
\end{equation}
where $W= w w^T$ is the rank one matrix.

One important result about the invariant $\theta$ is that:

\[
\omega(G) \leq \theta(G) \leq \chi(w)
\]


That is, $\theta$ is simultaneously an upper bound for the clique number and
chromatic number of graphs. Furthermore, $\theta$ is computable in polynomial
time.
More specifically, \ref{theta} may be
formulated as the following optimization problem:
\begin{equation}\label{dual}
\begin{array}{lll}
\min & z & \\
\mbox{subject to}& zI +X + W \succeq 0 & \\
& X_{ij}=0& \mbox{for all }i=j\mbox{ or }ij\in E
\end{array}
\end{equation}

Knuth \cite{Kn:94} gives a very nice expository of several ways of
characterizing the Lov\'{a}sz number $\theta$. The various
continuous formulations of $\theta$ can motivate efficient polynomial time
algorithms for its computation.

\nocite{Al:94,GLS-88,Kn:94,Lo:79,MoPo:92}

\subsection{The Maximum Satisfiability Problem}

Let ${\cal C}_1, {\cal C}_2, \ldots, {\cal C}_m$ be $m$ clauses,
involving $n$ Boolean variables $x_1, x_2, \ldots, x_n$, which can
take on only the values {\tt true} or {\tt false} (1 or 0).
In addition, for each clause ${\cal C}_i$, there is an associated
nonnegative weight $w_i$.
Define clause $i$ to be
\begin{displaymath}
{\cal C}_i = \bigvee_{j=1}^{n_i} l_{ij},
\end{displaymath}
where
the literals $l_{ij} \in \{ x_i, \bar{x}_i \;|\; i=1,\ldots,n\}$.
In the weighted {\em Maximum Satisfiability Problem} (MAX-SAT),
one is to determine the
assignment of truth values to the $n$ variables that
maximizes the sum of the weights of the satisfied clauses.
Note that the classical Satisfiability Problem (SAT) is a special
case of the MAX-SAT in which all clauses have unit weight and
one wants to decide if there is a truth assignment of total
weight $m$.

The weighted MAX-SAT has a natural mixed integer programming formulation.
Let $y_j = 1$ if Boolean variable $x_j$ is {\tt true} and 
$y_j = 0$ otherwise.
Furthermore, the continuous variable $z_i = 1$ if clause
${\cal C}_i$ is satisfied and $z_i = 0$, otherwise.
Consider the mixed integer linear program
\begin{displaymath} 
\max \;\; F(y,z) = \sum_{i=1}^m w_i z_i
\end{displaymath} 
subject to
\begin{displaymath} 
\sum_{j \in I^+_i} y_j + \sum_{j \in I^-_i} (1-y_j) \geq z_i,\;\;
i=1,\ldots,m,
\end{displaymath} 
\begin{displaymath} 
y_j \in \{0,1\},\;\;j=1,\ldots,n,
\end{displaymath} 
\begin{displaymath} 
0 \leq z_i \leq 1,\;\;i=1,\ldots,m,
\end{displaymath} 
where $I^+_i$ (resp. $I^-_i$) denotes the set of variables
appearing unnegated (resp. negated) in clause ${\cal C}_i$.

Although finding an exact solution to the MAX-SAT is NP-Complete, there has 
been a significant amount of research in developing 
$\epsilon$-approximation algorithms
for the MAX-SAT. Let the optimal solution of a maximization
problem be $F^*$. 
Then, an $\epsilon$-approximation algorithm is an 
algorithm that produces, in polynomial time, a solution $F$ such that
\begin{displaymath}
 F \ge \epsilon F^* , \mbox{where $0<\epsilon <1$}. 
\end{displaymath}
The first $\epsilon$-approximation algorithm for 
MAX-SAT is described by Johnson \cite{Joh74}, where a 
$\frac{1}{2}$-approximation algorithm is presented. 
When each clause has at least $k$ literals, then the algorithm becomes
a $(1-\frac{1}{2^k})$-approximation. 
Until recently, the best 
$\epsilon$-approximation algorithms were those 
by Yannakakis \cite{Yan92} and
Goemans and Williamson \cite{GoWi:93} with $\epsilon = \frac{3}{4}$. 
Goemans and Williamson \cite{GoWi:93} proved that the
solution of the
linear relaxation of the mixed integer linear program given above
is a $\frac{3}{4}$-approximate solution.
Subsequently,
Goemans and Williamson \cite{GoeWil95} described an 
improved $.758$-approximation algorithm based on 
semidefinite programming.
In an extension of the result in \cite{GoeWil95}, 
Feig and Goemans \cite{FieGoe95} derive
a $.931$-approximation algorithm
for MAX-2SAT. 

\nocite{FieGoe95,GoeWil93,GoeWil95}

\subsection{The Feedback Vertex Set Problem}

The feedback vertex set (FVS) problem can be stated as follows: Given a
directed graph $G(V,E)$, where $V$ denotes the set of vertices ($n = |V|$)
and $E$ the set arcs, find a minimum cardinality subset $V'$ of $V$ such
that every directed cycle in $V$ contains at least one vertex in $V'$.
In other words, we wish to determine how to remove the minimum number
of vertices from the original graph
such that the resulting graph has no directed cycle.

The FVS problem can be formulated as a covering optimization problem.
Let $C_G$ denote set of all cycles in the graph $G$ and define
\begin{displaymath}
x_j = \left\{ \begin{array}{ll}
1 & \mbox{if vertex $j$ is in the feedback vertex set} \\
0 & \mbox{otherwise.}
\end{array} \right.
\end{displaymath}
The problem of finding the minimum number of vertices that need to
be removed so that the resulting graph is cycle-free can be found by
solving the following integer programming problem:
\begin{displaymath}
\min \;\; \sum_{j=1}^{n} x_j
\end{displaymath}
such that
\begin{displaymath}
\sum_{j \in C_j} x_j \geq 1, \;\; C_j \in C_G
\end{displaymath}
\begin{displaymath}
x_j = (0,1),\;\;j=1,\ldots,n .
\end{displaymath}

The FVS problem is NP-complete and several approximation algorithms have
been proposed.
The best
approximation ratio for the directed version is
$O(\log \; n \; \log \; \log \; n)$ and is
due to Seymour \cite{Seymour93}.
Other approximations can be found in Qian, Ye, and Pardalos \cite{Qian96}
and references therein.

Based on the above integer programming formulation, Goemans and Williamson
proposed an $9/4$-approximation algorithm forteh planar feedback vertex set
problem
\cite{MR98b:90156}


\nocite{MR98b:90156,Seymour93,Qian96}

\bs{ENGINEERING APPLICATIONS}
noise - ???

\bs{MISCELLANEOUS APPLICATIONS}
\label{sect:miscapp}

\subsection{Distance Matrices}

Following is from search on    semidefinite   on mathsci:


[14] 96g:15031 Johnson, Charles R.; Tarazaga, Pablo Connections between
the real positive semidefinite
and distance matrix completion problems. Special issue honoring Miroslav
Fiedler and Vlastimil Ptak.
Linear Algebra Appl. 223/224 (1995), 375--391. (Reviewer: Linda J.
Patton) 15A99 (05C50)

\subsection{Chordality and Semidefiniteness}

5] 90j:05094 Helton, J. W.; Pierce, S.; Rodman, L. The ranks of extremal
positive semidefinite matrices
with given sparsity pattern. SIAM J. Matrix Anal. Appl. 10 (1989), no.
3, 407--423. (Reviewer: R. A.
Brualdi) 05C50 (15A57)

[82] 88i:94030 Andreev, A. E. On the complexity of realization of
semidefinite matrices by gate circuits.
(Russian) Mat. Zametki 41 (1987), no. 1, 77--86, 121. (Reviewer: A.
Adam) 94C10 (68Q25)



[43] 94a:15037 Grone, Robert; Loewy, Raphael; Pierce, Stephen Nonchordal
positive semidefinite
stochastic matrices. Linear and Multilinear Algebra 32 (1992), no. 2,
107--113. (Reviewer: Marvin
Marcus) 15A51 (05C35)


95e:05085 05C50 15A99 
Shaked-Monderer, Naomi(3-QEN)
Extremal positive semidefinite matrices with given sparsity pattern.
(English. English
summary) 
Linear and Multilinear Algebra 36 (1994), no. 4, 287--292. 

\subsection{Completion Problems}

[49] 93f:15021 Dancis, Jerome Positive semidefinite completions of
partial Hermitian matrices. Linear
Algebra Appl. 175 (1992), 97--114. (Reviewer: L. Rodman) 15A57 (47A57)


[50] 93e:15008 Shaked-Monderer, Naomi; Berman, Abraham More on extremal
positive semidefinite
doubly stochastic matrices. Sixth Haifa Conference on Matrix Theory
(Haifa, 1990). Linear Algebra Appl.
167 (1992), 17--34. (Reviewer: Robert Grone) 15A51 (05C50 15A48)



\section{NUMERICAL TECHNIQUES}
\label{sect:numerics}
The current solution methods are based on p-d i-p methods - large scale
sparse issues new Kojima paper on sparse ...???? krw paper on least
squares  ???? 

\subsection{Cutting Planes}
\label{sect:cuttplanes}
good facets for e.g. max-cut ...

new results from Ramana's thesis and ....


\section{APPENDIX-Notation}
\begin{description}
\item[SDP]  
~~~~~~~~semidefinite programming problem
\item[GP]  
~~~~~~~~graph partitioning problem
\item[$\sn$]  
~~~~~~~~the space of symmetric $n \times n$ matrices
\item[${\p}_n$~or~${\p}$]  
~~~~~~~~the cone of positive semidefinite matrices in $\sn$
\item[Slater CQ]  
~~~~~~~~the Slater constraint qualification; strict feasiblity
\item[p-d i-p]  
~~~~~~~~primal-dual interior-point method
\item[$G =({\cal V}, {\cal E})$]
~~~~~~~~graph with node set ${\cal V}$ and edge set ${\cal E}$
\item[cut edge]
~~~~~~~~an edge connecting nodes in different subsets of a partition
\item[$A =(a_{ij})$]
~~~~~~~~adjacency matrix of the graph
\item[$X =(x_{ij})$]
~~~~~~~~partition matrix
\item[$w(E_{cut})$]
~~~~~~~~total weight of cut edges of the partition
\item[$w^*(E_{cut})$]
~~~~~~~~minimal total weight of cut edges over all  partitions
\item[$\Diag$]
~~~~~~~~the diagonal matrix formed from the vector
\item[$L$]
~~~~~~~~Laplace matrix of the graph
\item[$Y_X$]  
~~~~~~~~partition matrix lifted into higher dimensional matrix space
\item[$B \circ C$]
~~~~~~~~the Hadamard product of $B$ and $C$
\item[$e_k$]
~~~~~~~~the $k$-dimensional vector of ones
\item[$\bar{m}$]
~~~~~~~~$ (m_{1}, \ldots, m_{k})^{t}$
\item[$A \otimes B$]
~~~~~~~~the Kronecker product of $A$ and $B$
\item[$\kvec(X)$]
~~~~~~~~the vector formed from the columns of the matrix $A$
\item[$Y_{0,1:n^2}$]
~~~~~~~~the $n^2$ vector from the first row of $Y$
\item[$\diag$]
~~~~~~~~the vector formed from the diagonal elements
\item[$\arrow$]
~~~~~~~~the arrow operator $ \diag (Y) - (0, (Y_{0,1:n^2})^t$
\item[${\cal G}_{J}$]
~~~~~~~~the gangster operator ${\cal G}_{J}$ shoots ``holes'' in a matrix
\item[$\bar{J}$]
~~~~~~~~$\bar{J} = J \cup \{(0,0)\}$
\item[$K \lhd C$]  
~~~~~~~~$K$ is a face of $C$
\item[$\relint$]  
~~~~~~~~relative interior
\item[$\rr (B)$]  
~~~~~~~~range space of $B$
\item[$\n (B)$]  
~~~~~~~~null space of $B$
\item[$Q \preceq R$]  
~~~~~~~~$R-Q$ is positive semidefinite
\item[$\diag(A)$]
~~~~~~~~the vector formed from the diagonal of the matrix $A$
\item[$\Diag(v)$]
~~~~~~~~the diagonal matrix formed from the vector $v$
\item[$E_{n}$]
~~~~~~~~the matrix of ones in $\sn$
\item[$E_{ij}$]
~~~~~~~~the $ij$ unit matrix in $\sn$
\end{description}
\bibliography{.setcover,.qap,.psd,.master,.publs}
\end{document}