{"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","summary":"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.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-17","reactions":{}}