A cut-based mixed integer programming formulation for the hop-constrained cheapest path problem

Abstract Given a simple graph $$G = (V,E)$$ with edge cost $$c \in \mathbb {R}^{|E|}$$ , a positive integer h , source $$s \in V$$ and terminal $$t \in V$$ , the hop-constrained cheapest path problem ( $$\operatorname {HCCPP}$$ ) seeks to find an $$s-t$$ path of length at most h hops with the cheapest cost. This paper proposes a cut-based mixed integer programming (MIP) formulation, which has only one set of constraints that capture connectivity and hop constraints simultaneously, to solve the $$\operatorname {HCCPP}$$ when edge costs are nonnegative. As the only set of constraints of the formulation has exponentially many constraints, we show that their corresponding fractional separation problem is easy for $$h \in \{2,3\}$$ and hard for $$h \ge 4$$ . We also propose a polytime algorithm for solving the integer separation problem. Furthermore, we show that our cut-based model is at least as strong as the jump-based model of Dahl ( Operations Research Letters , 1999), which results in perfectness of our proposed model for $$h \in \{2,3\}$$ . We finally conduct a brief set of computational experiments to compare the performance of the cut formulation against the jump model.