Geoscience Reference
In-Depth Information
continuous variables g
ij
for .i;j/
2
A
S
, representing the amount of flow routed
on arc .i;j/ to satisfy the demands of the facilities.
Minimize
X
i2I
f
i
y
i
C
X
.i;j/2A
c
ij
x
ij
(20.14)
X
g
ji
X
jW.i;j/2A
S
subject to
g
ij
jW.j;i/2A
S
8
<
b
i
y
i
if i
2
I;
X
k2I
b
k
y
k
if i
D
r;
D
i
2
S; (20.15)
:
0
otherwise,
0
g
ij
u
ij
x
ij
.i;j/
2
A
S
;
(20.16)
X
x
ij
D
1
j
2
J; (20.17)
iW.i;j/2A
J
X
d
j
x
ij
q
i
y
i
i
2
I; (20.18)
jW.i;j/2A
J
x
ij
y
i
.i;j/
2
A
J
;
(20.19)
x
ij
2f
0;1
g
.i;j/
2
A;
(20.20)
y
i
2f
0;1
g
i
2
I: (20.21)
Constraints (
20.17
)-(
20.21
) are similar to the Concentrator Location Problem
(see Sect.
20.2
). Constraints (
20.15
) are flow conservation constraints that ensure the
demands of open facilities are routed from the root node, while constraints (
20.16
)
make sure only arcs belonging to the Steiner tree are used for satisfying the demands
of the facilities, and that flows do not exceed arc capacities.
Although this formulation is compact, it is attractive from a computational point
of view to project out flow variables and replace constraints (
20.15
)and(
20.16
)by
the capacitated cut set inequalities (Ljubi
´
cetal.
2012
):
X
u
ij
x
ij
X
k2F\W
d
k
y
k
W
S
nf
r
g
:
.i;j/2ı
.W/
These inequalities can easily be strengthened as follows:
min
u
ij
;
X
k2F \W
!
x
ij
X
k2F \W
X
d
k
d
k
y
k
W
S
nf
r
g
:
.i;j/2ı
.W/
