Investing in the Links of a Stochastic Network to Minimize Expected Shortest Path. Length

Kannan Viswanath, Srinivas Peeta and Sibel F. Salman

Purdue University Economics Working Papers from Purdue University, Department of Economics

Abstract: We consider a network whose links are subject to independent, random failures due to a disruptive event. The survival probability of a link is increased, if it is strengthened by investment. A given budget is to be allocated among the links with the objective of optimizing the post-event performances of the network. Specifically, we seek to minimize the expected shortest path Length between a specified origin node and destination node in the network. This criterion is defined through the use of a fixed penalty cost for those network realizations in the expectation, that do not have a path connecting the origin node to the destination node. This problem type arises in the pre-disasters, by upgrading its weakest elements. We model the problem as a two-stage stochastic program in which the underlying probability distribution of the random variables is dependent on the first stage decision variables. Using a path-based approach we construct its equivalent deterministic program and derive structural results for the objective function. We then propose an approximate solution procedure based on a first order approximation the objective function. The procedure is tested by numerical experiments on a small-size network. The test results show that it yields very good performance on the instances solved.

Keywords: network vulnerability; decision dependent probability distribution; two-stage stochastic program; multilinear function (search for similar items in EconPapers)
Pages: 39 pages
Date: 2004-06
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
https://business.purdue.edu/research/Working-papers-series/Year-2004/1167.pdf
Our link check indicates that this URL is bad, the error code is: 404 Not Found (https://business.purdue.edu/research/Working-papers-series/Year-2004/1167.pdf [301 Moved Permanently]--> https://business.purdue.edu/research/working-papers-series/Year-2004/1167.pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pur:prukra:1167

Access Statistics for this paper

More papers in Purdue University Economics Working Papers from Purdue University, Department of Economics Contact information at EDIRC.
Bibliographic data for series maintained by Business PHD ().