Formulations and algorithms for the simple cycle problem

doi:10.1007/s10589-025-00726-4

Formulations and algorithms for the simple cycle problem

2025-09-01

0

PRE

AI

Alexandre Salles da Cunha

DOI：10.1007/s10589-025-00726-4

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Simple cycle problem

Formulations

Polyhedral comparisons

Branch-and-cut algorithms

Formulations and algorithms for the simple cycle problem

Abstract

Journal

Organization