PaperlayerView exact revision on arXiv

Source-linked AI summary

Imperfect Is Perfect: Learned Column Prefilling for Branch-Price-and-Cut

Haoran Liu, Yu Yang

arXiv:2610.21001v1cs.LG

TL;DR

Although initial columns can slow root column generation, exact pricing in a state-of-the-art branch-price-and-cut solver has remained CPU-based. The paper combines a lazy archive of learned candidate columns, a learned Wentges-smoothing center, and GPU exact pricing; the full pipeline is 7.6 times faster than vanilla RouteOpt on average.

  • Problem

    Exact pricing in a state-of-the-art branch-price-and-cut solver has remained on the CPU, and gains over a modest research baseline may shrink or reverse inside an efficient solver.

    Source: §1 · p. 2

  • Method

    A learned edge scorer and constructive generator supply a lazy archive, a network predicts the initial Wentges-smoothing center, and a GPU backend accelerates exact bucket-graph labeling with CPU certification.

    Source: §1 · p. 2

  • Results

    The full pipeline is 7.6 times faster than vanilla RouteOpt on average and 17.5 times faster in the best case; prefill alone reaches 26.1% of vanilla root pricing time.

    Source: §4.2 · p. 7, §4.3 · p. 9

  • Takeaways & Limitations

    Imperfect routes need not belong to an optimal solution: held in a lazy archive and served at the current smoothed dual, they speed root pricing across two exact solvers.

    Source: §5 · pp. 9–10

    The effect on the full branch-price-and-cut tree is unknown because the tested instances have no known exact solution time.

    Source: §5 · p. 10

Abstract

from arXiv · show

Column generation folklore warns that initial columns hurt: a warm start may bias the dual and slow the root of branch-price-and-cut. We show the opposite once the columns are imperfect in the right way. Preloading the support of the optimal root LP, the best columns one could know in advance, fails to finish on half of our hardest instances; a pool of ordinary routes that need not belong to any optimal solution, held outside the master and priced at the current smoothed dual, speeds the root up. Because the columns need not be optimal, producing them becomes a learning task: a neural edge scorer guides a constructive generator that builds the pool in seconds. A second network predicts the initial center of Wentges smoothing from the instance file, and with it the direction of the smoothed pricing queries; the solver's own updates run unchanged. With prefill and center in place, exact pricing dominates root pricing time, so we rebuild bucket-graph labeling around its dominance test for the GPU and certify on the CPU. Inside RouteOpt, the state-of-the-art exact solver for capacitated vehicle routing, the pipeline reaches the same certified root bound in 13.2% of vanilla RouteOpt's root pricing time over 95 instances with 300 to 1000 customers, prefill alone in 26.1%, and 17.5 times faster in the best case. In an exact branch-price-and-cut solver for unrelated parallel machine scheduling, prefill with smoothing and the learned center certifies all 25 benchmark instances, 12 times faster than the solver's own column generation, which certifies 20 of them.

1 INTRODUCTION

The paper studies whether learned prefilling, dual stabilization, and GPU pricing can accelerate root pricing inside an efficient exact branch-price-and-cut solver. Its approach reverses the usual warm-start intuition by keeping imperfect routes in a lazy archive and learning the initial smoothing center.

1 INTRODUCTION

  • The method combines candidate-column prefilling, a learned initial center for Wentges smoothing, and GPU acceleration of exact pricing.The solver’s subsequent smoothing updates run unchanged.Source: §1 · p. 2
  • A lazy archive of diverse, ordinary routes speeds root pricing, while preloading heuristic routes or even optimal-root-LP support can slow it.The archive is queried at the current smoothed dual, and routes are admitted only through the usual pricing test.Source: §1 · p. 2
  • Learning the initial center targets the direction of pricing queries rather than proximity to one optimal dual, especially on hard instances.The solver’s own rule subsequently moves the center and adapts the smoothing weight.Source: §1 · p. 2
  • A GPU backend rebuilds exact bucket-graph labeling around its dominance test and retains CPU certification.The construction is applicable to bucket-graph-based pricers after adapting their resource extension, dominance rule, and join.Source: §1 · p. 2
  • The paper evaluates its approach inside RouteOpt, an exact CVRP solver, and an exact solver for unrelated parallel-machine scheduling.It emphasizes testing against efficient implementations because gains over modest research baselines can shrink or reverse in state-of-the-art solvers.Source: §1 · pp. 2–3

