🔢 mathematics

A Numerically-safe Branch-Price-and-Cut Algorithm for the Length-Constrained Cycle Partition Problem

This paper presents a numerically safe branch-price-and-cut algorithm with an efficient dynamic programming pricing strategy that significantly outperforms existing methods for the length-constrained cycle partition problem, solving larger instances and closing previously unsolved cases.

Original authors: Mohammed Ghannam, Ambros Gleixner, Gioni Mexi, Edward Lam

Published 2026-07-20✓ Author reviewed ⓘ

📖 3 min read🧠 Deep dive

CC BY 4.0

Original authors: Mohammed Ghannam, Ambros Gleixner, Gioni Mexi, Edward Lam

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a fleet of delivery drones. Each delivery stop on your map must be visited regularly and has a very specific, non-negotiable rule: it has a "critical time," which is the maximum amount of time that can pass before that specific location must be serviced again. Some locations are extremely urgent and require immediate attention, while others are less time-sensitive and can wait longer. Your job is to figure out the most efficient way to group all your delivery stops into loops. You want to use as few drones as possible, but every loop you create must be short enough that the most urgent location in that loop—the one with the shortest critical time—can still be reached and serviced within its limit. This is a puzzle of geometry and timing, a problem that mathematicians call the "Length-Constrained Cycle Partition Problem." It's the kind of challenge that shows up in real life, like scheduling security patrols for a city or organizing kidney exchanges, but solving it perfectly is notoriously difficult. It's like trying to solve a massive jigsaw puzzle where the pieces keep changing shape depending on how you try to fit them together.

This paper introduces a new, super-smart way to solve that puzzle, one that is not only faster but also incredibly careful about its math. The authors, a team of researchers from Germany and Australia, built a "branch-price-and-cut" algorithm. Think of this as a detective who doesn't just guess where the clues are but systematically builds a map of every possible solution, cutting away the impossible ones and "pricing" the promising ones to find the absolute best route. Their secret weapon is a technique called "column generation," which is like building a house by only ordering the specific bricks you need right now, rather than trying to haul a whole mountain of bricks to the site at once. They also added a "numerical safety" feature, which is like a double-check system that ensures the computer doesn't make tiny rounding errors that could lead to a wrong answer.

The results are impressive. The team tested their method on 84 different puzzle instances, ranging from small setups with 14 nodes to massive ones with 100 nodes. Their new algorithm managed to solve 52 of these instances to proven perfection, including one with 76 nodes—a size that had never been solved before (the previous record was 52 nodes). They closed 14 instances that were previously unsolvable. In terms of speed, their method was, on average, 14.7 times faster than the best previous approach. They found that the most important tricks were "symmetry breaking" (telling the computer not to waste time checking the same loop twice just because it started from a different point) and a "bidirectional search" (building the loop from both ends at once and meeting in the middle). While they tried adding extra "cutting planes" (mathematical rules to prune bad options), they found that for most cases, the puzzle was already so tight that these extra rules didn't help much and sometimes even slowed things down. The paper concludes that while they have cracked the code for up to 76 nodes, the real bottleneck is now the speed of the pricing routine, and solving even larger puzzles will likely require even more powerful computing tricks.

Technical Summary: A Numerically-safe Branch-Price-and-Cut Algorithm for the Length-Constrained Cycle Partition Problem

1. Problem Definition

The Length-Constrained Cycle Partition Problem (LCCP) is a graph optimization problem defined on an undirected graph $G=(V, E)$ . The objective is to partition the set of nodes $V$ into the minimum number of disjoint cycles such that every node $i$ is covered exactly once.

Each node $i$ is associated with a critical time $q_i > 0$ , and each edge $\{i, j\}$ has a travel time $t_{i,j} \ge 0$ . A cycle $C$ is length-feasible if its total travel time does not exceed the critical time of any node contained within it:
$t(C) := \sum_{\{i,j\} \in C} t_{i,j} \le \min_{i \in C} \{q_i\}$
The problem is known to be NP-hard (reducible from the Traveling Salesman Problem) and admits no polynomial-time approximation algorithm. Previous state-of-the-art approaches utilized compact Mixed-Integer Programming (MIP) formulations (based on Miller-Tucker-Zemlin or Subtour Elimination Constraints) which could solve instances up to 52 nodes.

2. Methodology

The authors propose an exact Branch-Price-and-Cut (BPC) algorithm based on a Set Partitioning (SP) formulation.

2.1 Set Partitioning Formulation

Instead of compact formulations, the problem is modeled as a set partitioning problem where variables represent entire length-feasible cycles. Let $\Omega$ be the set of all length-feasible cycles. The formulation minimizes $\sum_{C \in \Omega} \lambda_C$ subject to covering constraints $\sum_{C \in \Omega} a^C_i \lambda_C = 1$ for all $i \in V$ . Due to the exponential size of $\Omega$ , the authors employ Column Generation to solve the Linear Programming (LP) relaxation dynamically.

2.2 The Pricing Problem (LCPCCP)

