Geoscience Reference
In-Depth Information
Hence the two problems are equivalent, and Chen et al. (
2010
) solved the RLP
indirectly with a branch-and-cut algorithm for the unit degree Steiner Arborescence
problem.
Introducing binary variables y
i
to indicate if a node i
2
N
2
is used in the
arborescence, and binary variables x
ij
to indicate if arc .i;j/
2
A is used, the
problem can be formulated as:
X
Minimize
c
ij
x
ij
(20.22)
.i;j/2A
X
subject to
x
ij
D
1j
2
N
1
;
(20.23)
iW.i;j/2ı
.fjg/
X
x
ij
D
y
j
j
2
N
2
;
(20.24)
iW.i;j/2ı
.fjg/
X
x
ij
1W
N; W
\
N
1
¤;
;
(20.25)
.i;j/2ı
.W/
X
x
ij
y
k
W
N; k
2
W
\
N
2
;
(20.26)
.i;j/2ı
.W/
X
x
rj
D
1
(20.27)
jW.r;j/2ı
C
.frg/
x
ij
2f
0;1
g
.i;j/
2
A;
(20.28)
y
i
2f
0;1
g
i
2
N
2
:
(20.29)
Constraints (
20.23
)and(
20.24
) are degree constraints imposing that each node
used in the arborescence has exactly one incoming arc, cut constraints (
20.25
)and
(
20.26
) ensure connectivity, while (
20.27
) is the degree constraint on the root.
A weighted version of the problem was also discussed by Chen et al. (
2010
),
where a cost
w
i
is associated with the placement of a regenerator in node i
2
V ,
depending on the location in the network. The model above can again be used by
setting the cost of arc .i
1
;i
2
/ to
w
i
instead of one.
Computational results reported show the effectiveness of the branch-and-cut
algorithm for small to medium size instances. For large scale instances, heuristics
appear to be the only viable approach as the lower bounds provided by the branch-
and-cut algorithm are really weak. Very recently, Duarte et al. (
2014
) proposed
randomized heuristics that outperform the constructive heuristics of Chen et al.
(
2010
).
