Lagrangian solution of maximum dispersion problems

Lagrangian solution of maximum dispersion problems

0.00 Avg rating0 Votes
Article ID: iaor200184
Country: United States
Volume: 47
Issue: 2
Start Page Number: 97
End Page Number: 114
Publication Date: Mar 2000
Journal: Naval Research Logistics
Authors: , ,
Keywords: lagrange multipliers
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.