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.

中文翻译：

---

用于循环覆盖的公式和分支和切割算法，具有高达 [公式省略] 个循环


给定一个正整数 p 和一个加权无向图 G=（V，E），我们研究一个问题，其中目标是找到一个最多 p 个基本循环的最小权重集来划分 G 的顶点。我们研究了几种指数大小的公式，包括 （i） 仅边缘变量;（ii） 仅 edge 和 depot 变量;（iii） 仅限边、站点和节点-站点分配 （NDA） 变量;（iv） 边缘、仓库、NDA 和边缘仓库分配 （EDA） 变量。此外，还引入了新的流动公式，并建立了所有公式之间的关系。提出了基于其中许多公式的 branch-and-cut 算法，并进行了计算实验以比较不同算法的性能。计算测试表明，一些公式（包括边缘、仓库和 NDA 或 EDA 变量）产生最佳初始下限，并且最佳计算时间是使用基于公式（仅包括边缘和仓库变量）的算法获得的。性能最佳的算法（就计算时间而言）能够求解具有不同 p 值的多个实例，最多有 442 个节点。