The Hamiltonian p-median problem is to partition the n vertices of a graph G into p cycles of minimum total weight.
We strengthen the corresponding MILP on edge variables with two families of inequalities: quasi-Hamiltonian cycle inequalities associated to cycles not spanning all nodes; restricted cut constraints whose shores have specific cardinalities and are valid when n=3p,3p+1.
We give facet-defining conditions for subsets of these inequalities.
We develop a branch-and-cut algorithm also enhanced by cost-based inequalities.
It compares well to existing algorithms for the problem and solves 3 benchmark instances previously unsolved and 16 new larger instances with up to 400 vertices.