Id: arxiv/2607.15837 Url: https://arxiv.org/abs/2607.15837 Tags: math.OC, cs.DM Score: 0 Title: A Numerically-safe Branch-Price-and-Cut Algorithm for the Length-Constrained Cycle Partition Problem Domain: math.OC Source: arxiv Authors: Mohammed Ghannam, Ambros Gleixner, Gioni Mexi, Edward Lam Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-17 Page: https://delphi.science/r/arxiv/2607.15837 The length-constrained cycle partition problem (LCCP) is a graph optimization problem in which a set of nodes must be partitioned into a minimum number of cycles. Every node is associated with a critical time and the length of every cycle must not exceed the critical time of any node in the cycle. We formulate LCCP as a set partitioning model and solve it using an exact branch-price-and-cut approach. Our dynamic programming-based pricing algorithm to generate improving cycles exploits the particular structure of the pricing problem for efficient bidirectional search and symmetry breaking.…