2 BACKGROUND

Branch-price-and-cut solves large-scale optimization problems through column generation, which generates variables as needed by solving pricing subproblems. This section outlines the route master, pricing levels, and dual smoothing used in the paper.

2 BACKGROUND

  • The route master uses customer-covering route variables, while its dual prices routes by reduced cost.A dual point is feasible exactly when the minimum route reduced cost is nonnegative.Source: §2 · p. 3
  • Column generation solves a Dantzig–Wolfe relaxation over a route subset, adding routes found by pricing; the paper calls any pre-run supply of candidate columns prefilling.When pricing certifies the dual point, the restricted master value is the root bound.Source: §2 · p. 3
  • Heuristic LIGHT and HEAVY pricing levels are cheap but may miss columns; only complete exact pricing can certify that no route prices out.The measured root-pricing time ends when exact pricing at the raw dual returns no route below the solver’s pricing tolerance.Source: §2 · p. 3
  • Wentges smoothing queries a convex combination of the RMP dual and a stabilization center, while candidate routes are re-priced at the raw dual before admission.The solver adapts the smoothing weight from an initial value of 0.5.Source: §2 · p. 3

3 METHOD

The method combines learned route prefilling and a predicted dual center with exact GPU pricing, while retaining the solver’s pricing tests and CPU certification.

3 METHOD

  • Two models read the instance file: an edge scorer guides route generation, and a set transformer predicts the initial dual-smoothing center.Pricing first queries the archive and heuristic levels, then uses GPU exact pricing and a final CPU-reproved certificate.Source: §3 · p. 3, Figure 1 · p. 4

3.1 LEARNING TO PREFILL

  • A broad set of distinct customer sets can constrain the restricted dual from many directions, so the paper learns to reproduce routes sampled by a seed-based population heuristic.Preloading optimal-root-LP support may reach the optimal primal value without ensuring the simplex-selected dual vertex certifies termination.Source: §3.1 · p. 4
  • The edge scorer predicts edge usage in reference-pool routes that price out at a reference dual, using instance-only graph features.Its message-passing graph is the same at training and generation; the constructive generator uses the heat map to build routes.Source: §3.1 · pp. 4–5
  • The route pool stays outside the initial master and offers eligible columns at the smoothed query before labeling; each route is offered once and admitted under the standard raw-dual test.This lazy archive cannot change the converged value, and the approach also applies to seed-based heuristics such as randomized list scheduling.Source: §3.1 · pp. 4–5

3.2 LEARNING THE DUAL CENTER

  • The learned center targets the direction and productive scale of pricing queries, rather than proximity to one optimal dual point.The solver certifies the installed center with an exact call, then subsequent centers are selected by certified Lagrangian bounds.Source: §3.2 · p. 5
  • A set transformer predicts singleton-normalized customer coordinates and a log magnitude; clipping and calibration set the installed customer-center norm.The vehicle dual is predicted separately, and the solver’s later center-selection and weight rules remain unchanged, with fallback retries for miscalibrated centers.Source: §3.2 · pp. 5–6

3.3 GPU EXACT PRICING

  • GPU exact pricing batches dominance comparisons and expands labels in waves, removing the sequential dependence of one-label-at-a-time bucket insertion.Label extension, dominance, and joining run on the GPU; reconstruction, deduplication, selection, and CPU certification remain outside it.Source: §3.3 · pp. 6–7
  • The GPU design targets bucket-graph pricers beyond RouteOpt when their resource extension, dominance rule, and join are adapted.The CPU profile identified the dominance test as the exact-pricing hotspot.Source: §3.3 · pp. 6–7

