Geoscience Reference
In-Depth Information
The above models work with a finite set of scenarios. In practice, however, this is
not always a correct representation for the uncertainty. In many situations, an uncer-
tain parameter can lie in some infinite set. A popular way of capturing uncertainty
in these cases is via intervals. In the general context of robust optimization, two
types of uncertainty sets are often considered: box and ellipsoidal uncertainty sets
(seeBen-Taletal.
2009
, for further details). In the first case, uncertainty is defined
by a set of linear constraints; in the second case, quadratic expressions involving
the uncertain parameters are used. We illustrate the use of box uncertainty sets
considering the uncapacitated facility location problem (UFLP), whose well-known
formulation is the following:
Minimize
X
i2I
f
i
y
i
C
X
i2I
X
c
ij
d
j
x
ij
(8.15)
j2J
subject to
X
i2I
x
ij
D
1; j
2
J
(8.16)
x
ij
y
i
; i
2
I; j
2
J
(8.17)
y
i
2f
0;1
g
; i
2
I
(8.18)
x
ij
0; i
2
I; j
2
J:
(8.19)
In this model, I denotes the set of potential locations for the facilities, J is the set
of customers, f
i
represents the setup cost for facility i
2
I, c
ij
corresponds to the
unitary cost for supplying the demand of customer j
2
J from facility i
2
I and
d
j
gives the demand of customer j
2
J. The binary variable y
i
indicates whether
a facility is installed at i
2
I, and the continuous variable x
ij
represents the fraction
of the demand of customer j
2
J that is supplied from facility i
2
I.
We consider now a common source of uncertainty in a facility location problem:
the demand. U
nd
er box u
nc
ertainty, each demand level, d
j
(j
2
J), lies in an
interval
B
j
D
Œd
j
j
;d
j
C
j
with 0
1. The parameter measures
the uncertainty “magnitude”; d
j
denotes a reference value for the demand of
customer j
2
J, and is commonly referred to as the nominal value for the unknown
parameter. Finally,
j
is a scaling factor.
A particular case
o
f box uncertainty that we consider for illustrative p
u
rposes
ari
se
s when
j
D
d
j
(j
2
J), which leads to the intervals
B
j
D
Œd
j
.1
/;d
j
.1
C
/ (j
2
J). Given these intervals, we can formulate the so-called robust
counterpart of model (
8.15
)-(
8.19
). Considering an auxiliary variable v, we can
rewrite the objective function of the problem as
Minimize v;
(8.20)