On the directed hop-constrained shortest path problem

In this paper we discuss valid inequalities for the directed hop-constrained shortest path problem. We give complete linear characterizations of the hop-constrained path polytope when the maximum number of hops is equal to 2 or 3. We also present a lifted version of the “jump” inequalities introduced by Dahl and show that this class of inequalities subsumes inequalities contained in the complete linear description for the case H=3 as well as a large class of facet defining inequalities for the case H=4. We use a minmax result by Robacker to present a framework for deriving a large class of cut-like inequalities for the hop-constrained path problem. A simple relation between the hop-constrained path polytope and the knapsack polytopes is also presented.