MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles

Rafael Castro Andrade () and Rommel Dias Saraiva ()
Additional contact information
Rafael Castro Andrade: Federal University of Ceará
Rommel Dias Saraiva: Federal University of Ceará

Annals of Operations Research, 2020, vol. 286, issue 1, No 7, 147-172

Abstract: Abstract Let $$D=(V,A)$$D=(V,A) be a digraph with a set of vertices V, and a set of arcs A, with $$c_{ij} \in {\mathbb {R}}$$cij∈R representing the cost of each arc $$(i,j) \in A$$(i,j)∈A. The problem of finding the shortest-path avoiding negative cycles (SPNC) is NP-hard and consists in determining, if it exists, a path of minimum cost between two distinguished vertices $$s \in V$$s∈V, and $$t \in V$$t∈V. We propose three exact solution approaches for SPNC, including a compact primal-dual model, a combinatorial branch-and-bound algorithm, and a cutting-plane method. Extensive computational experiments performed on both benchmark and randomly generated instances indicate that our approaches either outperform or are competitive with existing mixed-integer programming models for the SPNC while providing optimal solutions for challenging instances in small execution times.

Keywords: Shortest path in the presence of negative cycles; Compact primal-dual model; Combinatorial branch-and-bound; Cutting-plane (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-017-2743-5 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:286:y:2020:i:1:d:10.1007_s10479-017-2743-5

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

DOI: 10.1007/s10479-017-2743-5

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 ().