Analysis of budget for interdiction on multicommodity network flows

Pengfei Zhang, Neng Fan

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


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 Ra, the largest value under which all demands can still be satisfied in the resulted network even under the worst-case interdiction, and Rb, the least value under which the worst-case interdiction can make none of the demands be satisfied. We prove that the critical budget Rb 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 Ra is related to all of these parameters of the network. Additionally, we present formulations to estimate both Ra and Rb. 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.

Original languageEnglish (US)
Pages (from-to)495-525
Number of pages31
JournalJournal of Global Optimization
Issue number3
StatePublished - Mar 1 2017


  • Critical budget
  • Interdiction
  • Multicommodity flow
  • Network vulnerability

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research
  • Control and Optimization
  • Applied Mathematics


Dive into the research topics of 'Analysis of budget for interdiction on multicommodity network flows'. Together they form a unique fingerprint.

Cite this