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)
Search WWH ::




Custom Search