Example of abstract View





Yu. A. Kochetov


\ \\

In the paper we consider the Simple Plant Location Problem in the following formulation.

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 minimizes 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 creating 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) 35-63-27,\\ fax: (8-383-2) 35-06-52, e-mail: jkochet@math.nsc.ru