Exact methods for solving the elementary shortest and longest path problems

We consider in this paper the problems of finding the elementary shortest and longest paths on a graph containing negative and positive cycles. These problems are NP‐hard. We propose exact algorithms based on mixed integer programming for their solution, employing different valid inequalities. Moreover, we propose decomposition techniques which are very efficient for cases with special structure. Experimental results show the efficiency of our algorithms compared with state of the art exact algorithms.