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

摘要

Let D=(V,A)documentclass[12pt]be a digraph with a set of vertices V, and a set of arcs A, with cij is an element of Rdocumentclass[12pt] representing the cost of each arc (i,j)is an element of Adocumentclass[12pt]. 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 is an element of Vdocumentclass[12pt], and t is an element of Vdocumentclass[12pt]. 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.