Theoretical Paper
Journal of the Operational Research Society (2008) 59, 388–398; doi:10.1057/palgrave.jors.2602356 Published online 3 January 2007
VLSN search algorithms for partitioning problems using matching neighbourhoods
T Öncan1, S N Kabadi2, K P K Nair2 and A P Punnen3
- 1Galatasaray Üniversitesi, Ortaköy,
stanbul, Türkiye - 2University of New Brunswick, Fredericton, New Brunswick, Canada
- 3Simon Fraser University Surrey, Surrey, British Columbia, Canada
Correspondence: AP Punnen, 17048, 57th Ave, Surrey, British Columbia, Canada. V3S 8M9. E-mail: apunnen@sfu.ca
Received February 2006; Accepted September 2006; Published online 3 January 2007.
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.
Keywords:
integer programming, combinatorial analysis, VLSN search, partitioning problems, generalized assignment, local search
