VLSN search algorithms for partitioning problems using matching neighbourhoods

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...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of the Operational Research Society 2008-03, Vol.59 (3), p.388-398
Main Authors: Öncan, T, Kabadi, S N, Nair, K P K, Punnen, A P
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Assignment problem
Business and Management
combinatorial analysis
Dairy industry
Exact sciences and technology
Factories
Flows in networks. Combinatorial problems
generalized assignment
Heuristic
Heuristics
integer programming
Local minimum
local search
Logistics
Management
Mathematical vectors
Minimization of cost
Neighborhoods
Operational research and scientific management
Operational research. Management science
Operations research
Operations Research/Decision Theory
partitioning problems
Polynomials
Scheduling
Studies
Suppliers
Supply
Theoretical Paper
Transportation
VLSN search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0160-5682
1476-9360
DOI:10.1057/palgrave.jors.2602356