Example of abstract View


Yu. A. Kochetov


\ \\
In the paper we consider the Simple Plant Location Problem in the following
Given sets $I=\{1,2, \dots, {\bf I} \}, \ J=\{1,2, \dots, {\bf J} \},$ vector $c_i \geq 0,
i \in I$ and matrix $d_{ij} \geq 0, \ i \in I, \ j \in J.$ The objective is to find the subset $S \subseteq I,$ which minimize
s a function
$$ F(S) =\sum\limits_{i \in S} c_i + \sum\limits_{j \in J} \min_{i \in S} d_{ij}$$
over all subsets of the set $I$. It is a well-known $NP$-hard discrete optimization problem [1]. We study behavior of Tabu Search algorithm [2] with different kinds of neighborhoods: complete neighborhood for the 2 Hamming distance and two randomized subneighborhoods with constant and adaptive sizes. We present a new search strategy which keeps an information about searching process and uses it for creati
ng of a subneighborhoods (probabilistic antitabu rule). To find new starting point a history-sensitive randomized greedy algorithm is proposed. The algorithm is a modified Greedy Randomized Adaptive Search Procedure [3] which applies previous search information of Tabu Search algorithm. Comprehensive computational results for the Simple Plant Location Problem are discussed.\\

This research was supported by RFBR grant 97-01-00890.

\begin{center} REFERENCES \end{center}
1. M.Garey, D.Johnson (1979) {\it Computers and Intractability: A Guide to the Theory of NP-Completeness.} Freeman, San Francisco,CA. \\
2. E.Aarts, J.K.Lenstra (eds.) (1997) {\it Local Search in Combinatorial Optimization.} Wiley-Interscience Serias in Discrete Mathematics and Optimization.\\
3. T.A.Feo (1995) {\it Greedy Randomized Adaptive Search Procedure.} Journal of Global Optimization {\bf 6}, 109-133.\\


------------------------------------------------------------------------------------------ \\

Kochetov Yuri Andreevich, Sobolev Institute of Mathematics, \\
pr. Academica Koptyuga 4, Novosibirsk, 630090, Russia, \\
phone: (8-383-2) 33-20-86, fax: (8-383-2) 33-25-98, e-mail: jkochet@math.nsc.ru