Location of Dimensional Facilities in a Continuous Space - Location Science - page 166

Tabl e 7. 2 Summary of properties for some of the considered location problems

Problem FDS Halving LP

Minsum hyperplane with d D d ver Ye s Ye s Ye s

Minsum hyperplane with norm Ye s Ye s No

Minsum hyperplane with block norm Ye s Ye s Ye s

Minsum hyperplane with gauges No (Yes) No

Minmax hyperplane with norm Ye s No No

Minmax hyperplane with block norm Ye s No Ye s

Minmax hyperplane with gauges Ye s No No

Ordered minsum hyperplane with norm Ye s Ye s No

3

Minsum line in R No No No

Line may not pass through a polyhedral set Ye s No No

Minsum/minmax p-line with norm Ye s No No

Minsum hypersphere with norm No Ye s No

Minsum hypersphere with block norm Ye s Ye s Ye s

Minmax hypersphere with Euclidean norm Ye s No No

Minmax circle with rectangular norm Ye s No Ye s

The FDS property gives the straightforward possibility of enumerating the
candidate set. Also for the location of p facilities the FDS property is still helpful,
although the number of candidates increases to O( j FDS j p ). As demonstrated for the
p-minsum line location problem in Sect. 7.3.7 , an FDS also allows to transfer the
problem of locating p facilities to a p-location problem on a bipartite graph with
O( j FDS j ) nodes. It is ongoing work to test such approaches numerically.
Enumeration may be enhanced by the halving property which can be used
to directly discard candidates. Such discarding tests are also useful in other
approaches, even if no FDS is known, since the halving property allows to discard
whole regions when searching for an optimal solution. An example is the search
along bisectors which can be reduced to the relevant parts in the Euclidean minsum
circle location problem. Also in geometric branch & bound approaches such as Big-
Square-Small-Square (Plastria 1992 ), Big-Triangle-Small-Triangle (Drezner and
Suzuki 2004 ), or Big-Cube-Small-Cube (Schöbel and Scholz 2010 ), discarding tests
motivated by the halving property may be interesting.
Using linear programming methods is an efficient way of solving facility location
problems, in particular if the number of variables needed for the linear program
is not too large. This is the case for block norms with not too many fundamental
directions.
While many questions in the location of lines and hyperplanes seem to be solved,
there are still questions remaining in the location of hyperspheres. These concern,
on one hand, general properties about the location of hyperspheres with other than
the minsum objective function and with arbitrary norms or gauges. On the other
hand, there are also many special cases waiting to be investigated, in particular if
the sphere is defined with respect to another norm as the distance function.