Geoscience Reference
In-Depth Information
Thus, for a given vector , the solution to L SPSFLP ./ can be obtained as follows:
￿Fori 2 I,do
-Findk.i/ 2 arg max k2K i f p ki j2T k
j g .
- fp k.i/i P
j2T k.i/
j <0then y i D 1, z k.i/i D 1, z ki D 0; k 2 K i nf k.i/ g .
If p k.i/i P
j2T k.i/
j 0 then y i D 0, z ki D 0, k 2 K i .
Note that, for each feasible solution . O z ; O y/ to ( 3.32 )-( 3.34 ), for each i 2 I
there exists a one-to-one correspondence between . O y i ;. O z ki / k2K i /, and a vector
. O y i ;. O x ij / j2J /, that satisfies constraints ( 3.25 ). In particular, O x ij D P k2K i a ijk O z ki for
all i 2 I, j 2 J. Note that the above solution is well defined since for i 2 I there
is at most one k 2 K i with O z ki D 1. Furthermore, by definition of the z variables, for
i 2 I, . O x ij / j2J represents a feasible assignment to facility i,i.e. P j2J d j O x ij q i O y i .
Finally, the objective function values of the two solutions coincide since for i 2 I
fixed, P k2K i p ki O z ki D f i O y i C j2J c ij O x ij . Therefore, taking into account the above
considerations, L SPSFLP ./ can be rewritten as
0
@ f i y i C X
j2J
1
A X
j2J
X
i C minimize X
j2J
X
c ij x ij
j x ij
(3.35)
i2I
i2I
subject to X
j2J
d j x ij q i y i i 2 I
x ij 2f 0;1 g
i 2 I;j 2 J
y i 2f 0;1 g
i 2 I;
which is indeed L SFLP ./.
The reader will immediately conclude that a similar result holds for the MFLP.
Proposition 3.1 establishes that D SFLP and the LP relaxation of SPSFLP are
equally tight in terms of the lower bounds they produce (the same is true for D MFLP
and the LP relaxation of SPMFLP). Now, the question that arises naturally is how
to compare both types of formulations from an algorithmic point of view.
As we have seen, the Lagrangean subproblem L SFLP ./ is rather easy to solve
and subgradients are easy to compute at each point. For a given vector ,let
.y./;x.// denote an optimal solution to L SFLP ./. Then, a subgradient of
L SFLP ./ is given by ' D .' j / j2J ,where' j D 1 P i2I x ij ./. Therefore, D SFLP
can be efficiently solved with subgradient optimization. However, when looking
for an exact algorithm, the Lagrangean dual D MFLP may not be very handy within
an enumeration scheme. In contrast the LP relaxation of SPSFLP may be more
demanding than D SFLP from a computational point of view (the pricing subproblem
must be solved repeatedly to generate all the needed columns), but it can be very
Search WWH ::




Custom Search