4 EXPERIMENTS

The evaluation tests the pipeline on 95 large CVRP instances and a separate parallel-machine scheduling benchmark, measuring root-pricing time while checking certified outcomes. It examines component effects, GPU exact pricing, and transfer to scheduling.

4.1 EXPERIMENTAL SETUP

  • The 95-instance CVRP panel samples 300–1000-customer instances across route-size classes, and reports wall-clock root-pricing time relative to vanilla RouteOpt.Every completed configuration reaches the same certified root bound; the scheduling benchmark uses Hijazi et al. (2026) instances and seeds.Source: §4.1 · p. 7

4.2 THE PIPELINE TAKEN APART

  • Prefill alone reduces root time to 26.1% of vanilla’s; the learned center mainly helps large, long-route instances, while together they shift more work toward exact pricing.Prefill+Center has a panel average ratio of 0.264 versus 0.261 for Prefill, but is faster on ultra-long routes; the archive supplies columns in 24–52% of LIGHT rounds.Source: §4.2 · pp. 7–8, Table 1 · p. 8

4.3 GPU EXACT PRICING

  • Once prefill and center shift root time toward exact pricing, GPU calls are faster: the median CPU-to-GPU call-time ratio is 4.70 on L4 and 8.90 on Blackwell.Exact pricing’s share rises from 15% to 61%; the GPU cards produce identical bounds and exact-call counts.Source: Figure 3 · p. 8, §4.3 · p. 8, Table 2 · p. 8

4.4 CASE STUDY: PARALLEL-MACHINE SCHEDULING

  • 12 times faster in geometric mean, prefill with smoothing and the learned center certifies all 25 scheduling instances, compared with 20 certified by the learned-pricer baseline.The scheduling comparison uses a shared vectorized exact pricing oracle across configurations.Source: Table 3 · p. 9, §4.4 · p. 9

4.3 GPU EXACT PRICING

  • The full pipeline is 7.6 times faster than vanilla RouteOpt on average and 17.5 times faster in the best case; the reported root-time ratio is 0.884.Source: §4.3 · p. 9

5 CONCLUSION

The paper presents imperfect-column prefilling as a plug-in accelerator for branch-price-and-cut and reports faster certified root pricing in RouteOpt. Its scope is root pricing; the effect on the full branch-price-and-cut tree remains unknown.

5 CONCLUSION

  • 7.6-fold geometric-mean speed-up in root pricing over vanilla RouteOpt, with the same certified root bound; the best case uses 5.7% of vanilla RouteOpt’s time.The reported comparison is on the state-of-the-art CVRP solver.Source: §5 · p. 10
  • Imperfect routes speed the root when kept outside the initial master as a lazy archive and offered at the current smoothed dual.The archive supplies candidate columns to root pricing rather than preloading them into the master.Source: §5 · pp. 9–10
  • The effect on the full BPC tree is unknown; at the tested scale, the instances have no known exact solution time, so the paper measures and certifies root pricing.Extending measurement to the tree is identified as future work.Source: §5 · p. 10

A.1 DANTZIG–WOLFE DECOMPOSITION AND THE MASTER PROBLEM

  • Dantzig–Wolfe decomposition represents block solutions as columns in a master, whose bound equals the Lagrangian dual bound and is no greater than the integer optimum.The equality between the LP and Dantzig–Wolfe bounds holds when the block polyhedra have integral vertices.Source: §A.1 · pp. 14–15

A.2 COLUMN GENERATION: THE PRIMAL–DUAL VIEW

  • Column generation adds negative-reduced-cost columns until exact pricing certifies none remain; Wentges smoothing changes query points, while raw-dual admission preserves the bound.A heuristic pricing call may miss a minimizing route, so termination requires an exact call.Source: §A.2 · pp. 15–16

