Exact methods for solving the elementary shortest and longest path problems

Quoc Trung Bui

doi:10.1007/s10479-016-2116-5

Exact methods for solving the elementary shortest and longest path problems

2016-02-12

5

PRE

AI

DOI：10.1007/s10479-016-2116-5

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Elementary shortest path

Elementary longest path

Negative cycles

Mixed integer programming

Decomposition

Exact methods for solving the elementary shortest and longest path problems

Abstract

Journal

Organization