Geoscience Reference
In-Depth Information
The proof which is based on Remark
3.1
is left to the reader. Formulation (
3.54
)-
(
3.57
)involves
j
m
j
binary variables y and
j
J
j
continuous variables . Its total
number of constraints is .m
C
1/
j
J
j
.
The reader familiar with Benders type reformulations (Benders
1962
) will
immediately observe that, in fact, constraints (
3.55
) are nothing but Benders cuts.
Thus formulation (
3.54
)-(
3.57
) admits an alternative interpretation as a Benders
type reformulation for the UFLP. The interested reader is addressed to the inspiring
chapter by Magnanti and Wong (
1990
) for an extensive description of the
application of Benders reformulations to the UFLP.
We close this section by interpreting SUFLP as a radius-based formulation.
Such formulations have been broadly used in recent years for different types of
location and hub location problems, after the work by Elloumi et al. (
2004
). Their
main characteristic is the use of decision variables to model the service cost for
customers. Using the above notation, in which, for j
2
J, c
i
r
j
denotes the rth
smallest allocation cost for customer j, we define a new set of binary decision
variables
z
rj
, r
D
1;:::;m,where
z
rj
D
1 if and only if the allocation cost of
customer j is at least c
i
r
j
. With these decision variables, the allocation cost of
customer j can be written as the telescopic sum c
i
1
j
C
P
rD2
.c
i
r
j
c
i
r1
j
/
z
rj
,so
that an alternative UFLP formulation is
c
i
1
j
C
.c
i
r
j
c
i
r1
j
/
z
rj
!
.
RUFLP
/v
R
D
minimize
X
i
f
i
y
i
C
X
j
X
m
(3.58)
2
I
2
J
r
D
2
z
rj
C
X
i
subject to
y
i
1
r
D
1;:::;m
C
1; j
2
J
I
c
ij
<c
i
r
j
2
(3.59)
z
rj
2f
0;1
g
j
2
J;r
D
1;:::;m
C
1
(3.60)
y
i
2f
0;1
g
i
2
I:
(3.61)
The equivalence between both formulations can be established by observing that
feasible solutions to SUFLP define feasible solutions to RUFLP and vice versa.
Indeed, if .;y/ is feasible for SUFLP we obtain a feasible RUFLP solution by
setting, for each j
2
J,
z
rj
D
0 for all r with c
i
r
j
j
, and zero otherwise.
Constraints (
3.55
) guarantee that .
z
;y/ satisfies constraints (
3.59
) and is feasible
for RUFLP. Conversely, we can also check that a feasible SUFLP solution can be
obtained from a feasible RUFLP solution by setting for, j
2
J,
j
D
c
i
r
j
with
r
D
arg min
f
c
i
r
j
W
y
i
r
D
1
g
.
