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: | Punnen A.P., Nair K.P.K., Kabadi S.N., ncan T. |
Keywords: | combinatorial analysis, programming: integer, sets |
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.