A.3 TWO TYPICAL TASKS: ROUTING AND SCHEDULING

The paper applies its learning components to routing and unrelated-machine scheduling, where each column represents one resource’s plan. The exact pricing problems differ across the two tasks, while the learned components initialize column pools and stabilization centers.

A.3 TWO TYPICAL TASKS: ROUTING AND SCHEDULING

  • Routing prices ng-feasible routes with bucket-graph labeling, while scheduling prices machine-specific job subsets by dynamic programming over accumulated processing time.The scheduling formulation uses a machine-indexed master; the experiments combine the learned pricer setting with column initialization and dual stabilization.Source: §A.3 · p. 17, §A.5 · pp. 18–19

A.4 CASE 1: CAPACITATED VEHICLE ROUTING IN ROUTEOPT

  • In RouteOpt, an ng-route may revisit a customer only after passing through a customer whose neighborhood excludes it; exact dominance preserves the minimum reduced cost.The root measurement ends at the first exact certificate, before cuts, branching, or arc elimination.Source: §A.4 · pp. 17–18

A.5 CASE 2: UNRELATED PARALLEL MACHINE SCHEDULING

  • For unrelated machines, pricing uses a subset-selection dynamic program with a pseudo-polynomial O(n Σ_j p_kj) cost per machine for integer processing times.The learned center is predicted from instance data, projected onto the dual sign constraints, and installed at iteration 0; Wentges updates then run unchanged.Source: §A.5 · p. 19

B THE LEARNING COMPONENTS IN DETAIL

  • Both learned components read only the instance file, run once before column generation, and provide a route pool or an initial smoothing center.The pool is a lazy archive and the center initializes the solver’s existing stabilization rule.Source: B THE LEARNING COMPONENTS IN DETAIL · p. 19

B.1.1 TRAINING

The deployed edge scorer learns route-relevant edge heats from instance-derived graph features and reference-pool routes. At inference, its heat map guides a constructive generator whose routes are offered through a lazy archive.

B.1.1 TRAINING

  • The edge scorer uses three rounds of symmetric message passing over a graph built from the instance, with 26 instance-only edge features and a width-192 edge head.Its edge label is the fraction of reference-pool routes pricing out at the reference center that traverse the edge; training regresses on the square root of this heat.Source: §B.1.1 · pp. 19–20

B.1.2 INFERENCE: FROM THE HEAT MAP TO THE ARCHIVE

  • The generator builds distinct route columns from the heat map under a ten-second instance budget, and the lazy archive offers up to 300 routes at each pricing round.Archive routes are admitted using the raw-dual reduced-cost test; the learned generator’s wall time is 0.23 to 0.30 of the metaheuristic pool’s in a dedicated timing study.Source: §B.1.2 · p. 20

B.2.1 TRAINING

The center model predicts customer dual direction and magnitude from instance features, with a separate tree model for the vehicle row. After calibration and box projection, the resulting center is installed at the first pricing iteration and then updated by the solver.

B.2.1 TRAINING

  • The center uses a set transformer over customer and instance-context tokens, with separate heads for customer direction and log magnitude; a tree predicts the vehicle row.The customer tokens use attention with geometric distance bias; the deployed architecture is summarized in Table 7.Source: §B.2.1 · p. 21, Table 7 · p. 22
  • The 53 customer features combine depot distances, demand, neighborhood statistics, and instance context, while excluding root-LP values and generator-family digits.The vehicle-row model uses nine instance-context features.Source: §B.2.1 · p. 21
  • The direction target is each customer’s optimal dual divided by twice its singleton-serving cost; the center’s median relative L2 error is 0.2017 including the vehicle row, versus 0.1958 for the customer block alone.The authors emphasize that the intended value is a useful initial direction, not small prediction error.Source: §B.2.1 · p. 21

