%\documentclass[12pt,a4paper,reqno]{amsart}
%\documentclass[11pt,a4paper,reqno,twocolumn]{amsart}
\documentclass[11pt,a4paper,reqno]{amsart}
\usepackage{amsmath,amssymb}
\usepackage{enumerate,titletoc,a4}
\usepackage{ushort,bbm}
\usepackage{graphicx}
\usepackage{arydshln}
\usepackage{booktabs}


\usepackage[pagebackref,colorlinks,linkcolor=red,citecolor=blue,urlcolor=blue,hypertexnames=true]{hyperref}


%-----
% all this is to save space

\textwidth = 6.2 in %6.5
\textheight = 9 in %8.5
\oddsidemargin = 0.0 in %.5
\evensidemargin = 0.0 in%.5
\topmargin = 0.0 in
\headheight = 0.0 in
\headsep = 0.3 in
\parskip = 0.05 in
\parindent = 0.3 in
\linespread{1.1}
%\linespread{1.05}


\setlength{\textwidth}{17cm} \setlength{\oddsidemargin}{-0.5cm}
%-------------------------------------------------------------------------



\topskip=7.5mm \setlength{\textheight}{26.8cm}
\setlength{\topmargin}{-2.1cm}



% all this is to even more agressively save space
\usepackage{mathptmx}
\usepackage{microtype}
\linespread{.99}
%igors commands

%\usepackage{showkeys}