The core computational task is the Length-Constrained Prize-Collecting Cycle Problem (LCPCCP), which seeks a cycle with negative reduced cost. This problem is strongly NP-hard. The authors solve it using:

Dynamic Programming (DP): A label-setting algorithm where labels track visited nodes, reduced cost, total travel time, and the minimum critical time of the path.
Bidirectional Search: Exploiting the undirected nature of the graph, the algorithm extends labels from a start node $s$ only until $t(\ell) < q(\ell)/2$ . Non-dominated labels from forward and backward searches are then merged to form full cycles. This significantly reduces the search space compared to monodirectional search.
Dominance Rules: Labels are pruned if another label at the same node has lower or equal reduced cost, lower or equal travel time, and a subset of visited nodes.
ng-Relaxation: To handle non-elementary cycles (revisiting nodes), the authors use an ng-path relaxation with dynamic neighborhood expansion. This provides valid lower bounds while avoiding the complexity of enforcing elementarity strictly during the initial search phases.
Greedy Heuristic: A fast heuristic is run first to find improving cycles by removing negative dual nodes or inserting positive dual nodes, reducing the need for expensive DP iterations.

2.3 Exploiting Structure

Triangle Inequality: For nodes where the triangle inequality holds locally, the authors switch to set covering constraints. This restricts dual variables to be non-negative, allowing the removal of zero-dual nodes during pricing and enabling preemptive pruning.
Symmetry Breaking: To avoid generating the same cycle from different starting nodes, the search is restricted to visit only nodes with critical times greater than or equal to the start node's critical time (with index tie-breaking).

2.4 Cutting Planes

The algorithm integrates two families of cuts:

Subset Row Cuts (SRCs): Applied to subsets of nodes to limit the number of cycles covering them.
Clique Cuts (CCs): Based on the conflict graph of cycles.
The authors investigate respecting these cuts within the pricing problem. They find that while Clique cuts are ignored in pricing to avoid complexity, Subset Row cuts are respected by augmenting labels with additional resources, which improves convergence on specific difficult instances.

2.5 Numerical Safety

A key contribution is the implementation of numerically safe bounds. Floating-point arithmetic can lead to infeasible dual solutions due to rounding errors. The authors propose a dual repair mechanism:

Scale floating-point duals to large integers.
Verify dual feasibility exactly using integer arithmetic.
If infeasible, reduce the scaling factor and retry.
This ensures that the lower bounds used for branching are mathematically rigorous, preventing the algorithm from claiming optimality based on numerical artifacts.

2.6 Branching and Heuristics

Branching: Primarily uses Edge Branching (fixing edges to be in or out of the solution). Ryan-Foster branching (on node pairs) was tested but found to be less robust for this specific problem structure.
Heuristics: A heuristic branch-and-price variant relaxes dominance rules to find high-quality primal solutions quickly, which are then used as warm starts for the exact solver.

3. Key Contributions

Set Partitioning Formulation: Demonstrates that an SP-based approach yields significantly tighter LP relaxations (average root gap of 0.4%) compared to previous compact formulations (30.3% gap).
Bidirectional DP Pricing: Introduces an efficient bidirectional search for the LCPCCP pricing problem, leveraging the symmetry of undirected graphs to cut the search space.
Numerical Safety: Provides a framework for obtaining provably correct lower bounds in a branch-and-price setting by combining floating-point solvers with exact integer arithmetic for dual verification.
Algorithmic Integration: Combines greedy pricing, ng-relaxation, symmetry breaking, and specific cut management into a cohesive solver.

4. Computational Results

The algorithm was tested on 84 benchmark instances (14 to 100 nodes) against the previous state-of-the-art branch-and-cut method (bnc-sec).

Performance: The proposed Branch-Price-and-Cut algorithm (specifically the configuration withsrc+pricing) solved 52 instances to proven optimality, compared to 40 for the previous best method.
Scale: It successfully solved instances with up to 76 nodes, closing 14 previously unsolved instances. The previous limit was 52 nodes.
Speed: The branch-and-price core is on average 14.7 times faster than the previous best approach.
Root Node Efficiency: 49 out of the 52 solved instances were resolved at the root node without branching, highlighting the strength of the LP relaxation.
Numerical Safety Overhead: The numerically safe version solved the same number of instances as the unsafe version but was approximately 40% slower (7.6s vs 4.5s geometric mean). However, no incorrect results were detected in the unsafe version, and the overhead is considered moderate given the guarantee of correctness.

5. Significance and Claims

The paper claims that the set partitioning formulation is the primary driver of performance, providing tight bounds that allow most instances to be solved at the root node. The bidirectional search and symmetry breaking are identified as the most impactful algorithmic components for reducing runtime.

The authors modestly note that while the method significantly improves the state of the art, instances beyond 76 nodes remain unsolved, and the pricing routine remains the computational bottleneck. They suggest that future improvements may require stronger dual bounds or more scalable pricing algorithms (e.g., GPU acceleration). The work establishes a new benchmark for solving LCCP, proving that exact methods can handle larger, more complex instances when combined with numerically safe, structure-exploiting techniques.