A RANDOMIZED LOCAL SEARCH ALGORITHM
FOR THE SIMPLE PLANT LOCATION PROBLEM

Yu. A. Kochetov

In the paper we consider the Simple Plant Location Problem in the following formulation. Given sets I={1,2,...,I}, J={1,2,...,J}, vector c_i 0, iI and matrix d_ij 0, iI, jJ. The objective is to find the subset S I, which minimizes a function

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.

REFERENCES

1. M.Garey, D.Johnson (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco,CA.
2. E.Aarts, J.K.Lenstra (eds.) (1997) Local Search in Combinatorial Optimization. Wiley-Interscience Serias in Discrete Mathematics and Optimization.
3. T.A.Feo (1995) Greedy Randomized Adaptive Search Procedure. Journal of Global Optimization 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