Decomposition Algorithms for the Elementary Shortest Path Problem in Networks Containing Negative Cycles

Abstract

The Elementary Shortest Path Problem in Networks containing Negative Cycles (ESPPNC) is an NP-hard problem. Although there are exact formulation approaches to solve the ESPPNC, a decomposition setting for this problem has not been explored. In this thesis, two Decomposition and Branch-and-Cut (DBC) algorithms to solve the ESPPNC in directed networks are proposed. A master relaxation of the ESPPNC is presented and later strengthened by adding negative cycle elimination constraints in a branch-and-bound framework. The scalability of these approaches is analyzed by extracting their running times on two different test-beds. Also, the performance of these approaches is compared against the performance of an exact formulation on the same test-beds. From the results, the DBC approaches are able to solve all the instances much faster than the exact formulation approach, so the DBC algorithms scale much better than direct formulation in these test-beds. However, a pathological instance is also identified for which the direct formulation is the favorable approach.