Large routing problems are usually solved by cutting the instance into regions, solving each region, and stitching the pieces together. The weak point is the cut. If the best tour actually weaves back and forth across a region boundary, every downstream solver is optimizing the wrong subproblem, and no amount of local polishing can fix it. We propose to check, for each candidate region, whether the optimal solution can cross its boundary more often than it must. The check is a cheap lower-bound computation. If crossing even once more than the minimum provably costs more than a tour already in hand, the region is certified: it can be solved in isolation with no loss of optimality. Only uncertified boundaries then receive repair effort.
The idea borrows its logic from perturbation resilience. That literature studies instances whose optimal solution does not change when the input is scaled by a bounded factor, and it has shown that such instances split into exactly solvable pieces. So far this splitting has been proven only for clustering, where optimal clusters form contiguous pieces of a spanning tree (Metric Perturbation Resilience). Routing solvers, by contrast, split instances with coordinate heuristics that carry no guarantee. Our claim is that a per-boundary, per-instance version of resilience can be computed for travelling-salesperson and vehicle-routing instances. On structured benchmarks it should certify a large share of a hierarchical decomposition. Spending search effort only where certificates fail should then beat both whole-instance heuristics and uncertified decomposition at equal time.
Core Claim
Take a travelling-salesperson instance with edge costs $c$, an incumbent tour of cost $U$, and a candidate region $S$. Any tour enters and leaves $S$ at least once, so it crosses the cut $\delta(S)$ at least twice. Let $L_4(S)$ be a valid lower bound on the cost of every tour that crosses $\delta(S)$ at least four times. We compute it as a Held–Karp style Lagrangian 1-tree bound, with the extra constraint $x(\delta(S)) \ge 4$ added to the dual. If $L_4(S) > U$, every optimal tour visits $S$ in one contiguous stretch. The global problem then separates exactly into a Hamiltonian path inside $S$ and a tour over the contracted rest, coupled only through the choice of two endpoints.
The size of the certificate's slack translates directly into a perturbation radius. Suppose every edge cost is scaled by some factor in $[1/\alpha, \alpha]$. The best crossing tour then costs at least $L_4(S)/\alpha$, and the best contiguous tour costs at most $\alpha U$. The region therefore stays contiguous in every such perturbed instance whenever
$$\alpha < \sqrt{L_4(S)/U}.$$
This gives each boundary a measured local resilience factor. It is the routing analogue of the locally stable clusters of Certified Algorithms: Worst-Case Analysis and Beyond, with one difference: we output an explicit certificate saying which pieces are stable, which that paper does not.
For capacitated vehicle routing (CVRP, where each vehicle has a load limit $Q$ and customers have demands $d$), the same construction applies with a different threshold. The minimum crossing count is $2\lceil d(S)/Q\rceil$, the rounded capacity bound. The certificate asks whether requiring $x(\delta(S)) \ge 2\lceil d(S)/Q\rceil + 2$ pushes the lower bound above the incumbent. If it does, no optimal route mixes $S$ with outside customers beyond the forced minimum.
Relation to Prior Work
Three clustering papers motivate the approach and supply its structure. Metric Perturbation Resilience shows that 2-resilient clusters are contiguous subtrees of a minimum spanning tree, which dynamic programming can then recover. Clustering under Perturbation Resilience builds an analogous tree with closure-distance linkage, and Massively Parallel k-Means Clustering for Perturbation Resilient Instances distributes subtree dynamic programs across machines in a constant number of rounds. All three assume a global resilience factor, which is at least 2 and exceeds 6.1 in the parallel case. They restrict themselves to center-based objectives and offer no test of whether a given real instance satisfies the assumption. Where the assumption fails, the parallel paper reports only costs within 1.2x to 1.6x of k-means++. We keep their tree backbone, which we build from distances alone so it also works on non-Euclidean matrices. We replace the global assumption with a certificate checked at each tree node.
Graph Cuts Always Find a Global Optimum for Potts Models (With a Catch) is the closest methodological precedent. It uses linear-programming certification to bound how far a local minimum is from the optimum under perturbation, tightening the Hamming error bound on tsukuba from 82.1% to 29.0%. That paper warns that certification is expensive. Our bound is a Lagrangian 1-tree rather than a full integer program, precisely so that it can run at every tree node.
Decomposition-based routing supplies the application regime and the main competitors. Select and Optimize chooses sub-paths to re-optimize with a Transformer and escapes local minima with random destroy-and-repair. Imitation Improvement Learning for Large-Scale CVRP splits instances by clockwise angular sorting around the depot. That paper reports that this split degrades on the non-Euclidean DIMACS matrices, where no coordinates exist. Neither method knows whether its boundaries are correct.
Theoretical Challenges in Learning for Branch-and-Cut constrains the design. It shows that $k$ wrong decisions in a recursive search can inflate the search tree by $2^{\Omega(k)}$. A certified split is by construction never a wrong decision, so only uncertified splits can contribute to this amplification. This is the practical reason to separate the two kinds of split.
Research Program
We will build a hierarchical decomposition in three steps. First, construct a single-linkage tree on the distance matrix. Second, evaluate the boundary certificate at each tree node, top-down, against an incumbent from a fast heuristic, re-certifying as the incumbent improves. Third, contract certified regions and solve them independently. For the travelling-salesperson problem this means a small dynamic program over endpoint pairs, followed by exact or LKH-style solution of each region's path.
Uncertified boundaries form a residual "frontier". A destroy-and-repair loop concentrates on this frontier, removing and reinserting customers near uncertified cuts. This addresses the file's gap about random repair schedules: repair effort is directed by measured stability rather than by random choice.
We will also study how certificates behave: what fraction of tree nodes certify, how the measured $\alpha$ is distributed on real versus synthetic instances, and how often the certificate misses regions that the known optimum actually visits contiguously.
Baselines
The naive reference is to run the whole instance, with no decomposition, through the same underlying improvement heuristic we use inside regions. On the travelling-salesperson problem that heuristic is LKH3; on CVRP it is hybrid genetic search (HGS). Both get the same wall-clock budget and hardware as our full pipeline, including certification time. This baseline answers whether decomposition helps at all at a given budget.
The strongest existing CVRP method in the file is the IIL+HGS pipeline of Imitation Improvement Learning. It reports a gap of −0.27% against best-known solutions on the Uchoa et al. set, where classical HGS with 30k steps reaches −0.30%. It is the strongest competitor because it is the only method in the file that decomposes and then applies HGS on instances of up to 30,000 customers. We will run the authors' clockwise decomposition and ours on identical instances, with the same inner HGS and equal time, and report gap against best-known solutions. Beating it means a lower gap at equal time on the Arnold et al. 3,000–30,000 customer set, and not losing on DIMACS. On the Li et al. set the file gives only a qualitative claim of beating learning-to-delegate, so no reported number is available there.
For the travelling-salesperson problem, the decomposition baseline is Select and Optimize, run on its TSPLIB groups (1,000–2,000 and 2,000–6,000 cities) and its generated instances up to 20,000 cities. The paper reports an over-2x speedup against learning methods, but no optimality-gap value for it is found on Lacuna.
The key ablation keeps our tree, contraction and frontier repair but changes how boundaries are chosen for certification or repair. In one variant, boundaries are ranked by an uncertified score. In a second, they are ranked by empirical instability, measured by perturbing costs by a random factor, re-solving, and counting crossings. The time budget is the same. If the Lagrangian certificate adds nothing over these cheaper stability proxies, the ablation will show it.
Why not just…?
Why not just use geometric partitioning with repair, as current large-scale solvers do? It depends on coordinates, and Imitation Improvement Learning itself reports degradation on DIMACS matrices. It also cuts through dense interactions: Select and Optimize needed Lin-Kernighan and random destroy-and-repair to escape the traps its initial split created. The DIMACS and clustered-instance comparisons in our experiments test this directly. On uniform Euclidean instances we expect geometric splits to remain competitive, and we will say so if they are.
Why not just fix edges using LKH's candidate-edge sensitivity (alpha-nearness) and skip region certificates? This is the most serious threat, because 1-tree reduced costs already encode edge-level sensitivity. Edge fixing, however, never certifies that a whole region is entered once, which is the property that makes independent solving exact. We will run LKH with its default candidate sets as the naive baseline. We will additionally report how many certified regions are not implied by edge fixing alone. If that number is near zero, our certificate adds nothing, and we would drop the construction for the travelling-salesperson problem and retain only the CVRP capacity variant.
Why not just train an end-to-end neural solver that generalizes across distributions? Towards Omni-generalizable Neural Methods for Vehicle Routing Problems reports a 3.74% gap on 300-node rotation instances, against 4.43% for POMO. Both numbers are far from the sub-percent gaps of decomposition plus HGS, and that paper provides no certificate. We include its released code (Omni-VRP) only as a reference point on its own benchmark sizes.
Proposed Experiments
The first decisive check is soundness and recall on 10,000 optimal CVRP solutions. Because optimal solutions are known, we can verify that no certified region is ever crossed beyond the forced minimum, and any violation would indicate an implementation bug. We can also measure what fraction of truly separated regions the certificate detects. These results will be broken down across the 378 groups by clustered, mixed and random customer layouts and by route size. We predict that clustered layouts certify far more often, which would be the first measurement of local resilience in routing instances.
The second check is the distribution of measured $\alpha$ on TSPLIB and the Uchoa X instances, compared with the thresholds of 2 and 6.1 that the clustering theory requires. This tells us whether real instances are locally resilient even where they are globally not.
The third check is the head-to-head at equal time against IIL+HGS on the Uchoa, Arnold and DIMACS sets and against Select and Optimize on TSPLIB and 20,000-city instances, together with the frontier-targeting ablation. We will report gap against best-known solutions, the fraction of each instance certified, and certification time as a share of the total.
The proposal fails if certification consumes most of the budget, or if the certified fraction on real instances is small. Either outcome would itself be informative, because it would show that the stability assumed by the clustering theory is largely absent from routing practice.
References
- Metric Perturbation Resilience
- Certified Algorithms: Worst-Case Analysis and Beyond
- Clustering under Perturbation Resilience
- Massively Parallel k-Means Clustering for Perturbation Resilient Instances
- Graph Cuts Always Find a Global Optimum for Potts Models (With a Catch)
- Select and Optimize: Learning to solve large-scale TSP instances
- Imitation Improvement Learning for Large-Scale Capacitated Vehicle Routing Problems
- Theoretical Challenges in Learning for Branch-and-Cut
- Towards Omni-generalizable Neural Methods for Vehicle Routing Problems
- 10,000 optimal CVRP solutions for testing machine learning based heuristics