In this paper we consider generalizations of multifacility location problems in which as an additional constraint the new facilities are not allowed to be located in a prespecified region. We propose several different solution schemes for this nonconvex optimization problem. These include a linear programming type approach, penalty approaches and barrier approaches. Moreover, structural results as well as illustrative examples showing the difficulties of this problem are presented.