A strong flow-based formulation for the shortest path problem in digraphs with negative cycles

In this paper, we are interested in the shortest path problem between two specified vertices in digraphs containing negative cycles. We study two integer linear formulations and their linear relaxations. A first formulation, close in spirit to a classical formulation of the traveling salesman problem, requires an exponential number of constraints. We study a second formulation that requires a polynomial number of constraints and, as confirmed by computational experiments, its linear relaxation is significantly sharper. From the second formulation we propose a family of linear relaxations with fewer variables than the classical linear one.