Eighteen years of the same subproblem

In 2008 I published a paper on vehicle routing with Mads Jepsen, Bjørn Petersen and David Pisinger. It introduced subset-row inequalities, a family of cuts, and the branch-cut-and-price algorithm built on them closed eight Solomon benchmark instances that had been open until then.

Most of the citations are for the cuts. They also made the rest of the solver slower.

What the cuts cost

Solvers like this alternate between two problems. A master problem keeps track of the overall plan. A pricing subproblem keeps answering one narrow question: what’s the best single route I could add next? In vehicle routing that subproblem is a shortest path problem with resource constraints (capacity, time windows and so on), and it’s where most of the runtime goes.

Cuts are extra constraints on the master problem that tighten the lower bound the solver works from. A cut lives in the master problem, but it reaches into pricing: its price has to be accounted for when new routes are priced, and for subset-row cuts that means the subproblem gets one extra resource per active cut. Each partial route carries more state, and the pruning step (dominance: deciding that one partial route can never beat another) gets harder. More to compare, fewer routes thrown away, more left to extend.

So the bound gets better and the inner loop gets slower. It only pays off if the better bound saves more than the slower pricing costs.

In the 2008 paper we handled it in the dominance rule. A partial route that has picked up some cut state can still discard one that hasn’t, as long as it’s cheaper by enough to cover the cut penalty it might still have to pay. That was the contribution, as much as the cuts themselves.

Since then

Subset-row cuts are a special case of rank-1 cuts. Pecin, Pessoa, Poggi and Uchoa gave subset-row cuts a limited memory, and with Santos extended it to rank-1 cuts in general, both published in 2017. Limited-memory cuts are now part of the best exact routing solvers. They keep most of the cut’s strength and shrink the state it puts on the subproblem: a route forgets its progress on a cut once it leaves the cut’s memory. Our 2008 implementation was surpassed a long time ago, by methods built on it. That’s how it should go.

Pricing is still where most of the time goes, and a formulation whose pricing is too slow doesn’t get used. I’ve had my own pricing code for years, most recently the pull labelling Bjørn Petersen and I published, but it isn’t open source. VRPSolver, where the bucket-graph algorithm comes from, is closed too. Open bucket-graph code exists inside full routing solvers, but not as a library you can take out and build on. PathWyse (paper) is a good open library and it’s what I benchmark against below, but it uses standard labelling rather than the bucket graph, and it has no cuts built in. What I wanted was an open, fast one I could extend with a resource that has its own dominance rule, like the cut’s, without editing the solver.

bucket-graph-spprc

So I built bucket-graph-spprc. It implements the bucket-graph labelling algorithm of Sadykov, Uchoa and Pessoa. Bidirectional labelling, bucket fixing and arc elimination, with the labels stored side by side in memory so the dominance check can be vectorised.

The resource interface, seven functions per resource, is from Sadykov and co-authors’ Meta-Solver work. What the library adds is making it a compile-time C++ concept, so any set of resources, including your own, is combined into the label with no runtime dispatch. Five come built in: time and capacity, ng-path relaxation, cumulative cost, simultaneous pickup and delivery, and rank-1 cuts.

The rank-1 resource is limited to the original three-row subset-row cut from 2008, with limited memory on top and one bit of state per cut, up to 64 of them. Its dominance rule is the 2008 one, and it sits in the resource’s own functions like any other resource’s. For an ordinary resource like time or capacity, dominance is yes or no. The cut adds a finite penalty instead, so a cheaper route can fail to dominate, and a route carrying cut state can still dominate one without it, if it’s cheap enough.

Against PathWyse

PathWyse and bucket-graph-spprc tighten the bound differently by default, so I ran both in pure ng mode, with two small patches to PathWyse so they compute the same bound, up to rounding. No cuts are involved. The patches are committed with the benchmark.

At that bound, bucket-graph-spprc is 1.3–2.35× faster across the six combinations of instance set and neighbourhood size. That’s the shifted geometric mean of runtime (1 second shift), with timeouts counted at the 120 second limit rather than dropped. Of the 188 runs both solvers finish, it’s faster on 176.

That’s against PathWyse as of June 2025. Version 1.0 came out in July 2026 with a new bucket-based algorithm that its authors report is faster. I haven’t rerun against it.

PathWyse is single-threaded, so I also compared it with bucket-graph-spprc on one thread, using the scalar bidirectional build. It’s still 1.3–2.3× faster, so the gain isn’t just more cores.

The benchmark scripts, the PathWyse patches and the reference optima are in the repository, the instances are fetched from their public repos, and every table in the paper is regenerated by one command.

Where it loses

The benchmark runs without cuts. A same-bound comparison needs pure ng mode, so the rank-1 resource isn’t in those numbers. How the library does when pricing with active cuts still has to be measured.

The vectorised dominance check doesn’t pay on these instances. The scalar check walks a bucket sorted by cost and usually stops after a few comparisons, while the vectorised one compares a fixed-width batch before it can stop. On the larger instances the vectorised build is often slower, by up to about 40% on one group’s average. It’s the default anyway: the configurations that are fastest on some instance groups each fall over on another, and this one doesn’t. The paper’s conjecture is that the vector check pays off once cuts are active, since cut penalties break the early stop. That’s untested.

And it isn’t the fastest thing for this problem. The pull labelling Bjørn and I built is 1.9–2.4× faster on the 56 Solomon-based instances by shifted geometric mean. The gap narrows as the neighbourhoods grow, from 2.4× to 1.9×. I think pull does best on small, dense graphs, where each gather step has more to work with, but that isn’t measured in either paper. Closing the gap is on the list.

Why open source

The algorithms are published. What was missing was code anyone could pick up, add a resource to, and compare against the same baseline, and that’s what I want for myself too. Most of what I want to try next is a new resource, and a library where one plugs in through a fixed interface is a much better place to try it than a solver with its resources hardcoded.

The paper is arXiv:2606.30847.