Formulations and algorithms for the simple cycle problem

doi:10.1007/s10589-025-00726-4

2025-09-01

PRE

Abílio Lucena *

Luidi Simonetti

Alexandre Salles da Cunha

DOI：10.1007/s10589-025-00726-4

原文链接

原文求助

摘要

En 中文

简单循环问题（SCP）是旅行商问题（TSP）的一个推广，要求在无向图中寻找一个最小边权的基环。它也是众多在交通、电信和调度领域有应用的问题背后的关键结构。与适用于TSP以及几乎所有现有TSP变种的情况不同，关于最优循环中的顶点数量，没有任何直接或间接的先验信息可用。同样，不需要预先指定的顶点属于该循环，也没有任何直接或间接的限制施加在其拓扑结构上，而这种情况在TSP变种中经常出现。部分受这些表述挑战的启发，我们在先前的研究中揭示了隐藏的SCP结构，并在问题表述中探索了它。现在，我们通过有效不等式显著加强了这一表述。此外，我们还引入了一种全新的表述，强制SCP遵守我们任意施加的方便、定制化的结构。我们在多面体和计算方面比较了我们改进的先前表述、新的表述以及文献中的两种额外表述。结果表明，通过我们两种表述揭示和创建的SCP结构似乎有所回报。在众多方面，在一个大且多样化的测试实例集中，我们的两种算法的表现远优于竞争对手。此外，我们为SCP所获得的表述和算法收益必将直接转移到以简单循环为关键结构的问题中。

Keyword:

Simple cycle problem

Formulations

Polyhedral comparisons

Branch-and-cut algorithms