\documentclass{slides}
\pagestyle{plain}
\newcommand{\F}{{\cal F}}
\newcommand{\p}{{\cal P}}
\newcommand{\Kprod}{\otimes}
\newcommand{\Diag}{\rm Diag\,}
\newcommand{\tran}{^T}
\newcommand{\diag}{\rm diag\,}
\newcommand{\tr}{\rm trace\,}
\newcommand{\trace}{\rm trace\,}
\newcommand{\beq}{\begin{equation}}
\newcommand{\Sn}{{\cal S}^n}
\newcommand{\svec}{{\rm svec\,}}
\newcommand{\sMat}{{\rm sMat\,}}
\newcommand{\hMat}{{\rm hMat\,}}
\newcommand{\dsvec}{{\rm dsvec\,}}
\newcommand{\sdiag}{{\rm sdiag\,}}
\newcommand{\vsMat}{{\rm vsMat\,}}
\newcommand{\kvec}{{\rm vec\,}}
\newcommand{\kmat}{{\rm Mat\,}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\nc}{\newcommand}
\nc{\Hcal}{{\cal H}}
\newcommand{\rank}{{\rm rank\,}}
\newcommand{\trian}{{\rm trian\,}}
\newcommand{\Trian}{{\rm Trian\,}}
\newcommand{\BoDiag}{{\rm B^0Diag\,}}
\newcommand{\OoDiag}{{\rm O^0Diag\,}}
\newcommand{\arrow}{{\rm arrow\,}}
\newcommand{\Arrow}{{\rm Arrow\,}}
\newcommand{\bodiag}{{\rm b^0diag\,}}
\newcommand{\oodiag}{{\rm o^0diag\,}}
\newcommand{\ck}{{\cal C}_k}
\newcommand{\dk}{{\cal D}_k}
\newcommand{\uu}{{\cal U}}
\newcommand{\uk}{{\cal U}_k}
\newcommand{\vk}{{\cal V}_k}
\newcommand{\wk}{{\cal W}_k}
\newcommand{\wm}{{\cal W}_m}
\newcommand{\w}{{\cal W}}
\newcommand{\wks}{{\cal W}^s_k}
\newcommand{\wms}{{\cal W}^s_m}
\newcommand{\zk}{{\cal Z}_k}
\newcommand{\zks}{{\cal Z}^s_k}
\newcommand{\z}{{\cal Z}}
\newcommand{\n}{{\cal N}}
\newcommand{\ra}{{\cal R}}
\newcommand{\q}{{\cal Q}}
\newcommand{\s}{{\cal S}_n}
\newcommand{\m}{{\cal M}_{n}}
\newcommand{\req}[1]{(\ref{#1})}
\newcommand{\adj}{{\rm adj\,}}
\newcommand{\relint}{{\rm relint\,}}

\def\QED{~\rule[-1pt] {8pt}{8pt}\par\medskip ~~}
\begin{document}
%=======================
%=======================
\begin{slide}{}
\begin{center}
{\bf
Semidefinite Relaxations for Hard Combinatorial Problems
}
\end{center}


~~\\
~~\\
~~\\
~~\\
~~\\
~~\\
Henry Wolkowicz \\
University of Waterloo\\
Dept of Combinatorics and Optimization

~\\
~\\

\end{slide}
\begin{slide}{}

{\bf 
\begin{center}
OUTLINE
\end{center}
}

$\bullet$ Introduction to SDP \\
(geometry, duality, algorithms)

$\bullet$ Max-Cut Problem instance\\
 (quadratic boolean programming)\\
tractable relaxations versus Lagrangian duality 

$\bullet$ Other instances, e.g. QAP, GP, ...

$\bullet$ 
\underline{Theme:} - Tractable relaxation implies Lagrangian relaxation which 
can be solved efficiently using SDP. \\
       - Advantages of Lagrangian approach
(recipe for SDP relaxation).

\end{slide}
\begin{slide}{}
\begin{center}
INTRODUCTION
\end{center}
Semidefinite programming (denoted SDP) is an 
extension of linear programming (LP),
e.g. an (linear)  SDP is:
\[ 
(P)\quad  \begin{array}{rc}
   \mu^*:=  \min        &  C \bullet X  \\
     \mbox{s.t.} & {\cal A}X = b \\
                 & X \succeq 0,
    \end{array}
\]
$C,X \in \Sn$, space of symmetric $n \times n$ matrices\\
\underline{\hspace{90mm}}\\
inner product $C \bullet X = \tr CX$\\
\underline{\hspace{90mm}}\\
$A\succeq B$ if $A-B \succeq 0$ positive semidefinite\\
\underline{\hspace{90mm}}\\
\[ 
{\cal A} :\Sn \rightarrow \Re^m
\]
linear operator: $({\cal A}X)_i =\tr (A_iX)$\\
$A_i \in \Sn,~i=1, \ldots m.$


\end{slide}
\begin{slide}{}
Why use SDP?

Many applications: engineering, combinatorial optimization, statistics,
matrix completions, approximation theory, nonlinear programming, ...

\underline{\hspace{90mm}}\\

Many computationally  hard problems
can be modelled as quadratic programs.

These quadratic programs are themselves hard to solve numerically. 

But,
the Lagrangian relaxation can be solved efficiently using SDP.

\end{slide}
\begin{slide}{}

\begin{center}
{\bf Properties of  SDP}
\end{center}

SDP is a special case of the cone programming problem
\[ 
 \begin{array}{cc}
     \min        &  f(x)  \\
     \mbox{s.t.} & g(x) \succeq_K 0,
    \end{array}
\]
$K$ is a convex cone \\
$g(x) \succeq_K 0$ is cone partial order, $g(x) \in K.$ 

very general mathematical program 

e.g.  standard equality and
inequality constraints when
 $K= \Re^n_+ \otimes \Sn_+ \otimes \{0\}.$


\end{slide}
\begin{slide}{}


\begin{center}
{\bf GEOMETRY} 
\end{center}
Much of the elegant geometry of polyhedral sets
developed for LP can be extended to SDP.
(e.g.  Bohnenblust 1948, Barker-Carlson 1975 and more recently 
Lewis/98  and Pataki/98)

similarities to LP:\\
{\em self-polar}
\[
\p = \p^+:= \left\{Y: X \bullet Y \geq 0, \forall X \in  \p \right\};
\]
{\em homogeneous}\\
for any $X,Y \in \mbox{int}(\p)$,
there exists an invertible linear operator $\cal A$ that leaves $\p$
invariant and ${\cal A}(X)=Y.$



\end{slide}
\begin{slide}{}

{\em faces}
\[ {\cal F} = \left\{Y: {\cal N}(Y) \supset {\cal N}(X) 
                \right\}, \quad X \in \mbox{ relint } {\cal F}
\]

faces are {\em exposed}\\
${\cal F} =  \p \cap \phi^{\perp}$, where $\phi \in
 \p \cap {\cal F}^{\perp}$ {\em conjugate face},
(Here $\cdot^{\perp}$ denote orthogonal complement.)

But difficulties in duality theory can arise due to:

 $\p + {\cal F}^{\perp}$ is always closed

 $\p + \mbox{span}({\cal F})$ is never closed.


\end{slide}
\begin{slide}{}


\begin{center}
{\bf Duality Theory, Optimality Conditions} 
\end{center}
Extentions from LP to SDP, e.g.
Bellman and Fan 1963, but
strong duality theorems require
a Slater-type constraint qualification (strict feasibility). 

(Modified optimality conditions without CQ exit Borwein-Wolkowicz/81 and
Ramana/98.)


\end{slide}
\begin{slide}{}

\[ 
(P)\quad  \begin{array}{rc}
   \mu^*:=  \min        &  C \bullet X  \\
     \mbox{s.t.} & {\cal A}X = b \\
                 & X \succeq 0,
    \end{array}
\]
\underline{\hspace{90mm}}\\
weak duality (using hidden constraints)
\begin{eqnarray*}
 \mu^* &=& \min\limits_{X\succeq 0} \max_y C \bullet X + y^T(b-{\cal A}X)\\
       &\geq& \max_y \min\limits_{X\succeq 0}  y^Tb +\left(C -
                                  {\cal A}^*y\right) \bullet X\\
       &=& \nu^*,
\end{eqnarray*}
\underline{\hspace{90mm}}\\
${\cal A}^*$ adjoint operator of ${\cal A}$
\[  {\cal A} (X) \bullet y =
  X\bullet {\cal A}^* (y),  \quad  \forall  X, \forall y
\]
\underline{\hspace{90mm}}\\
dual program
\[ 
(D)\qquad \begin{array}{rc}
   \nu^*:=  \max &    b^T y \\
     \mbox{s.t.} & {\cal A}^*y \preceq  C 
    \end{array}
\]



\end{slide}
\begin{slide}{}


The duality theory gives rise to the
characterization of optimality
\begin{equation}
\label{eq:optcond}
\begin{array}{cccc}
           {\cal A}^{*}y +Z - C  &=&  0 & \mbox{dual feasibility} \\
          b - {\cal A}(X) &=&  0 & \mbox{primal feasibility} \\
          ZX &=&  0 & \mbox{complementary slackness} \\
       Z,X \succeq 0.
\end{array}
\end{equation}
$X,(y,Z)$ a primal-dual optimal pair. $Z$ is the (dual) slack
variable.

\underline{\hspace{90mm}}\\

  \[        ZX =  \mu I, \quad \mu >0   \]
 perturbed compl. slack. used for interior-point methods

\end{slide}
\begin{slide}{}

First and second order optimality conditions e.g. Shapiro/94,99

Nondegeneracy and strict complementarity
(Theorem of Goldman and Tucker)
do not directly
follow through from LP to SDP though generic, 
e.g. Shapiro/99, Pataki-Tuncel/98,
Alizadeh-Haeberly-Overton/98.

(strict complementarity 
for SDP translates to $Z+X \succ 0$)

Complexity/algorithms:
SDP are convex programs and fall into the class of problems that can be
approximately solved in polynomial time by int-pt algorithms, 
Nesterov-Nemirovski/93.


\end{slide}

\begin{slide}{}

\begin{center}
{\bf Tractable Relaxations of Max-Cut}\\
(quadratic boolean programming)
\end{center}
\[
(MCQ)~~~  \begin{array}{c}
   \mu^*:= \max\limits_{x \in \F} q_0(x) \quad ( : = x^TQx -2 c^Tx).
\end{array}
\]
where $\F=\left\{\pm 1\right\}^n$\\
\underline{\hspace{90mm}}\\

perturbing diagonal of $Q$ on $\F:$
\[
\begin{array}{rcl}
q_u(x)& : = &x^T(Q+\Diag(u))x -2 c^Tx - u^Te\\
      &~=&q_0(x),~~\forall x \in \F,
\end{array}
\]
where $e$ vector of ones.

\end{slide}
\begin{slide}{}
{\bf Bound 0:}
trivial bound from diagonal perturbations:
\[
  \mu^* \leq f_0 (u) := \max_x q_u(x).
\]
The function $f_0$ can take on the value $+\infty.$ 
Let 
\[S:=\left\{u:u^Te=0, Q+\Diag(u)\preceq 0\right\}.
\]
Then:
\[
\begin{array}{|c|}
\hline\\
  \mu^* \leq B_0 := \min\limits_u  f_0(u) \\
    \left(= \min\limits_{u^Te=0}  f_0(u),
       \mbox{ if } S \neq \emptyset   \right).  \\
~\\
\hline
\end{array}
\]
Using the hidden semidefinite constraint:
\[
  \mu^* \leq B_0 = \min\limits_{Q+\Diag(u) \preceq 0}  f_0(u).
\]

\end{slide}
\begin{slide}{}
{\bf Bound 1:}
relax the feasible set to
the sphere of radius $\sqrt{n}$ (tractable trust region subproblem, TRS):
\[
\mu^* \leq f_1(u):= \max_{|| x ||^2 =n} ~ q_u(x)
\]
and
\[
\begin{array}{|c|}
\hline\\
  \mu^* \leq B_1 :=\min\limits_u f_1(u).\\
~~\\
\hline
\end{array}
\]


The inner maximization problem is called a
trust region subproblem and is tractable.
This bound provides the central tool in the proofs of equivalence.

\end{slide}
\begin{slide}{}
{\bf Bound 2:} box constraint:
\[
\mu^* \leq f_2(u):= \max_{| x_i | \leq 1} ~ q_u(x).
\]
add the semidefinite constraint to make bound
tractable.
\[
  \mu^* \leq \min\limits_{u} f_2(u)
\]
and
\[
\begin{array}{|c|}
\hline\\
  \mu^* \leq B_2 :=\min\limits_{Q+\Diag(u) \preceq 0} f_2(u).\\
~~\\
\hline
\end{array}
\]


\end{slide}
\begin{slide}{}
{\bf Bound $B_1^c$:} lift to eigenvalue bound:

\[
 Q^c := \left[ \begin{array}{cc}
   0 &  - c^T \\
  - c &Q    \end{array}  \right]
\]
\[
 q^c_u(y) :=   y^T( Q^c+\diag(u))y-u^Te
\]
\[
  \mu^* \leq f_1^c(u) := \max_{||y||^2=n+1} q^c_u(y)
\]
where
\[
   \max_{||y||^2=n+1} q^c_u(y)
   = (n+1) \lambda_{\max} (Q^c + \diag (u) ) - u^Te
\]
\[
\begin{array}{|c|}
\hline\\
  \mu^* \leq B_1^c :=  \min\limits_{u} f_1^c(u).\\
~~\\
\hline
\end{array}
\]

Similarly, we get equivalent bounds $B_0^c$
and homogenized bounds for the other models.


\end{slide}
\begin{slide}{}
{\bf Bound $B_3$:} SDP bound:

After homogenization ( $c=0$), use
\[ x^TQx = \tr x^TQx = \tr Qxx^T\]
and, for $x \in \F,$ $y_{ij} = x_ix_j$ defines a
symmetric, rank one, positive semidefinite matrix $Y$ with diagonal elements 1.
Relax the rank one condition.
\[
\begin{array}{|ccc|}
\hline
&&\\
       B_3 :=&\max &\tr QY \\
 &  \mbox{~subject to~} &\diag(Y) = e \\
        && Y \succeq 0.\\
&&~\\
\hline
    \end{array}
\]



\end{slide}
\begin{slide}{}
Summary: ref. Polyak-Rendl-Wolkowicz (PRW) 1995.
(without restrictions e.g. $u^Te=0$)


\[
\begin{array}{|rcl|}
\hline
&&~\\
 B_0 &=&\min\limits_u \max\limits_x q_u(x)\\
 B_1 &=&\min\limits_u \max\limits_{x^Tx=n} q_u(x)\\
 B_2 &=&\min\limits_u \max\limits_{-1 \leq x_i \leq 1} q_u(x)\\
 B_3 &=&\max \{\tr Q^cY : \diag(Y) = e,~ Y \succeq 0. \}\\
 B_1^c &=&\min\limits_u \max\limits_{y^Ty=n+1} q^c_u(y)\\
&&~\\
\hline
\end{array}
\]


\end{slide}
\begin{slide}{}

Now replace $\pm 1$ constraints with $x_i^2=1, \forall i.$
\[
\begin{array}{ccc}
       (P_E)&\max & q_0(x)=x^TQx-2c^Tx \\
 &  \mbox{~subject to~} &
        x_i^2 = 1,~~i=1, \cdots, n.  \\
    \end{array}
\]
$B_L$ denotes Lagrangian relaxation bound.

Following our theme:
\begin{center}
\fbox{
{\bf Theorem } $B_L$ equals all above bounds.
}
\end{center}

 ref PR, PRW/95.\\
(The proofs come from exploiting strong Lagrangian duality of TRS.
More details below.)


\end{slide}
\begin{slide}{}

\begin{center}
{\bf A Strengthened SDP Bound for MC}\\
\end{center}


(ref Anjos-Wolkowicz/99 -Illustration of the recipe for SDP relaxation.
based on a
second lifting - motivated by strong duality results that follow
from adding redundant constraints of type
$XX^T$, ref. Anstreicher-Wolkowicz/98 and below)

first lifting procedure
\[ X=xx^T, \quad  \Diag X = e \]
implies second lifting procedure
\[X^2=xx^Txx^T=nX.\]
and provides an equivalent quadratic matrix model for MC

\end{slide}
\begin{slide}{}

MCQ is equivalent to:
\begin{eqnarray*}
\mu^*:=&\max& \tr QX\\
&\mbox{s.t.}&\diag(X)=e\\
&&X \succeq 0\\
&& X \mbox{ is rank 1}.
\end{eqnarray*}
which is equivalent to
\begin{eqnarray*}
\mu^*:=&\max& \tr QX\\
&\mbox{s.t.}&\diag(X)=e\\
&&X^2-nX=0
\end{eqnarray*}
Since $X$ and $X^2$ can be mutually diagonalized.\\
\underline{\hspace{90mm}}\\
Now add redundant constraints and get:
\begin{eqnarray*}
\mu^*:=&\max& \tr QX\\
&\mbox{s.t.}&\diag(X)=e\\
&&X^2-nX=0\\
&&X \circ X=E
\end{eqnarray*}
where $E$ is the matrix of ones.


\end{slide}
\begin{slide}{}

Note: $X^2=nX,~\trace X = n$ implies $X$ is rank one.
But, we cannot solve this nonconvex problem in general, i.e. we have to
look at the Lagrangian relaxation with vectors dimension $t(n).$


\end{slide}
\begin{slide}{}

Recipe for SDP relaxations:
\begin{enumerate}
\item   add redundant constraints 
\item   take Lagrangian dual 
\item   homogenize 
\item   use hidden semidefinite constraint to obtain SDP equivalent 
            {\em (check Slater's constraint qualification -
                      strict feasibility)}
\item   take Lagrangian dual again
\item   check Slater's CQ again - project if it fails
\item   delete redundant constraints
\end{enumerate}



\end{slide}
\begin{slide}{}

Notation:\\
(Interesting operators and adjoints
 --fun for me, if for no one else)

~$\bullet$ $S \in \Sn, \quad t(n)= \frac {n(n+1)}2$

~$\bullet$ $s=\svec(S) \in \Re^{t(n)} \quad$ 
vector formed (columnwise) from $S$
ignoring strictly lower triang.

~$\bullet$ $S=\sMat(s) \quad$ inverse of $\svec$

~$\bullet$ $\hMat (v) \quad$ 
is adjoint of $\svec$,
off-diagonal terms are multiplied by a half

~$\bullet$ $\dsvec (S) \quad$ is
adjoint of $\sMat$, operator 
like $\svec$ but off diagonal elements are
multiplied by 2

~$\bullet$ $\sdiag(s):= \diag( \sMat(s))$

~$\bullet$ $\vsMat(s):=\kvec(\sMat(s))$
\[ \bullet \quad 
  \vsMat^*(s)=\dsvec \left( \left(\kmat(v)+\kmat(v)^T\right)/2 \right).
\]


\end{slide}
\begin{slide}{}

start with equivalent program to MCQ:
\beq \label{eq:maxcutstrength}
 {\rm MC2} \begin{array}{ccc}
    \mu^*=
    &\max & \ \tr QX \\
  &\mbox{s.t.}& \diag(X) = e\\
     &&X\circ X=E\\
     &&X^2-nX=0,\\
\end{array}
\eeq
to efficiently apply Lagrangian relaxation and not lose
information from the linear constraint, replace the
constraint with the norm constraint $||\diag(X) - e||^2=0$.
Add $1-y_0^2=0.$

We use: $X=\sMat(x)$ is  a symmetric matrix.

\[
\begin{array}{ccc}
    &\max &  \tr \left(Q\, \sMat(x)\right)y_0 \\
  &\mbox{s.t.}& \sdiag(x)^T \sdiag(x) - 2 e^T \sdiag(x)y_0 
                  + n=0\\
     &&\sMat(x) \circ \sMat(x)=E\\
     &&\sMat(x)^2-n\, \sMat(x)y_0=0\\
     &&1-y_0^2=0.
\end{array}
\]



\end{slide}
\begin{slide}{}

take the Lagrangian dual;
Lagrange multipliers $w,T,S$
\[
 \begin{array}{lcc}
     \mu^*\leq \\
\nu_2^*:=
    \min\limits_{w,T,S}
\max\limits_{x,y_0^2=1}   \tr \left(Q\sMat(x)\right)y_0 \\
  ~~~~+w( \sdiag(x)^T \sdiag(x) - 2 e^T \sdiag(x)y_0 + n)\\
  ~~~~~~~~~~~+\tr T(E-\sMat(x) \circ \sMat(x))\\
  ~~~~~~~~~~~~~ +\tr S((\sMat(x))^2-n\, \sMat(x)y_0).
 \end{array}
\]
move variable $y_0$ into the Lagrangian
without increasing the duality gap since this is a trust region
subproblem

\[
 \begin{array}{rl}
      \nu_2^*=&
    \min\limits_{t,w,S}
\max\limits_{x,y_0}   \tr \left(Q\sMat(x)\right)y_0 \\
 &~+w( \sdiag(x)^T \sdiag(x) - 2 e^T 
                  \sdiag(x)y_0 + n)\\
 &~~+\tr T(\sMat(x) \circ \sMat(x)-E)\\
 &~~+\tr S((\sMat(x))^2-n\, \sMat(x)y_0)\\
 &~~~+ t(1-y_0^2).
\end{array}
\]

\end{slide}
\begin{slide}{}

The inner maximization of the above relaxation is an unconstrained
pure qua\-d\-r\-a\-tic maximization, i.e. 
the optimal value  is infinity unless the Hessian is negative
semidefinite {\bf (hidden constraint)} is which case $x=0$ is optimal.

Therefore we need to evaluate the Hessian of the Lagrangian.


\end{slide}
\begin{slide}{}

Using $Q \sMat(x) = x^T \dsvec(Q),$ and adding a 2 for convenience, we get
the constant part (no Lagrange multipliers) of the Hessian:
\[
 2H_c:=2\pmatrix{
  0 & \frac 12 \dsvec(Q)^T\cr
 \frac 12 \dsvec(Q)  & 0\cr
}.
\]


\end{slide}
\begin{slide}{}


nonconstant part:

Use:

$\dsvec \Diag \diag  \sMat = \sdiag^* \sdiag = \Diag \svec (I)$

rewrite the quadratic forms as follows:

\[
\begin{array}{lll}
\sdiag(x)^T \sdiag(x) = 
     x^T \left(\dsvec \Diag \diag  \sMat\right)x;\\
e^T \sdiag(x) = 
     \left(\dsvec \Diag e  \right)x;\\
~~\\
\tr S (\sMat(x))^2 = \tr  \sMat(x)\, S\, \sMat(x)\\
   ~~~~~  = x^T \dsvec\left(S \sMat(x)\right)\\
     ~~~~~= x^T \left(\dsvec S \sMat\right)x;\\
\mbox{ }\\
     \tr T(\sMat(x) \circ \sMat(x))\\
     ~~= x^T \left\{\dsvec \left(T \circ \sMat(x) \right) \right\} \\
     ~~= x^T \left(\dsvec \left(T \circ \sMat \right)\right) x.
\end{array}
\]


\end{slide}
\begin{slide}{}

use the {\em negative} of the Hessian and split it into four
linear operators with the factor 2:
\[
   \begin{array}{lll}
 2\Hcal:= 2\Hcal_1(w) + 2\Hcal_2(T)+ 2\Hcal_3(S) + 2\Hcal_4(t) \\
  ~~:=2w\pmatrix{
  0 &  (\dsvec \Diag e )^T\cr
  (\dsvec \Diag e ) & -\sdiag^* \sdiag }\\
  ~~~~~+2\pmatrix{
  0 &  0 \cr
   0 & \dsvec \left( T \circ \sMat\right) }\\
  ~~~~~~~~+2\pmatrix{
  0 & \frac 1n\dsvec(S)^T\cr
   \frac 1n\dsvec(S)
        & -\dsvec S  \sMat }\\
  ~~~~~~~~~~~+2t\pmatrix{
  1 & 0\cr
   0 & 0 }.\\
\end{array}
\]



\end{slide}
\begin{slide}{}

The matrix
$\sdiag^* \sdiag \in {\cal S}^{t(n)}$ is diagonal with elements
determined using 
\begin{eqnarray*}
e_i^T \left( \sdiag^* \sdiag \right)e_j
&=&\sdiag(e_i)^T\sdiag(e_j)\\
&=&
\left\{ \begin{array}{cc} 1 & \mbox{if } $i=j=t(k)$\\
               0  &  \mbox{otherwise.}
         \end{array}   \right.
\end{eqnarray*}
Similarly, we find that, for $T=\sum_{ij} t_{ij}E_{ij},$ where the
matrices $E_{ij}$ are the elementary matrices $e_ie_j^T+e_je_i^T,$ we have
\[
\dsvec \left( T \circ \sMat\right)= \sum_{ij} t_{ij}
                  \dsvec \left(E_{ij}\circ \sMat\right).
\]


\end{slide}
\begin{slide}{}

cancel the 2  and get the 
(equivalent to the Lagrangian dual) semidefinite program 
MCDSDP2
\[
  \begin{array}{ccc}
     \nu^*_2 =
    &\min & nw +\tr ET+\tr 0S  +t\\
  &\mbox{s.t.}& \Hcal(w,T,S,t) \succeq H_c\\
\end{array}
\]

take $T$ sufficiently positive definite and $t$ sufficiently
large, then we can guarantee Slater's constraint qualification.

the dual  of this SDP  is the strengthened SDP relaxation of MC:
\[
 {\rm MCPSDP2} \begin{array}{ccc}
     \nu_2^* =
    &\max & \trace H_cY\\
  &\mbox{s.t.}& \Hcal_1^*(Y) = n\\
  &                 & \Hcal_2^*(Y) = E\\
  &                 & \Hcal_3^*(Y) = 0\\
  &                 & \Hcal_4^*(Y) = 1\\
     && Y \succeq 0.
\end{array}
\]

we need to calculate the adjoint operators and remove redundant
constraints in MCDSDP2.


\end{slide}
\begin{slide}{}


\[  Y \cong \left( \begin{array}{c}y_0 \\ x \end{array}\right) 
                     \left( y_0 ~x^T\right), \quad
X = \sMat(x)
\]

simplified SDP relaxation MCPSDP2
\[
  \begin{array}{ccl}
    &\max & \trace H_cY\\
  &\mbox{s.t.}& \diag(Y) = e \\
  &                 & Y_{0,t(i)}=1, \quad \forall i=1, \ldots , n\\
  && \sum\limits_{k=1}^i Y_{t(i-1)+k,t(j-1)+k}\\
  &&  ~~+ \sum\limits_{k=i+1}^j Y_{t(k-1)+i,t(j-1)+i}\\
&&~~~~~      +\sum_{k=j+1}^nY_{t(i-1)+i,t(k-1)+j} \\
 && ~~~~~~~~~~-n Y_{0,t(j-1)+i}=0\\ 
    && ~~~~~~~~~~~~          \quad \forall 1\leq i < j \leq  n\\
     && Y \succeq 0, Y \in S^{t(n)+1}.
\end{array}
\]
This problem has $2t(n)-1$ constraints.



\end{slide}
\begin{slide}{}

surprise result

{\bf LEMMA}\\
Suppose that $Y$ is feasible in MCPSDP2. Then the first row
\[  \sMat \left( Y_{0,1:t(n)} \right) \succeq 0.  \]
\underline{\hspace{90mm}}\\
Proof:
Let $x=Y_{0,2:t(n)}$.
$X^2=nX$ constraint:
\[ n \sMat (x) = \sMat (x) \sMat (x) 
      =\sMat (x) x^T \sMat^*. 
\]
identify $xx^T$ with lower
right block of $Y$; get congruence of a positive
semidefinite matrix.
Alternatively: using ${\cal H}_3^*,$  and
$\dsvec (\cdot) \sMat$ is self-adjoint operator
\[ n\dsvec^* (x)
= \dsvec \bar{Y} \sMat 
= \left( \dsvec \bar{Y} \sMat \right)^*,
\]
where $\bar{Y}$ is the bottom
right block of $Y.$ Again congruence.
\QED




\end{slide}
\begin{slide}{}

\oddsidemargin -.35in
\evensidemargin -.35in
{\tiny

%\begin{table}[b]
%\begin{center}
\begin{tabular}{||c|c|c|c|c|c|c|c|c||}\hline
 $n$ & Wt & MCSDP& MCPSDP2&
 Num. \\
     & opt.& (\% rel. err) &
 (\% rel. err) & rank \\
\hline \hline
5 & 4 & 4.5225 (13.06\%) & 4.2890 (7.22\%) & 2 \\
\hline
7 & 56 & 56.4055 (0.72\%) & 56.0954 (0.17\%) & 3 \\
\hline
8 & 30 & 30.2015 (0.67\%) & 30. (e-10\%) & 1 \\
\hline
9 & 58 & 58.9361 (1.61\%) & 58.1182 (0.20\%) & 3 \\
\hline
 10&     64&  64.08 (0.1268\%) &   64 (e-08\%) &  3 \\
\hline
12 & 88 & 90.3919 (2.72\%) & 89.5733 (1.79\%) & 4 \\
\hline
\end{tabular}
%\end{center}
%\end{table}


The first line of results corresponds to
solving both MC relaxations for a 5-cycle with unit edge-weights;
the others come from randomly generated weighted graphs.

}

\end{slide}
\begin{slide}{}


Other instances:


 Trust Region Subproblem
\begin{eqnarray*}
 &\mu^*:=\min& q_0(x)\\
&\mbox{s.t.}& x\tran x - \delta^2\leq 0 \mbox{ (or } =0). \\
\end{eqnarray*}
(more general nonconvex constraints $\alpha \leq q(x) \leq \beta.$)\\
for ``$\le$," the Lagrangian dual is:
\[ 
\mbox{DTRS}\qquad
 \nu^*:=\max\limits_{\lambda \geq 0}\ \min\limits_x\ q_0(x) + \lambda 
(x\tran x - \delta^2).
\]
strong duality holds and equivalent to (ref Stern-Wolkowicz/95) the
(concave) nonlinear semidefinite program 
\begin{eqnarray*}
\mbox{DTRS}\qquad
&\nu^*:=\max& g_0\tran  (Q+\lambda I)^{\dagger} g_0 - \lambda \delta^2\\
&\mbox{s.t.}& Q+\lambda I \succeq 0\\
&&\lambda \geq  0.
\end{eqnarray*}

Again our theme holds:
if we have a tractable problem  then strong duality holds.
(tractable:- ref e.g. More-Sorensen/83)



\end{slide}
\begin{slide}{}

short proof of strong duality (e.g. A. Lewis)

WLOG TRS is nonconvex; 
smallest eigenvalue of $Q_0,$ denoted $\gamma,$ is negative:
\[
\begin{array}{rccll}
 \mu^*& =& \min\limits_{x^Tx \leq \delta^2}
       & x^T(Q_0-\gamma I)x-2c_0^tx + \gamma x^Tx\\
 &= & \min\limits_{x^Tx = \delta^2}
       & x^T(Q_0-\gamma I)x-2c_0^tx + \gamma x^tx, 
                     & \mbox{($Q_0$ is indefinite)}\\
 &= & \min\limits_{x^Tx = \delta^2}
       & x^T(Q_0-\gamma I)x-2c_0^tx + \gamma \delta^2\\
 &= & \min\limits_{x^Tx \leq \delta^2}
       & x^T(Q_0-\gamma I)x-2c_0^tx + \gamma \delta^2, &\mbox{($Q_0-\gamma
                      I$ is singular)}\\
 &=&   \max\limits_{\lambda \geq 0} \min\limits_x
       & x^T(Q_0-\gamma I)x-2c_0^tx + \lambda(x^Tx-\delta^2) + \gamma \delta^2
                  & \mbox{(convex case)}\\
 &=&   \max\limits_{\lambda \geq 0} \min\limits_x
       & x^TQ_0x-2c_0^tx +(\lambda - \gamma) (x^Tx-\delta^2)\\
 &\leq &   \max\limits_{\lambda \geq \gamma} \min\limits_x
       & x^TQ_0x-2c_0^tx +(\lambda - \gamma) (x^Tx-\delta^2)
           & \mbox{($\gamma < 0$)}\\
 &=& \nu^* \leq   \mu^*.
\end{array}
\]



\end{slide}
\begin{slide}{}

{\bf  Two Trust Region Subproblem}
TTRS consists in minimizing a
(possibly nonconvex) quadratic function subject to a norm and a
least squares constraint.

ref in SQP methods by Celis-Dennis-Tapia.

TTRS can have a nonzero duality gap, ref Peng-Yuan.

if objective not convex,
then the primal may not be attained, ref Luo-Zhang.

TRS can have at most one local and nonglobal optimum, ref Martinez.

Still an open problem whether TTRS is an NP-hard or a polynomial time
problem.


\end{slide}
\begin{slide}{}

Note: a quadratic constraint can be written as
\[  y^tPy \leq \delta  \]
after the homogenization. This is lifted to
\[  \trace PY \leq \delta. \]
Second lifting:
\[   YPY \preceq \delta Y. \]
This strictly strengthens the SDP relaxation.


\end{slide}
\begin{slide}{}


{\bf Orthogonally Constrained Programs with Zero Duality Gaps}

permutation matrices are a subset of orthogonal matrices
\[ \Pi \subset {\cal O} := \{X: X X\tran =I\} \]
(Stiefel manifold ref e.g. Edelman,Arias,Smith)

$A$ and $B$ $n\times n$ symmetric matrices
\[
\begin{array}{rcl}
{\rm QQP_O}\qquad  \mu^*:=&\min& \tr AXBX\tran\\
&{\rm s.t.}& XX\tran=I.
\end{array}
\]


\end{slide}
\begin{slide}{}

Tractable problem; can be solved using
classical Hoffman-Wielandt inequality. Provides bounds for e.g. QAP.

Proof using first application of Lagrange multipliers:
\[L(X,S)= \tr AXBX\tran + S(XX^T-I)
\]
\[ 0= \left< \nabla L(X,S),h \right> = 2 \trace AXB h^T + SXIh^T
  \quad \forall h.
\]
Therefore $AXBX^T = -S=-S^T$, i.e. $A$ and $XBX^T$ are mutually
diagonalizable. The optimal value is then 
\[ \mu^* = \sum_i \lambda_i(A) \lambda_{n-i+1}(B)
\]

\end{slide}
\begin{slide}{}


But, Lagrangian dual can have a duality gap, ref Zhao,Karisch,Rendl,Wolkowicz

Lagrangian of $(P)$
$$
L(X,S) = \tr AXBX^t + \tr SXX^t - \tr S.
$$
Lagrangian dual is
\[
\nu^* = \max_S \min\limits_X  L(X,S).
\]
The hidden constraint (Hessian is psd) yields the dual
\[
(D)
\begin{array}{ccc}
\mu^D = &\max\limits_{\hat{S}=\hat{S}^t} & -\tr \hat{S} \\ 
&  \mbox{~subject to~}  &  (B \otimes A + I \otimes \hat{S}) \succeq 0. 
\end{array}
\]


\end{slide}
\begin{slide}{}

 {A simple Example}

Consider the following $2\times 2$ example
$$
A:= \left( 
\begin{array}{cc}
1 & 0 \\
0 & 2 
\end{array} 
\right) ~~~~~~~~
B:= \left( 
\begin{array}{cc}
3 & 0 \\
0 & 4 
\end{array} 
\right).
$$
$\mu^* = 10$
$$
B \otimes A = \left( 
\begin{array}{cccc}
3 & 0 & 0 & 0 \\
0 & 6 & 0 & 0 \\
0 & 0 & 4 & 0 \\
0 & 0 & 0 & 8 \\
\end{array} 
\right).
$$
But $s_{11}\geq -3$ and $s_{22}\geq -6$;
to maximize $(D)$, equality must hold, and therefore $-\tr \hat{S} = 
9$ in the optimum. 

However, add redundant constraint $X^TX=I$.
Get $T \otimes I$ in Hessian and $-\trace T$ in objective function.
$s_{11}\geq -3-t_{11}$ 
$s_{11}\geq -4-t_{22}$ 
$s_{22}\geq -6-t_{11}$
$s_{22}\geq -8-t_{22}$
So $t_{22}=-1.$ Duality gap is closed.



\end{slide}
\begin{slide}{}


Summary: constraints $XX\tran=I$ and
$X\tran X=I$ are equivalent. Add redundant constraints.
\begin{eqnarray*}
{\rm QQP_{OO}}\qquad  \mu^O:=&\min& \tr AXBX\tran\\
&{\rm s.t.}& XX\tran=I,\ X\tran X=I.
\end{eqnarray*}
dual problem is
\begin{eqnarray*}
{\rm DQQP_{OO}}\\
\mu^O \geq \mu^D:=&\max& \tr S+\tr T\\
&\mbox{s.t.}&
(I\Kprod S)+(T\Kprod I)\preceq (B\Kprod A)\\
&& S=S\tran,\ T=T\tran.
\end{eqnarray*}

{\bf Theorem (Anstreicher-Wolkowicz/98)}
Strong duality holds for $\rm QQP_{OO}$ and $\rm DQQP_{OO},$ 
i.e.  $\mu^D=\mu^O$ and both primal and dual are attained.
\QED

Theme again holds.

\end{slide}
\begin{slide}{}
Other applications:

Weighted Sums of Eigenvalues;

Graph Partitioning Problem;

TRS like constraints $\{X: XX\tran \preceq I\}$ (ref
Anstreicher-Wolkowicz-Xin-Yuan/99)
(extension of Hoffman-Wielandt inequality)




\end{slide}
\begin{slide}{}

\begin{center}
{\bf Quadratic Assignment Problem, QAP}\\
(additional constraints)
\end{center}
\[
(QAP)~~ \begin{array}{ccc}
\mu^*:= &\min\limits_{X \in \Pi} & \tr AXBX^T - 2CX^T, \\
\end{array}
\]
$A, B$ real symmetric $n\times n$ matrices, $C$ 
real $n\times n$ matrix, $\Pi$ 
set of permutation matrices.

model for e.g.
allocating set of $n$ facilities to set of $n$ locations while
minimizing quadratic objective (distance-flow)

QAP is $N\!P$-hard and, in practice, 
problems of 
moderate sizes, such as $n=16$, are still considered very hard. 

recent surveys/books: Burkard/91, Rendl-Pardalos-Wolkowicz/93, Cellis/98???.

\end{slide}
\begin{slide}{}


Questions:
\begin{enumerate}
\item
interesting numerical and theoretical difficulties, e.g. loss of
constraint qualification and  loss of sparsity in the optimality
conditions.
\item
Can the new bound compete with other bounding techniques in speed and
quality?
\item
comparison on
the Nugent test problems?
%\item
%Can we incorporate the new bound in a branch and bound algorithm?
\item
add new facet inequalities?
\end{enumerate}

\end{slide}
\begin{slide}{}


Notation:\\

${\mathcal E} := \{ X : Xe=X^Te=e \}$\\
set of matrices satisfying {\em assignment constraints}

${\mathcal Z} := \left\{ X : X_{ij} \in \{0,1\} \right\}$ \\
set of (0,1)-matrices

${\mathcal N} := \left\{ X : X_{ij} \geq 0 \right\}$  \\
set of {\em nonnegative matrices}

${\mathcal O} := \{ X : XX^T=X^TX=I \}$\\
set of orthogonal matrices

\end{slide}
\begin{slide}{}


\[
 \Pi = {\mathcal E} \cap {\mathcal Z} = {\mathcal O} \cap {\mathcal Z} 
\]
rewrite QAP as (add redundant constraints)
\[
\begin{array}{ccl}
&\min & \tr AXBX^T - 2CX^T \\
&\mbox{~s.t.~} & XX^T =  X^TX = I \\
              && ||Xe -  e||^2=0 \\
              && || X^Te - e||^2=0 \\
        && X_{ij}^2 - X_{ij} = 0, \quad \forall i,j.\\
        &&  \diag(X_{:i}X_{:j}^T)=0, \quad \mbox{if } i \neq j\\
        &&  X_{:i}X_{:j}^T - \Diag\left(\diag(X_{:i}X_{:j}^T)\right) 
                    =0, \quad \mbox{if } i = j\\
\end{array}
\] 

\end{slide}
\begin{slide}{}


{Lagrangian Relaxation}\\
\[
\begin{array}{ll}
\mu_{\mathcal O} \geq  \mu_{\mathcal L} \\
~~~:= \max\limits_{W,u_{0},v_{0}\ldots} \min\limits_{XX^T=X^TX = I}
&\{\tr AXBX^T - 2CX^T\\
&~~+ \sum_{ij} W_{ij}(X_{ij}^2 - X_{ij})\\
&~~~+u_{0}\|Xe-e\|^{2}\\
&~~~~+v_0\|X^Te-e\|^{2}\\
&~~~~+\ldots \}.
\end{array}
\]
homogenize the Lagrangian using
scalar $x_0$ and constraint $x_{0}^{2}=1.$


\end{slide}
\begin{slide}{}

We get the lower bound\\
 (quadratic, linear constant in $X$)
\[
\begin{array}{ll}
         \max\limits_{W,S_b,S_o,u_{0}v_0,,w_{0}}  \min\limits_{X,~x_0} 
                     & \{ \tr [ AXBX^T \\
& ~~+ u_{0}\|Xe\|^2+v_0 \|X^Te\|^2 \\
& ~~~+ W(X \circ X)^T + w_0 x_0^2 \\
& ~~~~~+ S_b XX^T + S_o X^TX ] \\
& ~- \tr x_0(2C+ W)X^T\\
&~~~~ - 2x_{0}u_{0}e^T(X+X^T)e \\
&~~~~~ + \ldots \\
& ~- w_0 - \tr S_b - \tr S_o +2nu_{0}x_0^2 \}.
\end{array}
\]

Apply the hidden semidefinite constraint to get an SDP:

\[
\begin{array}{cl}
\max & - w_0 - \tr S_b - \tr S_o + \ldots \\
\mbox{~s.t.~}& L_Q +\Arrow(w) + \BoDiag(S_b) \\
            & ~~+ \OoDiag(S_o)+u_{0}D 
      + \ldots \succeq 0.
    \end{array}
\]

\end{slide}
\begin{slide}{}

check Slater's condition - OK\\
take Lagrangian dual again

\[
\begin{array}{cll}
\min &\tr L_QY \\
\mbox{~s.t.~}
  & \bodiag(Y) = I, & \oodiag(Y) = I \\
  & \arrow(Y) = e_{0}, & \tr DY=0 \\
  & \ldots \\
  & Y \succeq 0,
\end{array}
\]

check Slater's condition again - $D \succeq 0$ so it fails!!
But we can project onto the minimal face!!

Now remove redundant constraints to get simplified SDP relaxation


\end{slide}
\begin{slide}{}

simple projected relaxation with
$n^{3}-2n^{2}+1$ constraints.

\[
\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) = E_{00}  \\
 &&  R \succeq 0.  
\end{array}
\]

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}
\]


\end{slide}
\begin{slide}{}


Concluding Remarks:

In each case of a tractable bound for a nonconvex problem, the structure
allows for redundant constraints to be added to close the Lagrangian
duality gap.

What is the correct question about ``best''? Can we close or reduce the
duality gap in general? 


\end{slide}
\begin{slide}{}

\oddsidemargin -.45in
\evensidemargin -.45in
{\tiny

\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  & 3488 & 2676 & 2960 & n.a. & 3074 &  3068 & --~  & --~  \\
 Nug25  & 3744 & 2869 & 3190 & n.a. & 3287 &  3305 & --~  & --~  \\
 Nug30  & 6124 & 4539 & 5266 & 4805 & 5448 &  5413 & --~  & --~  \\
\hline
\end{tabular}
~~\\
{QAPLIB instances 1}
\end{center}


}


\end{slide}
\begin{slide}{}

\oddsidemargin -.45in
\evensidemargin -.45in
{\tiny


\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}
~~\\
{QAPLIB instances 2}
\end{center}

}

\end{slide}
\begin{slide}{}

\oddsidemargin -.35in
\evensidemargin -.35in
{\tiny

\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}
~~\\
{Numerical Results for old instances}
\end{center}

}

\end{slide}
\begin{slide}{}

\oddsidemargin -.35in
\evensidemargin -.35in
{\tiny

\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}
~~\\
{Instances for which symmetry is destroyed}
\end{center}

%\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}
%\end{center}
~~\\
Results for first level in branching tree

}


\end{slide}


\end{document}
