A polyhedral study of the Hamiltonian p-median problem

Given an edge-weighted graph G = ( V , E ) , the Hamiltonian p-median problem (HpMP) asks for determining p cycles in G whose total length is minimized such that each node is contained in exactly one cycle. As the travelling salesman problem (TSP) corresponds to the choice p = 1 , the HpMP can be interpreted as a generalization of the TSP. In this paper, we study the polytope associated with the HpMP. To this end, we investigate several known classes of valid inequalities with respect to their facet inducing properties. Furthermore, we show that a subset of the well-known 2-matching inequalities from the TSP define facets of the Hamiltonian p-median polytope.