\usepackage[svgnames,hideerrors]{xcolor}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lem}[theorem]{Lemma}
\newtheorem{thm}[theorem]{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{openproblem}[theorem]{Open Problem}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{rem}[theorem]{Remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{obs}[theorem]{Observation}
\newtheorem{example}[theorem]{Example}
\newtheorem{ex}[theorem]{Example}
\newtheorem{war}[theorem]{Warning}

\renewcommand{\subset}{\subseteq}
\renewcommand{\qedsymbol}{\rule[.12ex]{1.2ex}{1.2ex}}
\newcommand{\N}{\mathbb N}
\newcommand{\mbB}{\mathbb B}
\newcommand{\mbD}{\mathbb D}
\newcommand{\mbS}{\mathbb S}
\newcommand{\sohs}{\Sigma^2}
\newcommand{\sohsq}{\Sigma^2_q}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\ii}{\mathbbm i}
\newcommand{\jj}{\mathbbm j}
\newcommand{\kk}{\mathbbm k}
\newcommand{\HH}{\mathbb H}
\newcommand{\cP}{\mathcal P}
\newcommand{\cV}{\mathcal V}
\newcommand{\cU}{\mathcal U}
\newcommand{\cs}{{\mathcal{S}}}
\newcommand{\ck}{{\mathcal{K}}}
\newcommand{\cn}{{\mathcal{N}}}
\newcommand{\cc}{{\mathcal{C}}}
\newcommand{\f}{{\mathcal{F}}}
\newcommand{\g}{{\mathcal{G}}}
\newcommand{\CP}{{\mathcal{CP}}}
\newcommand{\COP}{{\mathcal{COP}}}





\newcommand{\raux}{\R\langle\ushort X\rangle}



\def\nd{\noindent}
\def\Diag{\mathrm{Diag}}
\def\diag{\mathrm{diag}}

%=========================================================
%DANGER
%=========================================================

\DeclareFontFamily{OT1}{manual}{}
\DeclareFontShape{OT1}{manual}{m}{n}{ <10> manfnt }{}
\newcommand*{\danger}{\raisebox{2.5ex}{\usefont{OT1}{manual}{m}{n}\symbol{"7F}}}

\newcommand*\dremark[1]{{{\color{red}\textbf{$\dagger$}}\marginpar{%
\parbox{\marginparwidth}{\flushleft%
{\color{red}\danger{\tiny#1}}}}}
}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\newcommand{\K}{\R}
\renewcommand{\l}{\ell}

\newcommand{\ncSOStools}{\href{http://ncsostools.fis.unm.si/}{{\tt NCSOStools}} }
\newcommand{\ncSOStoolz}{\href{http://ncsostools.fis.unm.si/}{{\tt NCSOStools}}}


\newcommand{\ep}[0]{\varepsilon}
\newcommand{\eps}[0]{\varepsilon}
\newcommand{\rh}[0]{\varrho}
\newcommand{\ual}[0]{\ushort{\alpha}}
\newcommand{\al}[0]{\alpha}
\newcommand{\bet}[0]{\beta}
\newcommand{\ga}[0]{\gamma}
\newcommand{\om}[0]{\omega}
\newcommand{\ta}[0]{\tau}
\newcommand{\ph}[0]{\varphi}
\renewcommand{\th}[0]{\vartheta}
\newcommand{\de}[0]{\delta}
\newcommand{\ze}[0]{\zeta}
\newcommand{\ch}[0]{\chi}
\newcommand{\et}[0]{\eta}
\newcommand{\io}[0]{\iota}
\newcommand{\la}[0]{\lambda}
\newcommand{\si}[0]{\sigma}

\newcommand{\Ga}[0]{\Gamma}
\newcommand{\De}[0]{\Delta}
\newcommand{\Th}[0]{\Theta}
\newcommand{\La}[0]{\Lambda}
\newcommand{\Si}[0]{\Sigma}
\newcommand{\Ph}[0]{\Phi}
\newcommand{\Ps}[0]{\Psi}
\newcommand{\Om}[0]{\Omega}
\newcommand{\can}[1]{{[#1]}}
\newcommand{\dual}{{\rm(DSDP$_{\rm eig-min}$)}}

\newcommand{\df}[1]{\emph{#1}}

\newcommand{\bO}{\mathbf{0}}
\newcommand{\x}{\mathbf{x}}
\newcommand{\y}{\mathbf{y}}
\newcommand{\z}{\mathbf{z}}
\newcommand{\uu}{\mathbf{u}}
\newcommand{\vv}{\mathbf{v}}
\newcommand{\ww}{\mathbf{w}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bE}{\mathbf{E}}
\newcommand{\bJ}{\mathbf{J}}
\newcommand{\bI}{\mathbf{I}}
\newcommand{\bm}{\mathbf{m}}
\newcommand{\ff}{\mathbf{f}}
\newcommand{\bal}{\mathbf{\alpha}}
\newcommand{\bbet}{\mathbf{\beta}}
\newcommand{\B}{\mathcal B}
\newcommand{\cW}{\mathcal W}
\newcommand{\cD}{\mathcal D}
\newcommand{\cN}{\mathcal N}
\newcommand{\bD}{\mathbb D}
\newcommand{\cA}{\mathcal A}
\newcommand{\cC}{\mathcal C}
\newcommand{\cB}{\mathcal B}
\newcommand{\bB}{\mathbb B}
\renewcommand{\L}{\mathcal L}
\newcommand{\cS}{\mathbb S}
\newcommand{\csim}{\stackrel{\mathrm{cyc}}{\thicksim}}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\ran}{Ran}
\DeclareMathOperator{\re}{Re}
\DeclareMathOperator{\eig}{eig}
\DeclareMathOperator{\rc}{rc}
\DeclareMathOperator{\mindeg}{mindeg}
\DeclareMathOperator{\cdeg}{cdeg}
\DeclareMathOperator{\mincdeg}{mincdeg}
\DeclareMathOperator{\im}{Im}
\DeclareMathOperator{\tr}{trace}
\DeclareMathOperator{\sym}{Sym}
\DeclareMathOperator{\card}{card}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\relint}{rel\,int}
\DeclareMathOperator{\convcone}{conv\,cone}
\DeclareMathOperator{\vvec}{\mathrm{vec}}
\DeclareMathOperator{\New}{\mathbf{New}}



\def\ben{\begin{enumerate} }
\def\een{\end{enumerate} }


\def\beq{\begin{equation} }
\def\eeq{\end{equation} }



\newcommand{\dd}[2]{\genfrac{}{}{0pt}{}{#1}{#2}}

\newcommand{\Abullet}{\hspace{10pt} \raisebox{2pt}{\scriptsize{\textbullet}}}
\newcommand{\abullet}{\raisebox{0.5pt}{\scriptsize{\textbullet}}}


\title[FROM COMBINATORIAL OPTIMIZATION TO REAL ALGEBRAIC GEOMETRY AND BACK]{FROM COMBINATORIAL OPTIMIZATION TO REAL ALGEBRAIC GEOMETRY AND BACK $^{*}$}


\author[Janez Povh]{Janez Povh}\address{Janez Povh, Fakulteta za informacijske \v studije v Novem mestu, Ulica talcev 3, 8000 Novo
mesto, Slovenia}
\email{\small janez.povh@fis.unm.si}
\thanks{$^*$Supported by  Slovenian research agency  via program P1-0383 and project L74119 and by
Creative Core FISNM-3330-13-500033 `Simulations' project funded by the European Union.}


\subjclass[2010]{Primary 90C22, 90C27, 14P10; Secondary 13J30, 15B48}

\date{\today}
\keywords{combinatorial optimization,
copositive programming, semidefinite programming, polynomial optimization, sum of squares, real algebraic geometry}

\begin{document}


\setcounter{tocdepth}{2}
\contentsmargin{2.55em}
\dottedcontents{section}[3.8em]{}{2.3em}{.4pc}
\dottedcontents{subsection}[6.1em]{}{3.2em}{.4pc}
\dottedcontents{subsubsection}[8.4em]{}{4.1em}{.4pc}
%
%\makeatletter
%\newcommand{\mycontentsbox}{%
%{\centerline{NOT FOR PUBLICATION}
%\small\tableofcontents}}
%\def\enddoc@text{\ifx\@empty\@translators \else\@settranslators\fi
%\ifx\@empty\addresses \else\@setaddresses\fi
%\newpage\mycontentsbox}
%\makeatother
%

\begin{abstract}
In this paper we explain the relations between combinatorial optimization and real algebraic geometry with a special focus to Quadratic assignment problem. We demonstrate how to write a quadratic optimization problem over discrete feasible set as a linear optimization problem over the cone of completely positive matrices. The later formulation enables hierarchy of approximations which rely on results from polynomial optimization, a sub-field of real algebraic geometry.
\end{abstract}
\maketitle




\section{Introduction}\label{sec:intro}



In combinatorial optimization the main task is to find optimum of given objective function over a
subset of finite combinatorial set, which is usually the set of all subsets of given universal set, the set of all permutations, combinations etc. Solving
the most interesting problems usually requires complete enumeration,
i.e. checking all feasible solutions, which might be time-consuming.
A typical approach to overcome the complexity obstacles is to
reformulate the problem in such a way that the cost function becomes
linear and the feasible set becomes some discrete subset of $\R^n$.
The next step usually consists of embedding the feasible set into a
convex subset of $\R^n$ which enables the application of efficient
methods from convex optimization. We may always choose the convex
superset in such a way that it is  an
 intersection of a convex
cone and a linear subspace. If the cone is well-equipped (i.e. we can
find  a self-concordant barrier function for the cone), then the
resulting conic program can be solved to a precision $\varepsilon$ in
polynomially many iterations, where the number of iteration is also polynomial function of $\log \varepsilon$ \cite{Ren:01}. This approach usually gives only lower
or upper bounds for the optimum of the original problem but these bounds
may be used to reduce the initial feasible set significantly or to reduce the branching tree at Branch and Bound
method.

Relaxations, which result in linear programming problems, were
intensively studied in the past decades because  many efficient algorithms
exist to solve them. For several problems, e. g. quadratic $0-1$ problems,
there is no reasonable linear approximation of the feasible set and
if we want to get tight bounds we have to use
 methods from nonlinear programming. These methods are widely
 considered much harder to implement and the size of instances that we
 can solve with them is much more limited.

In the last two decades a significant progress in the optimization
over the cone of positive semidefinite matrices has been made. The
results about this topic are gathered under the name
\df{semidefinite programming} (SDP).
Now we share a good understanding of the geometry in SDP
\cite{DeKlerk:02,WoSaVan00,AnjLas:11} and have a variety of efficient SDP solvers
which are based on the interior point concept
(\cite{DeKlerk:02,GaMatou:12,Ren:01,WoSaVan00} or on other concepts such us
bundle method  (\cite{He:00,FiGrReSo:06}) and Augmented Lagrangian
method \cite{PoReWi:06,MaPoReWi:09}.

Semidefinite programming has attained an important role in
combinatorial optimization. We point out two reasons why this
happened. The first is the efficiency of the methods for solving
semidefinite programs. The second reason is the strong evidence that
many semidefinite models are significantly stronger than the purely
linear ones, justifying the additional computational costs to solve
them.




Optimization of linear function over the cone of copositive or
completely positive matrices is called \df{copositive
programming}.\index{copositive programming} Recently several authors
have highlighted the importance of copositive programming in
combinatorial optimization
\cite{DePa:02,PoRe:07,Bu:09,EiPo:13,DiPoEi:13}. It has been shown
that the feasible sets for some hard combinatorial problems (like
stability number problem, quadratic assignment problem, graph
partitioning problem) may be represented as the intersection of a
linear space and the cone of copositive or completely positive
matrices. This does not make the problems tractable since the
separation problem for the copositive cone is NP hard \cite{DiGi:14}, but opens many new possibilities to
construct approximation schemes for the problems.

When we try to find advanced approximation of copositive programming problems we naturally meets the real algebraic geometry.
This is a very rich field within algebra which mainly studies solution sets of a given finite set of polynomial equalities and inequalities, so called semi-algebraic sets.
Basic questions that are studied within this area are if the given semialgebraic set is empty, bounded, connected, ...
Polynomial optimization is a subfield of real algebraic geometry and is focused to optimization problems where one want to find optimum of a real polynomial $f(\x)$ over the feasible set defined by polynomial inequalities:
\begin{equation}\label{eq:1}
                            f_K^{\inf}  =  \inf\{f(\x)\colon \x\in K\},~~\mbox{where}~~
 K=\{\x\in\R^n\colon g_i(\x)\ge 0~\mbox{for}~i=1,\ldots,k\}.
\end{equation}

Problem \eqref{eq:1} covers all well-known combinatorial problems, hence is in general hard to solve. In the last two decades approach based on sum-of-squares (SOS) and the dual moment idea became very promising. The SOS approach relies on fact that if $f$ can be written as $s_0+\sum_i s_ig_i$ where $s_i$  are non-negative on $K$ then $f$ is non-negative on $K$. The largest $\varepsilon$ such that $f-\varepsilon=s_0+\sum_i s_ig_i$ is  a lower bound for optimum of \eqref{eq:1}. If we consider $s_i$ that are SOS we obtain SDP approximations for \eqref{eq:1}, if
we consider $s_i$ which are polynomials with non-negative coefficient (this is sufficient if $K$ is a subset of a non-negative orthant) then we get LP approximations for \eqref{eq:1}.


Results that relate positivity of polynomial functions to
algebraic representations of these functions are known as \emph{Positivstellensatz} \cite{MaNe:12}. In the real algebraic geometry people also use term \emph{Nichtnegativestellensatz} for results about algebraic certificates for non-negative polynomials. Some people use these two names only for theorems that are ``if and only if'', see e.g. Scheiderer \cite{Scheiderer_09}.
In this paper we call a \emph{Positivstellensatz} any result which provides algebraic certificates for positivity (or non-negativity) for positive polynomials.

We consider as the most famous Positivstellens\"{a}tze the results of  P\'olya~\cite{Po:29,Hardy_Littlewood_Polya_1988}, Schm\"udgen  \cite{Schm:91} and Putinar \cite{Pu:93}. P\'olya proved (see Theorem \ref{thm:polya} below) that if given real homogeneous polynomial $f$ is positive on $\R_+^n\setminus\{\bO\}$ then multiplying it with $(\sum_i x_i)^r$ , where  $r$ is sufficiently large, gives polynomial with non-negative coefficients, i.e. a certificate that  the original polynomial is nonnegative on $\R_+^n$. There exist also a ``positive'' version of the P\'olya's theorem stating that all coefficients of $(\sum_i x_i)^rf$ are positive for $r$ sufficiently large \cite{PowRez:01}.

 Theorems of Schm\"udgen \cite{Schm:91} and Putinar \cite{Pu:93} show that (i) if the semialgebraic set $K$ is compact then $f$ belongs to the preordering generated by $\{g_i\}$ (Schm\"udgen) and (ii) if the quadratic module generated by $\{g_i\}$ is Archimedean then $f$ belongs to this module (Putinar). For definitions and details about this results we suggest the reader to consider \cite{Laur:09}. In both cases we do not have ``if and only if'', i.e. we only have certificates for non-negativity. For complexity issues related with Schm\"udgen and Putinar Positivstellens\"{a}tze see~\cite{Sch:04,NiSch:07}, while a comprehensive overview of this type of results can be found in ~\cite{Scheiderer_09,MaNe:12}.

The P\'olya's Positivstellensatz therefore implies non-negativity certificate based on polynomials with non-negative coefficients while Schm\"udgen's and Putinar's theorems guaranty non-negativity certificates  that are based on polynomials which are SOS.


\subsection{Notation}


We denote the vector
of all ones by $\be_n\in\R^n$ (or $\be$ if the dimension $n$ is obvious).
The square matrix of all ones is $\bJ_n$
(or $\bJ$), the identity matrix is $\bI$.
 When we consider
matrix $A\in\R^{m\times n}$ as a vector from $\R^{mn}$ obtained from $A$ column-wise, we write
this vector as $\vvec(A)$.

In this paper we consider the following sets of matrices:
 \begin{itemize}
\item The vector space of real symmetric $n\times n$ matrices:
 $\cs_n= \{X\in \R^{n\times n}: X=X^T \}$,
 \item the cone of $n \times n$ symmetric nonnegative matrices:
$\cn_n = \{ X\in \cs_n\colon x_{ij}\geq 0, \forall i,j \}$,
 \item the cone of
$n\times n$ positive semidefinite matrices: $\cs^+_n = \{ X\in
\cs_n\colon y^TXy\geq 0, \forall y \in \R^n \}$.
 \item  the cone of
$n\times n$ copositive matrices: $\COP_n = \{ X \in \cs_n\colon
\x^TX\x\geq 0, \forall \x \in \R^n_+ \}$,
 \item the cone of $n\times n$
completely positive matrices:
$\CP_{n}= \mbox{conv}\{ \x\x^{T}: \x \in
\R^{n}_{+} \},$ where $\mbox{conv}(A)$ stands for the convex hull of $A$.
\end{itemize}



We also use $X\succeq 0$ for $X\in\cs_n^+$ and $X\ge 0$ for $X \in\cn$. A   linear optimization problem over $\cn_n$ is a linear programming problem while a linear optimization problem over $\cs_n^+$ is called a
semidefinite programming problem. Linear optimization problem over the cone of copositive or completely positive matrices is a copositive programming problem.

The sign $\otimes$ stands for Kronecker product.  If $a\in\R^n$, then $\mbox{Diag}(a)$ is a $n\times n$
diagonal matrix with $a$ on the main diagonal and $\diag(X)$ is a vector containing the
main diagonal of a square matrix $X$.

For a matrix  $Z\in  \cs_{k^2}$, with $k\ge 1$, we often use the
following block  notation:
\begin{equation}\label{eq:A_block_pq}
Z = \left[
\begin{array}{ccc}
Z^{11} & \cdots &Z^{1k}\\
\vdots&\ddots & \vdots\\
Z^{k1}& \cdots & Z^{kk}
\end{array}
\right],
\end{equation}
\nd where $Z^{ij}\in\R^{k\times k}$.

When $P$ or $P_{subscript}$ is the name of the optimization problem, then $OPT_P$ or $OPT_{subscript}$, respectively, denote
their optimal values.


If $f\in\R[\x]$ is a polynomial with real coefficients we say that $f$ is sum of squares (SOS) if there exist polynomials $s_i\in\R[\x]$ such that $f(\x)=\sum_is_i^2(\x)$.


\subsection{Contribution}
In this paper we
\begin{itemize}
\item clearly explain how the combinatorial optimization naturally meets with real algebraic geometry via copositive programming;
\item list the results from real algebraic geometry that have straightforward implications for combinatorial optimization;
\item demonstrate contributions in approximate solving the combinatorial optimization problem \ref{eq:qap1} by results from real algebraic geometry.
\end{itemize}



\section{Combinatorial optimization}
Following \cite{Schr:05} one of the first studied combinatorial optimization problems is assignment problem. It was studied as a continuous optimization problem under the name \emph{transportation problem} already in 1784 by G. Monge \cite{Schr:05}.
The original version, now known as linear assignment problem \ref{eq:lap}, asks how to assign e.g. workers to tasks such that the total time (or cost) for all tasks is minimum.
Suppose we have $n$ workers and $n$ tasks and we construct a  matrix $C\in\R^{n\times n}$ such that $c_{ij}$ is the cost of doing task $j$ by worker $i$.
With this notation \ref{eq:lap} can be written as
\begin{equation}\label{eq:lap}
\tag*{(LAP)}
OPT_{LAP}=\min\{\sum_{i,j}c_{i,\varphi(i)}\colon \varphi~\mbox{a parmutation}\}.
\end{equation}

We can describe each permutation $\varphi$ of order $n$ by $0-1$ matrix $X^{\varphi}$ of order $n$ (we call such matrix a \emph{permutation matrix}:
\begin{equation*}
X^{\varphi}_{ij}= 1 \iff \varphi(i)=j.
\end{equation*}
Every permutation matrix is a $0-1$ matrix which has  in each row and column exactly one non-zero (equal to 1).
Therefore \ref{eq:lap} can be rewritten as
\begin{equation*}
OPT_{LAP}=\min\{\tr(C^TX)\colon X~\mbox{a parmutation matrix}\}.
\end{equation*}

Note that the set of all permutation matrices $\Pi$ can we described in different ways:

\begin{eqnarray*}
\Pi & = &\{X\colon X_{ij}\in\{0,1\}, X\be = X^T\be = \be\} \\
& = & \{X\colon X\ge 0,~X^TX=\bI\}.
\end{eqnarray*}

Indeed, if the row and column sums of $0-1$ matrix are equal to 1, then there must be in every row and column exactly one nonzero (equal to 1). This explains the first representation.
For the second representation note that if $X\ge 0$ has orthogonal columns and rows this means that in every row and column there is at most one nonzero (positive) element. It must be equal to 1 since the (Euclidean) norm of each row and column must be 1.

Using the first representation of permutation matrices we can formulate \ref{eq:lap} as follows:

\begin{equation}\label{eq:lap1}
\tag*{(LAP')}
OPT_{LAP}=\min\{\langle C,X\rangle\colon X_{ij}\in\{0,1\}, X\be = X^T\be = \be \}
\end{equation}

\nd where $\langle\cdot,\cdot\rangle$ stands for the standard inner product, i.e.
$\langle X,\, Y\rangle = \tr(X^TY)$ for $X,Y\in\R^{m\times n}$.


We can solve \ref{eq:lap} very efficiently (theoretically and practically) using several optimization methods. The most efficient are so-called primal-dual methods. They are based on the fact that replacing the $0-1$ constraint  in \ref{eq:lap1} by $X\ge 0$ does not change the optimal solution of \ref{eq:lap}, since the convex set, spanned by all permutation matrices, is exactly the convex hull of feasible set from \ref{eq:lap1} after the replacement.

The most famous primal-dual method to solve \ref{eq:lap} is Hungarian method, which was introduced in 1955 by Harold Kuhn \cite{Ku:55} and was at that time the first method with known polynomial complexity to solve \ref{eq:lap}. Kuhn named the method after two Hungarian mathematicians Egerv\'ary and K\"{o}nig, whose results he used to construct the method.
Currently the Shortest augmenting path method is considered the most efficient method to solve \ref{eq:lap}.
We can solve \ref{eq:lap} also by using any method for solving linear programming since \ref{eq:lap1} becomes a linear programming problem if we replace $X_{ij}\in\{0,1\}$  by $X_{ij}\ge0$. See also \cite{Po:08}.


The quadratic assignment problem \ref{eq:qap1} is a generalization of linear assignment problem.
It was introduced to model the location problems which take into account the costs of placing new facilities on certain places and the interaction between all facilities.
It became a standard problem in
location theory and is very famous because of its hardness. Koopmans
and Beckmann \cite{KoBe:57} introduced it in 1957 in the following
form:


\begin{equation}\label{eq:qap1}
\tag*{(QAP)}
   OPT_{QAP}~=~\min \ \{ \sum_{i,j}a_{ij}b_{\pi(i)\pi(j)}+
\sum_{i}c_{i,\pi(i)}\colon
\pi~\mbox{a~permutation}\},
\end{equation}

\nd where $A,B,C$ are $n\times n$ matrices. We assume (this is a standard
assumption) that $A$ and $B$ are symmetric.
Using similar approach as above (we use the second representation for permutation matrices) we can rewrite
\begin{equation}\label{eq:qap2}
\tag*{(QAP')}
   OPT_{QAP}~=~\min \ \{ \langle X,\,AXB+C\rangle\colon  X\ge 0,~X^TX=\bI\}.
\end{equation}

\ref{eq:qap1} is known to be very hard from a theoretical and practical point
of view.
 Problems of size $n\ge 25$ are currently still considered as difficult.
Sahni and Gonzales \cite{SaGo:76} showed that even finding an
$\varepsilon$-approximate solution for \ref{eq:qap1} is NP-hard. Solving \ref{eq:qap1} in
practice is usually based on the Branch and Bound (B$\&$B) algorithm.
The performance of B$\&$B algorithms depends on the computational
quality and efficiency of  lower bounds (see \cite{An:03} for a
summary of recent advances in the solution of \ref{eq:qap1} by B$\&$B). The
study of lower bounds for \ref{eq:qap1} is therefore very important for the
development of B$\&$B algorithms.
We propose the following surveys about  \ref{eq:qap1}
\cite{Ce:98,Re:02,Hahn:06}.

The most recent and promising trends of research for the bounding
methods for \ref{eq:qap1} are based on semidefinite programming.
 Zhao et al., Sotirov and Rendl \cite{ReSo:07,ZaKaReWo:98} lifted the problem from
the vector space $\R^{n\times n}$ to the cone of positive semidefinite matrices of order $n^2+1$ and formulated
several semidefinite relaxations  which give increasingly tight lower bounds for \ref{eq:qap1}. They
used interior point methods \cite{ZaKaReWo:98} and the bundle method
\cite{So:06} to solve these programs. The computational results show that
these lower bounds are among the strongest known but  also the most
expensive to compute (state-of-the-art computers could compute the strongest of these  bounds  only for $n\le 35$).

Recently De Klerk and Sotirov \cite{DeKlSo:10} exploited the symmetries in some special instances   of \ref{eq:qap1} and solve these instances for size up to 128.

A new direction in solving \ref{eq:qap1} was started when it was shown that \ref{eq:qap1} can be formulated as a linear programming problem over the cone of copositive or completely positive matrices.
 More precisely, starting with \ref{eq:qap2} where few initially redundant constraints were added
\begin{equation}\label{eq:qap3}
\tag*{(QAP'')}
   OPT_{QAP}~=~\min \ \{ \langle X,\,AXB+C\rangle\colon  X\ge 0,~X^TX=XX^T=\bI,~\langle X,\bJ X\bJ\rangle=n^2\}
\end{equation}
Povh and Rendl showed that the Lagrangian dual of \ref{eq:qap3} is a copositive programming problem with zero duality gap.
The conic dual of this Lagrangian dual has the following formulation

\begin{equation}\label{eq:qap4}
\tag*{($QAP_{\CP}$)}
\begin{array}{llrcl}
 &\min & \multicolumn{3}{c}{\langle B\otimes A+\Diag(c),Y \rangle}  \\
&\mathrm{s.\ t.} &   \sum_iY^{ii} & = & \bI, \\
&&  \langle \bI,\,Y^{ij}\rangle & = &\delta_{ij},\ \forall i,j,\\
& \multicolumn{2}{r}{\langle \bJ_{n^2},\,Y\rangle} &  = &n^2,\\
&  \multicolumn{2}{r}{Y} &\in & \CP_{n^2},
\end{array}
\end{equation}
where $c=\vvec(C)$.

In this formulation we introduced the cone of completely positive matrices $\CP$.
Its dual is the cone of copositive matrices. Both cones are defined in Introduction.
Formulation \ref{eq:qap4} means that \ref{eq:qap1} can be restated as a linear programming problem over the cone of completely positive matrices. We call such a problem a copositive program (we use the same name for a linear programming problem over $\COP$).

The copositive programming formulation \ref{eq:qap4} together with the copositive formulation of the \emph{stability number problem} \cite{DePa:02} inspired several generalizations.
Burer \cite{Bu:09} proved that every quadratic optimization problem over the non-negativity orthant with linear and binary constraints can be formulated as copositive program.
Dickinson et al.  \cite{DiPoEi:13} generalized this result to hold for every quadratic  optimization problem over the closed set subject to linear and binary constraints if this closed  set satisfies some technical assumption (like being bounded or being  convex).

Although the strong membership problem for the cones $\CP$ and $\COP$ are NP-hard \cite{DiGi:14} the reformulation \ref{eq:qap4} is important since any reasonable approximation for the cone $\CP$ yields approximation for $OPT_{QAP}$.

The definition of $\COP$ is strongly related to positivity of certain real polynomials, hence we can use the real algebraic tools to get approximations for $\CP$ and $\COP$.

\section{Real algebraic geometry}

Checking whether given real symmetric matrix $A$ is copositive is directly linked to a question if the corresponding polynomial $f_A(\x)=\sum_{i,j}a_{ij}x_ix_j$ has non-negative infimum on non-negative orthant. The question can be restate as constrained or unconstraint optimization problem:
\begin{equation}\label{eq:2}
A\in\COP \iff \inf_{\x\in\R_+^n} \sum_{i,j}a_{ij}x_ix_j\ge 0\iff \inf_{\z\in\R^n} \sum_{i,j}a_{ij}z_i^2z_j^2\ge 0.
\end{equation}
Indeed, if $A$ is copositive than $\sum_{i,j}a_{ij}x_ix_j$ is non-negative on the non-negative orthant, hence   $\inf_{\z\in\R^n} \sum_{i,j}a_{ij}z_i^2z_j^2\ge 0$.
To see the reverse direction we use the trivial fact that every $\x\ge 0$ can be represented by  $x_i=z_i^2$ for some $\z\in\R^n$.

Any sufficient and tractable condition that guaranties  non-negative infimum of the constrained or unconstrained  problem in \eqref{eq:2} can lead to efficient inner approximation of $\COP$. Similarly necessary conditions yield outer approximations of $\COP$.

One of the very first results from real algebraic geometry yielding sufficient conditions for copositivity (now regarded as Positivestellensatz) is due to P\'olya.
\begin{thm}(P\'olya, 1929, Hardy, Littlewood, P\'olya, 1988)\label{thm:polya}
Let $f\in\R[\x]$ be a homogeneous polynomial on $\R^n$ such that $f(\x)>0$ for all $\x\in\R_+^n\setminus\{\bO\}$. Then for some $r\in\N$, we have that all the coefficients of $(\be^T\x)^rf(\x)$ are non-negative.
\end{thm}

Powers and Reznick \cite{PowRez:01} proved stronger result. If $r$ is larger than a certain number which depends only on the degree of $f$ and its minimum  on the standard simplex then all coefficients of $(\be^T\x)^rf(\x)$ are positive, hence the P\'{o}lya's theorem is actually ``if and only if''.

This theorem motivated Parrilo \cite{Pa:00,Pa:03} to introduce the following hierarchy of inner approximations for $\COP$:
\begin{equation}\label{eq:3}
\cc^0\subset \cc^1\subset \cdots\subset \COP
\end{equation}
where $\cc^r$ is defined as follows
\begin{equation*}\label{eq:4}
\cc^r=\{A\in\cS_n\colon (\sum_i x_i^2)^r(\sum_{i,j}a_{ij}x_i^2x_j^2)~\mbox{has non-negative coefficients}\}.
\end{equation*}



Another well known Positivstellensatz is the following theorem from Reznick.
\begin{thm}[{\cite{Reznick_1995}}]\label{thm:reznick}
 Let $f\in\R[\x]$ be a homogeneous polynomial of even degree on $\R^n$ such that $f(\x)>0$ for all $\x\in\R^n\setminus\{\bO\}$. Then for some $r\in\N_+$, we have that $(\x^T \x)^rf(\x)$ is SOS.
\end{thm}

Faybusovich \cite[Theorem 1]{Fay:04} provided an explicit bound for the exponent $r$ in the theorem above.
This theorem probably motivated  Parrilo \cite{Pa:00} to introduce also the following hierarchy
\begin{equation}\label{eq:5}
\ck^0\subset \ck^1\subset \cdots\subset \COP
\end{equation}
where $\ck^r$ is defined as follows
\begin{equation*}\label{eq:6}
\ck^r=\{A\in\cS_n\colon (\sum_i x_i^2)^r(\sum_{i,j}a_{ij}x_i^2x_j^2)~\mbox{is SOS}\}.
\end{equation*}

The dual cones $\ck^{r*}$ form a decreasing hierarchy approximating $\CP$ from the outside.

Hierarchies \eqref{eq:3} and \eqref{eq:5} are important because separation problems over the cones in these hierarchies can be done with linear and semidefinite programming, respectively.
Indeed, the cone $\cc^0$ is the set of symmetric matrices which are non-negative component-wise.
Similarly the cone $\ck^0$ consists of symmetric matrices which are sum of a non-negative and a positive semidefinite matrix while $\ck^{0*}$ contains exactly the matrices which are positive semidefinite and non-negative \cite{Pa:00,DePa:02}.
For higher members in the hierarchies above we again obtain descriptions which rely of positive semidefinitness and component-wise non-negativity.
Note that if we consider matrices of order $\le 4$ then $\ck^0=\COP$ \cite{dia:62}.

Several results about certificates for non-negativity of polynomials over feasible sets defined by polynomial equalities and inequalities (like $K$ from \eqref{eq:1}) have been published in last two decades. We mention the famous Positivestellensatz from Putinar and Vasilescu.
\begin{theorem}[{\cite[Theorem~1]{Putinar_Vasilescu_1999}}]\label{Thm:PosPV}
Let $m\in\N,~m\ge 1$ and $f_0,\ldots,f_m\in\R[\x]$ be homogeneous polynomials of even degree on $\R^n$ such that $f_0(\x)>0$ for all non-zero $\x\in\{\x\colon f_1(\x)= 1,~f_i(\x)\ge 0~\forall i\ge 1  \}$.
Then for some $r\in\N$, there exists homogeneous SOS polynomials $g_1,\ldots,g_m\in\R[\x]$ such that
$(\x^T\x)^r f_0(\x) = \sum_{i=1}^m f_i(\x)g_i(\x).$
\end{theorem}

This result was recently extended by Dickinson and Povh \cite{DiPo:14}.
\begin{theorem}
Let $m\in\N,~m\ge 1$ and $f_0,\ldots,f_m\in\R[\x]$ be homogeneous polynomials on $\R^n$ such that $f_0(\x)>0$ for all non-zero $\x\in\{\x\colon \x\ge 0,~  f_1(\x)= 1,~f_i(\x)\ge 0~\forall i\ge 1\}$.  Then for some $r\in\N$, there exist homogeneous polynomials $g_1,\ldots,g_m\in\R[\x]$ such that all of their coefficients are non-negative and $(\be^T\x)^r f_0(\x) = \sum_{i=1}^m f_i(\x)g_i(\x)$.
\end{theorem}
Dickinson and Povh proved in \cite{DiPo:14a} that this Positivestellensatz implies in a natural way linear and semidefinite programming bounds for \ref{eq:qap1} which are comparable to the strongest bounds from the literature.

\section{Sum of squares and semidefinite programming}\label{sec:approx}
We can check whether polynomial $f\in\R[\x]$ of degree  $2d$ is SOS by semidefinite programming. Indeed, $f$ is SOS if and only if there exists a $Q\succeq 0$ such that
$f(\x)=V_d^TQV_d,$
where  $V_d$ is the vector of all monomials of degree $\le d$. Checking if $f$ is SOS is therefore a semidefinite programming feasibility problem. We can use objective function $\tr(Q)$ as a heuristic for rank minimization of $Q$. If we include in $V_d$ all monomials up to degree $d$ then
$V_d$ is of length  ${n+d}\choose d$.
We can find examples, where we indeed need all these monomials. If $n=4$ and $d=10$, we obtain
 ${n+d \choose d}=1001$, hence the resulting SDPs are already on the boundary of the set of instances, solvable by interior point methods.

Nevertheless, very often, especially if the polynomial is sparse (has only few monomials) it is possible to considerable decrease the number of monomials in $V_d$. We can use a result, first  formulated in \cite{Re78}, that characterizes the monomials that
can appear in a sum of squares representation. Define the  Newton polytope $\New_p$
 of given polynomial $p$ of degree $2d$ as the integer lattice points in the convex hull of the degrees $\alpha$, which appear in $p$. Then, it can be shown that the only monomials $x^\beta$
that can appear in a sum of squares representation are those such that $2\beta$ is  in the
$\New_p$ (or equivalently $\beta \in \frac{1}{2}\New_p$). The package SOStools, Yalmip and some other packages for SOS decompositions
are essentially based on the Newton polytope algorithm.

Finding certificate that follows from Putinar Vasilescu Positivestellensatz \ref{Thm:PosPV} can be again done by SDP but here we are looking for $m$ positive semidefinite matrices that will yield polynomials $g_i$. Since the bounds for these polynomials (and therefore the sizes of SDP matrices) are not determined in advance we typically put a uniform bound (i.e. we demand that the degree of $f_ig_i$ must be equal to degree $2s$). This yields a hierarchy of lower bounds for infimum of $f_0$ over the given semialgebraic set via
\begin{eqnarray*}
OPT_{f_0}&=&\inf\{f_0(\x)\colon f_1(\x)= 1,~f_i(\x)\ge 0~\forall i\ge 1  \}\\
&\ge &\varepsilon_s~=~  \sup\{\varepsilon\colon f_0-\varepsilon = \sum_{i=1}^m s_if_i,~\deg(s_if_i)=2s,~s_i~\mbox{are SOS}\}.
\end{eqnarray*}

Computing $\varepsilon_s$ is therefor an SDP in $m$ SDP variables. When $s$ increases the bounds $\varepsilon_s$ are getting tighter and tighter.
In some cases (e.g. when the semialgebraic set is compact) these bounds converge to $OPT_{f_0}$ \cite{lass:00}.


\section{Approximating combinatorial optimization problems}\label{sec:approx}

In this section we show how to use results from previous section to obtain tractable relaxations for \ref{eq:qap1}.
The staring point is formulation \ref{eq:qap4}.
A simple relaxation is obtained by changing
$ Y \in \CP_{n^2}$ to the weaker condition $Y \in\ck^{0*}_{n^2}$.

We obtain the model:
\begin{equation}\label{eq:qap5}
\tag*{($QAP_{\mathcal{K}_n^{0*}}$)}
\begin{array}{llrcl}
 &\min & \multicolumn{3}{c}{\langle B\otimes A+\Diag(c),Y \rangle}  \\
&\mathrm{s.\ t.} &   \sum_iY^{ii} & = & \bI, \\
&&  \langle \bI,\,Y^{ij}\rangle & = &\delta_{ij},\ \forall i,j,\\
& \multicolumn{2}{r}{\langle \bJ_{n^2},\,Y\rangle} &  = &n^2,\\
& \multicolumn{2}{r}{Y} &\in & \mathcal{N}_{n^2}\cap\cs_{n^2}^+,\\
\end{array}
\end{equation}
\nd \nd We have to emphasize that this is already a computationally expensive model
since the constraint $Y \in  \mathcal{N}_{n^2}$ implies $O(n^4)$
linear inequalities, but yields very strong lower bound for the optimal value of \ref{eq:qap1}.
In fact, \ref{eq:qap5} is equivalent to the strongest approximation models from the literature, see \cite[Theorem 8]{PoRe:09}.

Trading quality of the relaxation for more computational efficiency,
we can follow the approach from Zhao et al. \cite{ZaKaReWo:98}, and observe the
following zero pattern for matrices feasible for
$QAP_{\mathcal{K}_n^{0*}}$:
$$
Y^{ii}_{jk} = 0 ,~~ Y^{jk}_{ii} = 0 ~~~\forall j\not= k, \forall i.
$$
Collecting all these $O(n^3)$ equations symbolically in the map
$\mathcal{G}(Y)=0$, we can consider weaker but also simpler relaxation:
\begin{equation}\label{eq:qap6}
\tag*{($QAP_{ZKRW1}$)}
\begin{array}{llrclrcl}
               & \min & \multicolumn{6}{l}{\langle B\otimes A+\Diag(c),Y
               \rangle}
               \qquad \\
               &\mathrm{s.\ t.} &   \sum_iY^{ii}_{jj} & = & 1,
& \langle \bI,\, Y^{jj}\rangle & = &1,\ \forall j,\\
& & \langle \bJ_{n^2},\,Y\rangle & = & n^2, & \mathcal{G}(Y) & = & 0\\
&& Y &\in & \cs_{n^2}^+
\end{array}
\end{equation}

We use the
acronym ZKRW1 to emphasize that this model is inspired by Zhao et
al.\ \cite{ZaKaReWo:98}. In \cite{PoRe:09} it was shown
that this model is in fact equivalent to the 'gangster-model' from
\cite{ZaKaReWo:98}, see \cite[Theorem 7]{PoRe:09}.

The relaxation \ref{eq:qap6} has 'only' $O(n^3)$ constraints, but solving it is
still a computational challenge. More details about his can be found in \cite{PoRe:09}.




\section{Conclusions}

In this paper we demonstrated that combinatorial optimization naturally poses optimization problems that are very hard to solve and therefore need input from other area of mathematics. Real algebraic geometry contributes via so-called Positivestellens\"atze a hierarchical approach, i.e. a hierarchy of easier problems which optimal solutions converge under some condition to the optimal solution of the original hard problem. These easier problems are typically linear or semidefinite programming problems which can be solved to optimality (at least $\varepsilon$ optimality) efficiently in theory and in practice. However, the size of these simpler problems grows very fast so in practice we are able to use only the members from the beginning of the hierarchy.








%\subsection*{Acknowledgments}
%
%The authors thank Kristijan Cafuta for fruitful discussions and help in coding the Matlab package \ncSOStools.
%
%
%\appendix


%\linespread{1.13}
\bibliographystyle{alpha}
\bibliography{Koi_bib}

\end{document}