Geoscience Reference
In-Depth Information
problem, which is simply the r-IMP problem defined in Sect.
24.3
with the addi-
tional constraints (
24.16
). These constraints, which link the upper level protection
variables and the lower level interdiction variables, prevent the interdiction of any
protected facility.
It is important to note that in the above model protection resources can be cast
with a budget constraint and facility varying protection costs (Aksen et al.
2010
). It
is also possible to add the costs of protection as a an additional term in the objective,
where the costs of protection and costs of worst case operation are simultaneously
minimized. In either case (as formulated or as an added objective term), one would
generally want to solve a series of such problems in order to determine tradeoff
curves of system impacts versus protection resources. The above form can be
used to identify both supported and unsupported non-dominated solutions whereas
the latter will be effective in solving for only supported non-dominated solution.
In any case, one would want to understand exactly what protection provides in
terms of reducing impacts of interdiction as compared to the added costs of
protection.
Bilevel programs are generally very difficult to solve (Moore and Bard
1990
),
especially when integer variables appear in both levels and when the upper
level variables parametrize the feasible region of the lower level problem, as it
is the case in r-IMPF. Common approaches to solve bilevel integer programs
include reformulation into single level problems and decomposition methods.
Examples of casting r-IMPF as a single level problem can be found in Church
and Scaparra (
2007b
) and Scaparra and Church (
2008b
). However, these sin-
gle level models require a complete enumeration of all the possible ways of
interdicting r out of the
j
F
j
existing facilities and therefore become quickly
intractable as the value of the parameters
j
F
j
and r increases. Scaparra and
Church (
2008a
) propose an implicit enumeration algorithm to solve the bilevel r-
IMPF. The approach is based upon the observation that an optimal protection plan
must include at least one of the critical facilities identified by solving a simple
r-IMP. The recursive use of this property allows a significant reduction of the
number of protection strategies that must be evaluated in an enumeration scheme.
To date, this algorithm remains one of the most effective methods for solving
this type of protection/interdiciton models and has been successfully applied to
problems in different settings as well (e.g., the network protection models in
Cappanera and Scaparra
2011
).
Since its appearance, the r-IMPF has spurred a significant amount of research
and several different variants to the original problem have been proposed in the
literature. As an example, Liberatore et al. (
2010
) introduced a stochastic version
of r-IMPF where the number of possible losses r is uncertain, to reflect the fact
that the extent of a disruption is usually not known with certainty. In a follow
up paper, Liberatore and Scaparra (
2011
) compared the model proposed for the
above stochastic problem with two regret-based models to identify robust protection
strategies in uncertain environments.
Aksen et al. (
2010
) proposed a budget-constrained version of the r-IMPF with
flexible capacity expansion. In particular, they replaced the cardinality constraint
