Geoscience Reference
In-Depth Information
24.3.1
The
r
-Interdiction Median Problem
In addition to the notation introduced in Sect.
24.2
, the mathematical formulation
of r-IMP requires the definition of the set T
ij
Df
k
2
F
j
d
kj
>d
ij
g
defined for
each facility i
2
I and customer j
2
J. T
ij
represents the set of existing sites that
are farther than i is from demand j.Ther-IMP can be formulated in the following
manner:
maximize
X
i2F
X
d
j
c
ij
x
ij
(24.1)
j2J
subject to
X
i2F
x
ij
D
1
8
j
2
J
(24.2)
X
s
i
D
r
(24.3)
i2F
X
x
kj
s
i
8
i
2
F;j
2
J
(24.4)
k2T
ij
x
ij
2f
0;1
g8
i
2
F;j
2
J
(24.5)
s
i
2f
0;1
g8
i
2
F:
(24.6)
The objective function (
24.1
) maximizes the demand-weighted total cost after the
interdiction of r facilities. Constraints (
24.2
) ensure that each customer is assigned
to a facility after interdiction. Constraints (
24.3
) stipulate that exactly R facilities
are to be interdicted. Constraints (
24.4
) force each customer j to be assigned to
its closest non-interdicted facility. Namely, this set of constraints prevents each
customer j from being assigned to facilities which are further than facility i, unless
facility i is interdicted. Finally, constraints (
24.5
)and(
24.6
) represent the binary
restrictions on the assignment and interdiction variables, respectively. Note that the
structure of the problem guarantees that there is always one optimal solution in
which all the x
ij
variables are binary, so that the integrality restrictions on these
variables can be relaxed.
In the above model the parameter r, i.e., the number of facilities that are lost
simultaneously in a particular event, is chosen as a metric of possible disruption.
In other words, r is used to capture the possible extent of a disruptive event: small
values are usually associated with low-impact but possibly frequent events, whereas
larger values are associated with disruptions which may affect a large number of
assets. Given the difficulty of estimating this parameter precisely, an analyst would
normally solve each model over a range of facility losses, r, in order to capture
the range of possible impacts to system operations. Using a loss parameter r makes
sense in modeling worst case disruptive scenarios due to natural events; however, in
a case of intentional disruption one may want to consider the fact that each facility
may require different amounts of resources to be completely disabled. For this type
