@ARTICLE\{IMM2007-04570,
    author       = "A. Dohn and S. G. Christensen and D. M. Rous{\o}e",
    title        = "The p/q{-ACTIVE} uncapacitated facility location problem: Investigation of the solution space and an {LP-}fitting heuristic",
    year         = "2007",
    month        = "jul",
    keywords     = "p/q-active; p-active; Uncapacitated facility location; Heuristic solution methods; {LP-}relaxation; {LP-}fit; {MIP-}heuristics; {FBA-}search; First better admissible search",
    pages        = "532-546",
    journal      = "European Journal of Operational Research",
    volume       = "180",
    editor       = "",
    number       = "2",
    publisher    = "Elsevier",
    url          = "http://dx.doi.org/10.1016/j.ejor.2006.05.007",
    abstract     = "The p/q-active uncapacitated facility location problem is the problem of locating p facilities on n possible sites each serving at least q of the m clients at the minimum cost. The problem is an extension of the uncapacitated facility location problem (UFL) where constraints on the number of facilities and their minimum activity have been added. A use of this formulation could be the opening of p new schools where each must have at least q pupils. p/q-active is {NP-}hard like the {UFL}.

In this paper we present a thorough investigation of the p/q-active {UFL} and propose a heuristic solution method. Different geometric and random cost problem instances are considered. Experiments show that 60\% of the problems can be solved to optimality just by solving the corresponding {LP-}relaxation. Using a simple local search heuristic, the remaining geometric problems are solved with an average gap of 0.1\% to a lower bound found by {LP-}relaxation. An effort is put into isolating problem types that are hard to solve. Problems with low p, p · q close to m combined with clustered clients or a low variation in the facility opening cost are most likely to give results worse than average. Gaps up to 8\% are observed in the worst cases.",
    isbn_issn    = "03772217"
}