  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-and-price
approach. We use a dynamic programming-based pricing algorithm to generate
improving cycles, exploiting the particular structure of the pricing problem
for efficient bidirectional search and symmetry breaking. Computational results
show that the LP relaxation of the set partitioning model produces strong dual
bounds and our branch-and-price method improves significantly over the state of
the art. It is able to solve closed instances in a fraction of the previously
needed time and closes 13 previously unsolved instances, one of which has 76
nodes, a notable improvement over the previous limit of 52 nodes.
