Geoscience Reference
In-Depth Information
Fig. 20.3
An example of solution to the ring star problem
Using binary variables x
ij
to indicate if node j is assigned to concentrator i,
i;j
2
V , with x
ii
D
1 indicating that i is selected as concentrator, and variables
z
ij
to indicate if edge
f
i;j
g2
E is used in the cycle, the problem can be formulated as:
Minimize
X
i2V
X
c
ij
x
ij
C
X
fi;jg2E
d
ij
z
ij
(20.30)
j2V
X
subject to
x
ij
D
1
j
2
V;
(20.31)
i2V
X
z
ij
D
2x
ii
i
2
V;
(20.32)
jWfi;jg2ı.fig/
X
z
jk
2
X
i2W
x
ii
W
V
nf
r
g
;i
2
W; (20.33)
fj;kg2ı.W/
x
rr
D
1
(20.34)
x
ij
2f
0;1
g
i;j
2
V;
(20.35)
z
ij
2f
0;1
g
f
i;j
g2
E;
(20.36)
where, for any W
V , ı.W/
Dff
i;j
g2
E
W
i
…
W; j
2
W
g
denotes the cut
induced by W . Constraints (
20.31
) ensure that each node is linked to one of the
