Information Technology Reference
In-Depth Information
vectors
δ
B
I
each corresponding to a constraint generated. We note that the
definition of
R
(
x, y, z
;
δ
) contains the terms
z
i
y
i
and hence is non-linear. There-
fore,weassumethevalueof
z
to be fixed for each constraint generated, so (32)
become linear constraints to facilitate solution of (
RM
) using mixed-integer
programming solvers. The dual ascent approach is as follows:
∈
Dual Ascent Algorithm
(
DA
)
Step 0:
(Initialisation)
.
Let
V
=0
,k
=1.
Step 1:
(Restricted Master Problem) Solve (
RM
), let the optimal solution be
(
x, y, z
) and the optimal value be
V
.
Step 2:
(Termination) If all extreme points of
D
=
∅
F∈
(
x, y, z
) are already in
D
,or
K
, terminate. (The complete solution is obtained by solving (
L2a
).)
Otherwise,
Step 3:
(Cut Generation) Consider some
δ
if
k
≥
∈F∈
(
x, y, z
)notin
D
.Solve(
L3a
)to
obtain the dual values
α
and
β
.Add
δ
to
D
and the corresponding constraint
to (
RM
). Increase
k
by 1. Go to
Step 1
.
5.3 Cut Generation
The eciency of the dual ascent algorithm depends heavily on how quickly it
converges, since each iteration involves solving the
Restricted Master Problem
which is a mixed-integer-programming problem. Thus, eciency might be im-
proved if more than one cut is generated per iteration. Of course, if constraints
corresponding to
all
the extreme points of
(
x, y, z
) are generated at each it-
eration, the number of iterations needed is expected to be small. However, this
entails enumerating these extreme points and also adding a large number of cuts
to (
RM
). In our approach, we propose a heuristic for identifying three values
of
δ
to be used for cut generation in
Step 3
of (
DA
), as follows. The heuris-
tic is based on the
ADD-DROP
heuristic for facility location (Kuehn and
Hamburger, 1963).
F∈
Cut Generation Heuristic
(
CG
)
Step 0:
(Initialisation) Let
δ
a
=0
,δ
b
=0
,δ
d
=
y
.Let
R
max
=0.Let
I
a
=
I
d
=
I
=
.
Step 1:
(Termination of ADD) If
I
a
=
{
i
∈
I
:
y
i
=1
}
,goto
Step 3
.Otherwise,
Step 2:
(ADD) For each
i
in
I
a
,consider
δ
=
δ
a
+
1
i
and solve (
L3a
). Let
i
∗
be
the index that corresponds to the highest optimal value. We set
δ
a
=
δ
a
+
1
i
∗
.
If the optimal value is larger than
R
max
,thenweset
δ
b
=
δ
a
and update
R
max
.Goto
Step 1
.
Step 3:
(Termination of DROP) If
∅
I
d
<D
, terminate. Otherwise,
Step 4:
(DROP) For each
i
in
I
d
,consider
δ
=
δ
d
|
|
1
i
and solve (
L3a
). Let
i
∗
be
the index that corresponds to the highest optimal value. We set
δ
d
=
δ
d
−
1
i
∗
.
If the optimal value is larger than
R
max
,thenweset
δ
b
=
δ
d
and update
R
max
.Goto
Step 3
.
−
If no centre is destroyed by the disaster, the recovery cost is zero. The ADD part
of the heuristic successively selects one additional centre to destroy to cause the
