Analysis of budget for interdiction on multicommodity network flows

Pengfei Zhang () and Neng Fan ()
Additional contact information
Pengfei Zhang: University of Arizona
Neng Fan: University of Arizona

Journal of Global Optimization, 2017, vol. 67, issue 3, No 3, 495-525

Abstract: Abstract In this paper, we concentrate on computing several critical budgets for interdiction of the multicommodity network flows, and studying the interdiction effects of the changes on budget. More specifically, we first propose general interdiction models of the multicommodity flow problem, with consideration of both node and arc removals and decrease of their capacities. Then, to perform the vulnerability analysis of networks, we define the function F(R) as the minimum amount of unsatisfied demands in the resulted network after worst-case interdiction with budget R. Specifically, we study the properties of function F(R), and find the critical budget values, such as $$R_a$$ R a , the largest value under which all demands can still be satisfied in the resulted network even under the worst-case interdiction, and $$R_b$$ R b , the least value under which the worst-case interdiction can make none of the demands be satisfied. We prove that the critical budget $$R_b$$ R b for completely destroying the network is not related to arc or node capacities, and supply or demand amounts, but it is related to the network topology, the sets of source and destination nodes, and interdiction costs on each node and arc. We also observe that the critical budget $$R_a$$ R a is related to all of these parameters of the network. Additionally, we present formulations to estimate both $$R_a$$ R a and $$R_b$$ R b . For the effects of budget increasing, we present the conditions under which there would be extra capabilities to interdict more arcs or nodes with increased budget, and also under which the increased budget has no effects for the interdictor. To verify these results and conclusions, numerical experiments on 12 networks with different numbers of commodities are performed.

Keywords: Multicommodity flow; Network vulnerability; Interdiction; Critical budget (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-016-0422-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jglopt:v:67:y:2017:i:3:d:10.1007_s10898-016-0422-8

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-016-0422-8

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().