Exact methods for solving the elementary shortest and longest path problems
(2016) Annals of Operations Research — Vol. 238, n° 1, p. 1-36 (2016)
Files
main.pdf
Open Access - Adobe PDF
- 1.14 MB
Details
- Authors
- Abstract
- 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
- Affiliations
Citations
Bui, Q. T., Deville, Y., & Pham, Q. D. (2016). Exact methods for solving the elementary shortest and longest path problems. Annals of Operations Research, 238(1), 1-36. https://doi.org/10.1007/s10479-016-2116-5 (Original work published 2016)