The Minimum Flow Cost Hamiltonian Cycle Problem: A comparison of formulations

We introduce the Minimum Flow Cost Hamiltonian Cycle Problem (FCHCP). Given a graph and positive flow between pairs of vertices, the FCHCP consists of finding a Hamiltonian cycle that minimizes the total flow cost between pairs of vertices through the shortest path on the cycle. We prove that the FCHCP is NP-hard and we study the polyhedral structure of its set of feasible solutions. In particular, we present five different mixed integer programming formulations which are theoretically and computationally compared. We also propose several families of valid inequalities for one of the formulations and perform some computational experiments to assess the performance of these inequalities.