The p/q-active uncapacitated facility location problem: Investigation of the solution space and an LP-fitting heuristic

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.