VLSN search algorithms for partitioning problems using matching neighbourhoods

VLSN search algorithms for partitioning problems using matching neighbourhoods

0.00 Avg rating0 Votes
Article ID: iaor20091342
Country: United Kingdom
Volume: 59
Issue: 3
Start Page Number: 388
End Page Number: 398
Publication Date: Mar 2008
Journal: Journal of the Operational Research Society
Authors: , , ,
Keywords: combinatorial analysis, programming: integer, sets
Abstract:

In this paper, we propose a general paradigm to design very large-scale neighbourhood search algorithms for generic partitioning-type problems. We identify neighbourhoods of exponential size, called matching neighbourhoods, comprised of the union of a class of exponential neighbourhoods. It is shown that these individual components of the matching neighbourhood can be searched in polynomial time, whereas searching the matching neighbourhood is NP-hard. Matching neighbourhood subsumes a well-known class of exponential neighbourhoods called cyclic-exchange neighbourhoods. Our VLSN algorithm is implemented for two special cases of the partitioning problem; the covering assignment problem and the single source transportation problem. Encouraging experimental results are also reported.

Reviews

Required fields are marked *. Your email address will not be published.