An Implicit Optimization Approach for Survivable Network Design

Details An Implicit Optimization Approach for Survivable Network Design An Implicit Optimization Approach for Survivable Network Design

2011-09-08

arxiv.org/abs/1109.1801v1

Mathematics

Optimization and Control

Scientific paper

We consider the problem of designing a network of minimum cost while satisfying a prescribed survivability criterion. The survivability criterion requires that a feasible flow must still exists (i.e. all demands can be satisfied without violating arc capacities) even after the disruption of a subset of the network's arcs. Specifically, we consider the case in which a disruption (random or malicious) can destroy a subset of the arcs, with the cost of the disruption not to exceed a disruption budget. This problem takes the form of a tri-level, two-player game, in which the network operator designs (or augments) the network, then the attacker launches a disruption that destroys a subset of arcs, and then the network operator attempts to find a feasible flow over the residual network. We first show how this can be modeled as a two-stage stochastic program from the network operator's perspective, with each of the exponential number of potential attacks considered as a disruption scenario. We then reformulate this problem, via a Benders decomposition, to consider the recourse decisions implicitly, greatly reducing the number of variables but at the expense of an exponential increase in the number of constraints. We next develop a cut-generation based algorithm. Rather than \emph{explicitly} considering each disruption scenario to identify these Benders cuts, however, we develop a bi-level program and corresponding separation algorithm that enables us to \emph{implicitly} evaluate the exponential set of disruption scenarios. Our computational results demonstrate the efficacy of this approach.

Affiliated with

Also associated with

No associations

Rating

An Implicit Optimization Approach for Survivable Network Design does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Implicit Optimization Approach for Survivable Network Design, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Implicit Optimization Approach for Survivable Network Design will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-475734