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

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.