% INFO: Journal "INFORMATION TECHNOLOGY AND CONTROL", KTU, Lithuania
% Requires Latex2e!
\documentclass{informx}
\usepackage{graphics}%
%\usepackage[dvips]{graphicx}
% Lithuanian letters
%\usepackage{ltletter}
\volume{41}
\issue{1}
\pubyear{2012}
\firstpage{5}
\lastpage{7}
%\newtheorem{}{}
%\listfiles
\begin{document}
\begin{frontmatter}                           % The preamble begins here.  
\vspace{20pt}
\def\infnumber{1}%
\def\infyear{2010}%
\def\volume{39}
\def\infphouse{\journal,\volume, \infyear, \infnumber}
%
\title{Application of Multistart Tabu Search to the \\
MAX--CUT Problem}
%\thanks{}
\author{\textbf{\fnms{Vardenis} \snm{Pavardenis}}}  %\thanks{}
\address{Kaunas University of Technology, Department of Multimedia Engineering\\
Studentu st. 50-400a, LT-3031 Kaunas, Lithuania\\
\email{itc@ktu.lt}}

\author{\textbf{\fnms{Varden\.e} \snm{Pavarden\.e}}}%\thanks{}
\address{Vytautas Magnus University, Department of Applied Informatics\\ 
Vileikos str. 8, LT-44404 Kaunas,Lithuania%\\
}
\runningauthor{V.Pavardenis, V.Pavarden\.e}
\runningtitle{Application of Multistart Tabu Search to the MAX--CUT Problem}
% HISTORY:
\received{\smonth{May} \syear{2011}}
%
\maketitle
\begin{abstract}
In this paper, we investigate two multistart tabu search implementations for the MAX - CUT problem: an algorithm based on application of a steepeset ascent heuristic to specially constructed subproblems and the classical random restart method. Computational results on three seta of standard test problems indicate that the first of these techniques outperforms the second one and is very competitive when compared to other heuristic algorithms.
\end{abstract}
\begin{keyword}
combinatorial optimization; heuristics; tabu search; MAX--CUT.
\end{keyword}
\end{frontmatter}

%*************** Text entry area ******************%

\section{Introduction}\label{intro}%1

Given an undirected graph $G=(V,E)$  with vertex set $V={1,\ldots ,n}$, edge set $E\subseteq V \times V $ and weights    ${w_{ij}}$ associated with the edges $(i,j)\in E$, the MAX - CUT problem asks for a subset of vertices $V_1$  such that the weight of the cut $(V_1, V_2=V\setminus V_1)$  given by $w(V_1, V_2)=\sum_{i\in V_1 , j\in V_2} w_ij $  is maximized. 

\begin{figure*}
 	\centerline{\includegraphics{1sample}}
  \caption{Graphical interpretation of the quadratic assignment problem}\label{figb}
\end{figure*}

Introducing binary variables $i, j \in V$, the problem can be stated as follows 
\begin{equation}
\text{maximize}\quad F(x)=\sum_{{i,j}\in E} w_ij (x_i - x_j)^2
    \label{e1}
\end{equation}

\begin{equation}
\text{subject to}\qquad x_i \in \{0,1\},i \in V .
    \label{e2}
 \end{equation}
 
The MAX - CUT problem is of considerable practical significance. It has a large number of applications, the most known of which are found in design automation \cite{1,2} and statistical physics \cite{3}.

\section{Algorithms}\label{alg}%3
In this section we briefly describe two multistart tabu search algorithms adapted for solving the MAX - CUT problem. 

The first algorithm generates new staring points by fixing values of some variables at 0 and then applying a steepeset ascent procedure to the projection of the problem constructed by removing the fixed variables. 

\section{Theorems, Definitions, Proof}

It is very easy to set theorems, lemmas, definitions, examples and
proofs. Really, it is very easy to set theorems, lemmas, definitions, examples and
proofs.

\begin{theorem}\label{T1}
It is very easy to set theorems.
\end{theorem}

\begin{proof}\label{P1}
It is very easy to prove.
\end{proof}

\begin{lemma}\label{L1}
It is very easy to set lemmas.
\end{lemma}


\begin{definition}\label{D1}
It is very easy to set definitions.
\end{definition}


\begin{remark}
It is very easy to set remarks.It is very easy to set theorems, lemmas, definitions, examples and
proofs. Really, it is very easy to set theorems, lemmas, definitions, examples and
proofs.
\end{remark}

\begin{corollary}
It is very easy to set corollaries.
\end{corollary}

\begin{proposition}
It is very easy to set theorems, lemmas, definitions, examples and
proofs. Really, it is very easy to set theorems, lemmas, definitions, examples and
proofs.
\end{proposition}

The last experiment was conducted on a set of test problems taken from the DIMACS library of semidefinite - quadratic - linear programs. This set contains four instances of MAX - CUT, called the torns problems, which originated from the Ising model of spin glasses in physics. We run MST and RRT on each instance 5 times for 1800 seconds in the case of pm3-8-50 and g3-8 and for 7200 seconds in the case of pm3-15-50 and g3-15. The results are reported in Table~\ref{tab1}.

