A complete characterization of jump inequalities for the hop-constrained shortest path problem

Considering an integer k and a directed, weighted graph with two distinct nodes s and  t, the Hop-Constrained Shortest Path Problem looks for a shortest (s,t)-path using at most k arcs. In this paper, we study the polytope of the convex hull of incidence vectors of (s,t)-paths using at most k arcs. We present valid inequalities and adaptations of known concepts such as cloning and a unique representation of facets. The main focus will be on one particular family of valid inequalities, the family of Jump Inequalities. Thereby, the main contribution will be a characterization of the members of the family inducing facets. Furthermore, all possibilities to lift the remaining inequalities will be defined. The analysis of Jump Inequalities will be concluded by further results concerning the equivalence of inequalities as well as their Chvátal rank.