Premium
Lagrangian solution of maximum dispersion problems
Author(s) -
Ağca Şenay,
Eksioglu Burak,
Ghosh Jay B.
Publication year - 2000
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(200003)47:2<97::aid-nav2>3.0.co;2-2
Subject(s) - heuristics , mathematical optimization , heuristic , lagrangian , lagrangian relaxation , variety (cybernetics) , set (abstract data type) , selection (genetic algorithm) , mathematics , computer science , artificial intelligence , statistics , programming language
We address the so‐called maximum dispersion problems where the objective is to maximize the sum or the minimum of interelement distances amongst a subset chosen from a given set. The problems arise in a variety of contexts including the location of obnoxious facilities, the selection of diverse groups, and the identification of dense subgraphs. They are known to be computationally difficult. In this paper, we propose a Lagrangian approach toward their solution and report the results of an extensive computational experimentation. Our results show that our Lagrangian approach is reasonably fast, that it yields heuristic solutions which provide good lower bounds on the optimum solution values for both the sum and the minimum problems, and further that it produces decent upper bounds in the case of the sum problem. For the sum problem, the results also show that the Lagrangian heuristic compares favorably against several existing heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 97–114, 2000