Shortest path interdiction problem with convex piecewise-linear costs

This paper addresses a special kind of network optimization interdiction problems, called the shortest path interdiction problem. The problem is a natural extension of the well-known shortest path problem in the presence of an adversary. The adversary is capable of increasing arc lengths under budge...

Full description

Saved in:
Bibliographic Details
Published in:Computational & applied mathematics 2023-10, Vol.42 (7), Article 309
Main Authors: Tayyebi, Javad, Deaconu, Adrian M., Bigdeli, Hamid, Niksirat, Malihe
Format: Article
Language:English
Subjects:
Algorithms
Applications of Mathematics
Applied physics
Computational mathematics
Computational Mathematics and Numerical Analysis
Linear functions
Mathematical analysis
Mathematical Applications in Computer Science
Mathematical Applications in the Physical Sciences
Mathematics
Mathematics and Statistics
Optimization
Polynomials
Shortest-path problems
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper addresses a special kind of network optimization interdiction problems, called the shortest path interdiction problem. The problem is a natural extension of the well-known shortest path problem in the presence of an adversary. The adversary is capable of increasing arc lengths under budget and bound constraints in a way that the shortest path length between two prescribed nodes becomes large as much as possible. This paper considers the problem in the case that the increment costs are convex piecewise-linear functions. It presents an algorithm which solve the problem in polynomial time. An applicable example and several randomly generated instances are presented to evaluate the performance and validity of the proposed algorithm.
ISSN:2238-3603
1807-0302
DOI:10.1007/s40314-023-02445-0