Geoscience Reference
In-Depth Information
The two node sets of the graph are given by the existing points V and by the potential
hyperplanes in the FDS. Every node v from V is connected to every node H from
the FDS where the edge .v;H/ is weighted by the distance, the node v has from the
hyperplane H. The goal is to serve all customers in V by installing p new locations
in the FDS.
Finally, the problem of finding p lines in the plane is studied in Bertsimas and
Shioda (
2007
) where it is formulated as an integer program. Binary variables x
j;q
determine to which of the q
D
1;:::;p lines the existing point v
j
is assigned.
Applying their basic formulation to the linear program (
7.9
)-(
7.14
) of Sect.
7.3.5
gives
X
n
minimize
w
j
d
j
jD1
subject to d
j
v
j
a
q
C
b
q
M.1
x
j;q
/ for j
D
1;:::;n; q
D
1;:::;p
d
j
v
j
a
q
b
q
M.1
x
j;q
/ for j
D
1;:::;n; q
D
1;:::;p
p
X
x
j;q
D
1 for j
D
1;:::;n
qD1
x
j;q
2f
0;1
g
for j
D
1;:::;n; q
D
1;:::;p
d
j
0 for j
D
1;:::;n
a
q
D
1 for q
D
1;:::;p
b
q
;a
i
q
2
R
for i
D
1;:::;D
1; q
D
1;:::;p:
Solving the integer program in its basic form is not possible in reasonable time; in
Bertsimas and Shioda (
2007
) clustering algorithms are performed in a preprocessing
step. The above integer program can also be used for solving the minmax version of
the problem, if
P
is replaced by max in its objective function.
7.3.7.3
Restricted Line Location
Line location problems in which the line is not allowed to pass through a specified
set R
2
can be tackled by looking at the dual space and transforming
the restriction to a forbidden set there. Since the problem is convex for vertical
distances, techniques from location theory can be used, e.g., the boundary theorem
saying that there exists a solution on the boundary of the restricted set whenever the
restriction is not redundant (see Hamacher and Nickel
1995
). The results may be
generalized to block norms or to arbitrary norms, see Schöbel (
1999b
).
In some statistical applications it is preferable to restrict the slope of the line
(or the norm of a) as done in types of RLAD approaches (Wang et al.
2006
). Such
R
