Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles

摘要

In this paper, we discuss exact algorithm for the shortest elementary path problem in digraphs containing negative directed cycles. We investigate various classes of valid inequalities for the polytope of elementary paths in digraphs. The problem of separation of these valid inequalities can be shown to be NP-hard, thus only solvable for small sized problems. To deal with larger problems, lifting techniques are proposed. We provide results of computational experiments to show the efficiency of lifted inequalities in reducing the integrality gap. Indeed, considering a series of difficult test examples, the integrality gap is shown to be closed in about half of the cases within no more than ten rounds of cutting plane generation.