Locating a semi-obnoxious facility - A toland-singer duality based approach

© Heldermann Verlag. We consider the problem of locating a facility amongst a given collection of attraction and repulsion points. The goal is to find a location x in the Euclidean space ℝn for a facility, such that the difference between the weighted sum of distances from x to the attraction points and the weighted sum of distances to the repulsion points is minimized. The corresponding objective function constitutes as a D.C. function. Based on the duality theory by Toland and Singer for the class of D.C. programs, we formulate a dual problem to the given location problem. Taking into account the special structure of the location problem, we present geometrical properties of the model, give conditions for the existence of an optimal solution, obtain duality results, describe the relationship between primal and dual elements, and formulate an algorithm which determines exact solutions for the location problem by reducing this non-convex optimization problem to a finite number of linear programs.