Geoscience Reference
In-Depth Information
A further reason for using heuristics is that aggregation is used to reduce the
size of the problem so that larger size instances can be tackled. Daskin et al.
(
1989
) study the effect of node aggregation for MCLP. Three aggregation schemes
are tested based on relative demands on the disaggregate nodes, distances between
the disaggregate nodes and a mix of both. The first and the third methods are shown
to perform much better than the second. In Current and Schilling (
1990
)threerules
are proposed to reduce the aggregation error in SCP and MCLP.
5.6
Lagrangian Relaxation
Among the many different methods that have been developed in the literature for
covering models, we highlight here Lagrangian Relaxation (LR) for several reasons.
First, LR can be used as a heuristic method but can additionally provide good lower
bounds which can be embedded into a branch-and-bound framework to develop an
exact method. Second, as shown in Sects.
5.4
and
5.5
, LR has been widely used
in covering problems. Third, it can be designed for the general model (COV) and
then used on any particular case without loss of accuracy. And, finally, LR usually
produces very good results in a reasonable amount of computational time. Readers
not familiarized with this technique are referred to Guignard (
2003
).
In what follows, we apply LR to model (COV) by making the natural choice of
relaxing constraints (
5.3
). Since the non-relaxed linear constraints (
5.2
)andy
i
e
i
8
i
2
I give rise to a totally unimodular coefficients matrix, lower bounds
produced by means of LR will not be greater than lower bounds produced by
the usual linear relaxation. A Lagrangian multiplier v
j
2
associated to each
constraint in (
5.3
), unrestricted in sign, will be used. So, a family of Lagrangian
relaxed subproblems is obtained with objective functions
R
X
!
D
X
f
i
y
i
C
X
j2J
X
g
jk
w
jk
C
X
j2J
a
ij
y
i
b
j
X
k2K
v
j
w
jk
i2I
k2K
i2I
0
@
f
i
C
X
j2J
1
A
y
i
C
X
j2J
X
X
g
jk
v
j
w
jk
X
j2J
v
j
a
ij
v
j
b
j
:
i2I
k2K
By solving
.COVLR.v// min
P
i2I
f
i
C
P
j2J
v
j
a
ij
y
i
C
P
j2J
P
k2K
g
jk
v
j
w
jk
s.t. (
5.2
); (
5.4
); (
5.5
);
and then adding constant
P
j2J
v
j
b
j
, we will get a lower bound on the objective
value of (COV) when the set of multipliers is v
D
.v
1
;:::;v
n
/.
