Formulations and branch-and-cut algorithms for cycle covers with up to p cycles

Given a positive integer p and a weighted undirected graph G=(V,E), we study a problem in which the objective is to find a minimum weight set of up to p elementary cycles partitioning the vertices of G. We study several exponentially sized formulations including (i) edge variables only; (ii) edge and depot variables only; (iii) edge, depot and node-depot assignment (NDA) variables only; (iv) edge, depot, NDA and edge-depot assignment (EDA) variables. New flow formulations are also introduced, and relations between all the formulations are established. Branch-and-cut algorithms based on many of these formulations are proposed, and computational experiments are conducted to compare the performance of the different algorithms. The computational testing reveals that some of the formulations including edge, depot and NDA or EDA variables produce the best initial lower bounds and that the best computational times are obtained with the algorithms based on formulations including edge and depot variables only. The best performing algorithm (in terms of computational times) is capable of solving several instances with up to 442 nodes for different values of p.