The big cube small cube solution method for multidimensional facility location problems

摘要

In this paper we propose a general solution method for (non-differentiable) facility location problems with more than two variables as an extension of the Big Square Small Square technique (BSSS). We develop a general framework based on lower bounds and discarding tests for every location problem. We demonstrate our approach on three problems: the Fermat-Weber problem with positive and negative weights, the median circle problem, and the p-median problem. For each of these problems we show how to calculate lower bounds and discarding tests. Computational experiences are given which show that the proposed solution method is fast and exact.