A Numerically-safe Branch-Price-and-Cut Algorithm for the Length-Constrained Cycle Partition Problem
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.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.15837
curl -X POST /api/v1/records/arxiv/2607.15837/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.15837/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'