A polynomial time dual algorithm for the Euclidean multifacility location problem

A polynomial time dual algorithm for the Euclidean multifacility location problem

0.00 Avg rating0 Votes
Article ID: iaor1997824
Country: Netherlands
Volume: 18
Issue: 4
Start Page Number: 201
End Page Number: 204
Publication Date: Feb 1996
Journal: Operations Research Letters
Authors: , ,
Abstract:

The Euclidean multi-facility location (EMFL) problem is one of locating new facilities in the Euclidean space with respect to existing facilities. The proble consists of finding locations of new facilities which will minimize a total cost function which consists of a sum of costs directly proportional to the Euclidean distances between the new facilities, and costs directly proportional to the Euclidean distances between new and existing facilities. In this paper, it is shown that the dual of EMFL proposed by Francis and Cabot is equivalent to the maximization of a linear function subject to convex quadratic inequality constraints and therfore can be solved in polynomial time by interior point methods. The authors also establish a theorem on the duality gap and present a procedure for recovering the primal solution from an interior dual feasible solution.

Reviews

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