An improved lower bound for the multimedian location problem

An improved lower bound for the multimedian location problem

0.00 Avg rating0 Votes
Article ID: iaor20031307
Country: Netherlands
Volume: 110
Issue: 1
Start Page Number: 17
End Page Number: 31
Publication Date: Feb 2002
Journal: Annals of Operations Research
Authors: , ,
Keywords: networks, programming: linear
Abstract:

We consider the problem of locating, on a network, n new facilities that interact with m existing facilities. In addition, pairs of new facilities interact. This problem, the multimedian location problem on a network, is known to be NP-hard. We give a new integer programming formulation of this problem, and show that its linear programming relaxation provides a lower bound that is superior to the bound provided by a previously published formulation. We also report results of computational testing with both formulations.

Reviews

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