Arc-dependent networks: theoretical insights and a computational study

Alvaro Velasquez (), P. Wojciechowski (), K. Subramani () and Matthew Williamson ()
Additional contact information
Alvaro Velasquez: University of Colorado
P. Wojciechowski: West Virginia University
K. Subramani: West Virginia University
Matthew Williamson: Marietta College

Annals of Operations Research, 2024, vol. 338, issue 2, No 11, 1126 pages

Abstract: Abstract In this paper, we study the efficacy of several mathematical programming formulations for the single-source shortest path problem, the negative cost cycle detection problem, and the shortest negative cost cycle problem in arc-dependent networks. In an arc-dependent network, the cost of an arc a depends upon the arc preceding a. These networks differ from traditional networks in which the cost associated with an arc is a fixed constant and part of the input. Arc-dependent networks are useful for modeling a number of real-world problems, such as the turn-penalty shortest path problem, which cannot be captured in the traditional network setting. We present new integer and non-linear programming formulations for each problem. We also perform the first known empirical study for arc-dependent networks to contrast the execution times of the two formulations on a set of graphs with varying families and sizes. Our experiments indicate that although non-linear programming formulations are more compact, integer programming formulations are more efficient for the problems studied in this paper. Additionally, we introduce a number of cuts for each integer programming formulation and examine their effectiveness.

Keywords: Arc-dependent networks; Shortest path; Negative cycle; Integer programming; Non-linear programming; 90C10; 90C30; 68R15; 65K05 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-024-05910-z 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:annopr:v:338:y:2024:i:2:d:10.1007_s10479-024-05910-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-024-05910-z

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().