Scholarlink

<p>The Simple Cycle Problem (SCP) is a generalization of the Travelling Salesman Problem (TSP) that asks for a minimum edge-weighted elementary cycle of an undirected graph. It is also the key structure behind numerous problems with applications to transportation, telecommunications and scheduling. Contrary to what applies to TSP and virtually every existing TSP variant, no direct or indirect prior information is available on the number of vertices in an optimal cycle. Likewise, no predefined vertex is required to belong to the cycle nor any restriction is directly or indirectly imposed on its topology, as it frequently occurs for TSP variants. Motivated in part by these formulation challenges, we have, in a previous contribution, uncovered hidden SCP structure and explored it in a formulation to the problem. Now, we significantly reinforce this formulation with valid inequalities. Additionally, we also introduce an entirely new formulation that <i>forces</i> SCP to abide to a convenient, tailor-made, structure we arbitrarily impose on it. We compare our improved previous formulation with the new one and two additional formulations from the literature in both polyhedral and computational terms. The results indicate that uncovering and creating structure for SCP, as enforced by our two formulations, appears to pay off. Among others, over a large and varied test bed of instances, our two algorithms performed much better than their competitors. Furthermore, the formulation and algorithmic gains we attained for SCP are bound to be directly transferred to problems where simple cycles are the key structure involved.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Formulations and algorithms for the simple cycle problem

  • 期刊论文

  • 发表日期：

    2025年9月6日

查看全文
  • Abilio Lucena,
  • Luidi Simonetti,
  • Alexandre Salles da Cunha

摘要

The Simple Cycle Problem (SCP) is a generalization of the Travelling Salesman Problem (TSP) that asks for a minimum edge-weighted elementary cycle of an undirected graph. It is also the key structure behind numerous problems with applications to transportation, telecommunications and scheduling. Contrary to what applies to TSP and virtually every existing TSP variant, no direct or indirect prior information is available on the number of vertices in an optimal cycle. Likewise, no predefined vertex is required to belong to the cycle nor any restriction is directly or indirectly imposed on its topology, as it frequently occurs for TSP variants. Motivated in part by these formulation challenges, we have, in a previous contribution, uncovered hidden SCP structure and explored it in a formulation to the problem. Now, we significantly reinforce this formulation with valid inequalities. Additionally, we also introduce an entirely new formulation that forces SCP to abide to a convenient, tailor-made, structure we arbitrarily impose on it. We compare our improved previous formulation with the new one and two additional formulations from the literature in both polyhedral and computational terms. The results indicate that uncovering and creating structure for SCP, as enforced by our two formulations, appears to pay off. Among others, over a large and varied test bed of instances, our two algorithms performed much better than their competitors. Furthermore, the formulation and algorithmic gains we attained for SCP are bound to be directly transferred to problems where simple cycles are the key structure involved.