Maximum Capacity Path Interdiction Problem with Fixed Costs

Abumoslem Mohammadi () and Javad Tayyebi
Additional contact information
Abumoslem Mohammadi: Department of Mathematics, Faculty of Sciences, Imam Ali University, Tehran, Iran
Javad Tayyebi: Department of Industrial Engineering, Birjand University of Technology, Birjand, Iran

Asia-Pacific Journal of Operational Research (APJOR), 2019, vol. 36, issue 04, 1-21

Abstract: This paper addresses a network optimization interdiction problem, called the maximum capacity path interdiction problem. The problem is a hierarchical game containing two players: one evader and one interdictor. In a capacitated network, the evader wants to find a simple path from his current position to a target point with maximum capacity to send his forces along it while the interdictor decreases arc capacities under a budget constraint to interdict the advance of the evader’s forces as much as possible. This paper studies the case that each arc has a fixed cost for decreasing its capacity. An algorithm is proposed to solve the problem in strongly polynomial time. Computational experiments on two real-world datasets guarantee the efficiency and accuracy of the algorithm.

Keywords: Networks; interdiction problems; robust optimization; Stackelberg game; minimum cut (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595919500180
Access to full text is restricted to subscribers

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:wsi:apjorx:v:36:y:2019:i:04:n:s0217595919500180

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595919500180

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().