Geoscience Reference
In-Depth Information
right part a circle minimizing the sum of Euclidean distances to the existing facilities
is depicted. The lengths of the thin lines in both examples correspond to the
distances from the existing facilities to the line (or to the circle, respectively). Note
that the distance between a facility v 2 X and X is zero—this happens twice in the
right part of the figure where the minsum circle passes through two of the existing
points.
In the following sections we discuss different types of dimensional facilities
to be located. Most of the resulting optimization problems are multi-modal and
neither convex nor concave. Hence, methods of global optimization are required.
However, in many of these location problems it is possible to exploit one or more
of the following properties showing that they have much more structure than just an
arbitrary global optimization problem.
LP properties: Some of the problems become piecewise linear, sometimes even
resulting in linear programming (LP) approaches which can be solved highly
efficiently.
FDS properties: A finite dominating set (FDS) is a finite set of possible solutions
from which it is known that it contains an optimal solution to the problem. This
allows an enumeration approach by evaluating all possible elements of the FDS.
Halving properties: In many cases, any optimal facility to be located splits the sets
of existing points into two sets of nearly equal weights. This allows to enhance
enumeration approaches.
In our conclusion we provide a summary on these properties and give some general
hints when they hold and why they are useful.
7.3
Locating Lines and Hyperplanes
D the hyperplane location problem is to find a
hyperplane H minimizing the distances to the points in V . In this section we
consider such hyperplane location problems for different types of distances and
different objective functions.
Note that line location deals with finding a line in
Given a set of points V
R
2 minimizing the distances
to a set of two-dimensional points and is included in our discussion as the special
case D D 2.
R
7.3.1
Applications
The location of lines and hyperplanes has many applications within at least three
different mathematical fields: Operations research, computational geometry, and
statistics. Applications in operations research are various. The new facility to be
located may be, e.g., a highway (see Díaz-Bánez et al. 2013 ), a train line (see Espejo
Search WWH ::




Custom Search