B.2.2 INFERENCE: FROM THE PREDICTION TO THE SMOOTHING CENTER

  • At inference, a calibrated, box-projected prediction becomes the first pricing center; later solver updates remain active, and the center adds no columns of its own.The center is certified by an exact pricing call, replacing the stabilized baseline’s seeding exact call.Source: §B.2.1 · p. 21, §B.2.2 · p. 22

B.3 LABELS AND DATA

The learned components use certified root-dual labels from a defined instance split, while the GPU backend reorganizes bucket-graph dominance work and retains CPU certification safeguards. The backend targets a sequential dependence in bucket labeling, and completed comparison arms are required to agree on the root bound.

B.3 LABELS AND DATA

  • The labels are certified optimal root duals from 320 XML instances, split 200/60/60 for training, validation, and testing; evaluation instances are held out, and XML400 and Vrp-Set-X instances are unlabeled.Label duals are accepted only after objective and reference-pool pricing checks.Source: §B.3 · pp. 22–23

C.1 BUCKET-GRAPH LABELING AND THE DOMINANCE TEST

  • RouteOpt’s bucket-graph pricer extends partial routes through resource-ordered buckets and checks arrivals against stored labels using resource, ng-set, and cut-state dominance conditions.The sequential dependence arises because each arrival is checked against and changes the bucket as it stands.Source: §C.1 · p. 23

C.2 WHERE THE TIME GOES

  • On the profiled cut-loaded roots, dominance accounts for close to half of self cycles, while exact calls evaluate orders of magnitude more dominance predicates than LIGHT or HEAVY calls.The profiling concerns vanilla RouteOpt; exact pricing becomes more consequential after prefill and the learned center reduce heuristic-pricing time.Source: §C.2 · p. 23, Table 8 · p. 23

C.3 REMOVING THE SEQUENTIAL DEPENDENCE

  • The GPU backend groups candidate labels by target bucket and wave, then applies staged dominance checks and a repair pass that preserves a surviving direct dominator for every deleted label.Label extension, dominance testing, and forward-forward joins run on the GPU; reconstruction, deduplication, and returned-column selection remain on the CPU.Source: §C.3 · pp. 23–24

C.4 CERTIFICATION AND SAFEGUARDS

  • The backend runs only on symmetric instances within the compiled ng bit-set bound, with CPU fallback otherwise; an empty GPU answer is re-proved by a CPU exact call.Every returned column is re-priced on the CPU, and completed comparison arms must report the same root bound.Source: §C.4 · p. 24

C.5 WHAT THE BACKEND BUYS PER CALL

The per-call comparison serves identical exact-pricing calls with RouteOpt’s CPU labeling and the GPU backend, with bounds and call counts agreeing across the reported instances.

C.5 WHAT THE BACKEND BUYS PER CALL

  • 10/10 instances agree in root bounds and exact-call counts across the three GPU cards and the CPU comparison.The comparison uses steady-state exact calls, excluding the first GPU-initialization call and final CPU re-proof.Source: §C.5 · p. 24, Table 10 · p. 25
  • Table 9 serves the same exact calls on one CPU thread and an L4 in the first cut-free column-generation runs of five Vrp-Set-X instances.Its final column estimates end-to-end gain by subtracting measured pricing time; it is not a separate vanilla run.Source: Table 9 · p. 24, §C.5 · p. 24
  • Table 10 reports per-instance median seconds per steady-state exact call on one CPU thread and three GPU cards for the 10 longest-exact-pricing Vrp-Set-X instances.The comparison excludes LP solves, which run on the CPU on every card.Source: §C.5 · p. 24, Table 10 · p. 25

D ABLATIONS AND ADDITIONAL RESULTS

The ablations compare two design choices—how to supply pool columns and how to initialize the smoothing center—on 10 deep X-set instances, with completed arms reaching vanilla’s certified root bound.

