Premium
Very large‐scale neighborhood search
Author(s) -
Ahuja R.K.,
Orlin J.B.,
Sharma D.
Publication year - 2000
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2000.tb00201.x
Subject(s) - computer science , generalization , mathematical optimization , cluster analysis , scheduling (production processes) , local search (optimization) , combinatorial optimization , class (philosophy) , mathematics , algorithm , artificial intelligence , mathematical analysis
Neighborhood search algorithms are often the most effective approaches available for solving partitioning problems, a difficult class of combinatorial optimization problems arising in many application domains including vehicle routing, telecommunications network design, parallel machine scheduling, location theory, and clustering. A critical issue in the design of a neighborhood search algorithm is the choice of the neighborhood structure, that is, the manner in which the neighborhood is defined. Currently, the two‐exchange neighborhood is the most widely used neighborhood for solving partitioning problems. The paper describes the cyclic exchange neighborhood , which is a generalization of the two‐exchange neighborhood in which a neighbor is obtained by performing a cyclic exchange . The cyclic exchange neighborhood has substantially more neighbors compared to the two‐exchange neighborhood. This paper outlines a network optimization based methodology to search the neighborhood efficiently and presents a proof of concept by applying it to the capacitated minimum spanning tree problem, an important problem in telecommunications network design.