\begin{table*}%[h]%t2
\caption{Solutions found by different techniques for the torns problems}\label{tab1}
\begin{tabular}{lrrrrr}
\hline
Problem&  n&  circuit& SA&  RRT&   MST\\
\hline
pm3-8-50 &    512&       454&  458&       458&       458\\
pm3-15-50 &  3375&      2964&  900&      2930&      3000\\
g3-8 &        512&  41684814&  892&  40043061&  41684814\\
g3-15 &      3375& 281029888&  898& 251918092& 283206561\\
\hline
\end{tabular}
\end{table*}

\section{Experimental results}\label{results}%3


The main purpose of experimentation was to investigate the capabilities of tabu search in solving instances of the MAX - CUT problem and to compare the obtained results with those reported in the literature. 

\begin{figure}%[t]
   \centerline{\includegraphics{2sample}}
   \caption{A curve}\label{fig2}
\end{figure}

\section{Conclusions}\label{conc}%3
In this paper we presented two multistart tabu search implementations for the MAX - CUT problem. 
The algorithm can quickly find solutions that are competitive with those found by most successful algorithms described in the literature. For 6 benchmark graphs the solutions of weight larger than the best known value were produced. 

%**************** End of text entry *****************

\begin{thebibliography}{9}%{References}{00} for numbered bibliography
\bibitem{1}
\textbf{F. Barahona, M. Gr\"{o}tschel, M. J\"{u}nger, G. Reinelt.} An application of combinatorial optimization to statistical physics and circuit lauout design. \emph{Operation Research}, 1988, 36, 493 - 513.
\vspace{9pt}  
\bibitem{2}
\textbf{P. Festa, M. G. C. Resende.} CIRCUIT + PR: rank-2 heuristic with path - relinking for MAX - CUT. \emph{Extended abstracts of the First Metaheuristics International Conference MIC2003, Kyoto, Japan}, 2003.
\vspace{9pt}     
\bibitem{3} 
\textbf{G. Pataki, S. Schmieta.} The DIMACS library of semidefinite - quadratic - linear programs. \emph{Technical report, Computational Optimization Research Center, Columbia University}, 2002.           \vspace{9pt}                                                                                      
\bibitem{4}   
\textbf{G.C.Armour and E.S.Buffa.} A heuristic algorithm and simulation approach to relative location of facilities. \emph{Management Science},1963,9,294--304.
\vspace{9pt}  
\bibitem{5}   
\textbf{Z. Michalewicz, D.B. Fogel.} How to Solve IT: Modern Heuristics. \emph{Springer, Berlin--Heidelberg}, 2000.
\vspace{9pt}  
\bibitem{6}
\textbf{A. Hertz, E. Taillard, D. de Werra.} Tabu search. \emph{In: E. Arts and J.K. Lenstra (eds.), Local Search in Combinatorial Optimization, Wiley, Chichester},1997, pp. 121--136.

\end{thebibliography}
%********* Backmatter
\begin{backmatter}
\vfill
\begin{abstractLT}
\title{Patobulintas hibridinis optimizavimo algoritmas \\kvadratinio paskirstymo u\v{z}daviniui}
\authors{V. Pavardenis, V. Pavarden\.e}
\v{S}iame straipsnyje pasi\={u}lytas patobulintas hibridinis euristinis optimizavimo algoritmas gerai \v{z}inomam, sud\.{e}tin\-gam kombinatorinio optimizavimo u\v{z}daviniui, b\={u}tent, kvad\-ratinio paskirs\-tymo (KP) u\v{z}daviniui. Tai~\textemdash\quad pagerinta autoriaus ankstesnio hibridinio algoritmo versija. Naujasis algoritmas pasi\v{z}ymi tuo, jog \v{c}ia i\v{s}pl\.{e}tota efektyvi\c{u} euristik\c{u} ~\textemdash\quad atkaitinimo modeliavimo (AM) (angl. \emph{simulated annealing}) ir tabu paie\v{s}kos (TP) (angl. \emph{tabu search}) ~\textemdash\quad ``hibridizacijos'' id\.{e}ja. ``Hibridizacija'' remiasi vadinamaja iteracine schema: TP algoritmas panaudojamas kaip post-analiz\.{e}s proced\={u}ra AM algoritmo gautajam sprendiniui, savo ruo\v{z}tu, AM algoritmas taikomas sprendini\c{u} sekai, gautai sprendini\c{u} diversifikavimo/generavimo keliu. Svarbi pasi\={u}lyto algoritmo savyb\.{e} yra ir ta, kad jame realizuotas vadinamasis ``\v{s}altojo restarto'' principas (mechanizmas), kurio paskirtis ~\textemdash\quad pad\.{e}ti i\v{s}vengti galim\.{u} paie\v{s}kos ``stagnacijos'' situacij\c{u}. Naujasis algoritmas i\v{s}bandytas su KP u\v{z}davinio testiniais pavyzd\v{z}iais (duomenimis) i\v{s} testini\c{u} pavyzd\v{z}i\c{u} bibliotekos ~\textemdash\quad QAPLIB. Gauti eksperiment\c{u} rezultatai liudija, jog nagrin\.{e}tiems KP u\v{z}davinio testi\-niams pavyzd\v{z}iams si\={u}lomas algoritmas yra prana\v{s}esnis u\v{z} ankstesnius atkaitinimo modeliavimo ir tabu. \end{abstractLT}
\end{backmatter}

\end{document}