D ABLATIONS AND ADDITIONAL RESULTS

  • The ablations isolate pool-column supply and initial smoothing-center choice on 10 X-set instances from the long and very long route-size classes.Each arm runs within one job on one node and is bracketed by two vanilla solves.Source: D ABLATIONS AND ADDITIONAL RESULTS · p. 25
  • The vanilla denominator is the mean of four bracketed vanilla solves, and timeouts are reported as lower bounds under a limit of 1.5 times the first vanilla time plus 300 seconds.Every completed arm reaches the same certified root bound as vanilla.Source: D ABLATIONS AND ADDITIONAL RESULTS · p. 25
  • Tables 11 and 12 give instance-level root times and an instance-equal geometric mean of ratios to vanilla, with two-sided 90% t intervals on log ratios.Source: D ABLATIONS AND ADDITIONAL RESULTS · p. 25

D.1 SUPPLYING THE COLUMNS: WHICH POOL, AND HOW

A learned pool of imperfect routes outperforms both a heuristic pool and the oracle support of the optimal root LP; a learned smoothing center adds further speed. Very-short-route instances are an outlier: prefill helps, but the center and GPU add little.

D.1 SUPPLYING THE COLUMNS: WHICH POOL, AND HOW

  • 1.233× faster than the heuristic pool (PH/PN, 90% interval [1.121, 1.356]), the learned pool wins on 9 of 10 instances.On X-n1001-k43, the scorer proposed 326470 feasible routes against a few thousand from one heuristic run.Source: §D.1 · p. 25
  • On these instances, lazy archive and full-pool dump show no detected difference (PDUMP/PN 1.044×, interval [0.960, 1.135]); preloading costs 1.209× on deep XML instances.The archive starts from singleton columns and offers routes at the current smoothed dual; on X-n1001-k43, scanning the pool costs 18 ms and only 2.7% enters the model.Source: §D.1 · pp. 25–26
  • 5 of 10 optimal-support preloads time out; the five completed runs are 0.732× vanilla and 2.478× slower than deployed prefill (PSUPP/PN, [1.620, 3.790]).The complete converged column set is the best oracle arm at 0.183×, suggesting that a rich neighborhood of near-optimal routes—not just optimal support—is useful.Source: §D.1 · p. 25, Table 11 · p. 26

D.2 CHOOSING THE CENTER: THE LEARNED DIRECTION

  • 1.369× faster than standard smoothing (S/CN, interval [1.257, 1.492]); standard smoothing alone reaches only 0.837× of vanilla.The learned direction is predicted, assigned a magnitude, projected onto the structural box, and used as the iteration-0 Wentges center.Source: §D.2 · p. 26, Table 12 · p. 27
  • 1.176× slower when the learned center’s customer entries are permuted (CRAND/CN, [1.094, 1.264]); the calibrated center still beats standard smoothing, 0.719× versus 0.837× of vanilla.The comparison attributes part of the gain to installing a calibrated center at iteration 0 and the additional gain to its learned direction.Source: §D.2 · p. 26

D.3 VERY SHORT ROUTES

  • 0.126× vanilla root time across all 20 very-short instances (best 0.075×); the center costs 1.376× versus prefill alone, while GPU pricing is 1.003×.These instances are excluded from the main panel because prefill has more to offer and exact pricing is too small a share of runtime for the GPU to matter.Source: §D.3 · p. 27, Table 14 · p. 27

E REPRODUCIBILITY

The experiments use released solver code, instances, and seeds where specified, with fixed randomness and reported software versions.

E REPRODUCIBILITY

  • Routing experiments use RouteOpt’s released source and identical settings for vanilla and the fork; the scheduling case study uses released code, instances, and seeds.The LP solver is Gurobi 13.0.1 and the GPU backend uses CUDA 12.9.1; all randomness is seeded, with generator and training seeds listed in Appendix B.Source: E REPRODUCIBILITY · p. 27

Related papers

Loading 2610.21001v1…