Certified Bounds for Column Generation with Noisy Quantum Pricers

Many planning problems that trade upfront capital against running costs are solved exactly by column generation. A classic example is deciding when to charter an outside ship instead of running more voyages with your own fleet. Column generation is a method that keeps a small set of candidate plans (columns) and repeatedly asks a subproblem, called pricing, for a new plan that would lower the total cost. The method is only exact if, at the end, someone proves that no such improving plan exists. That last step is an unsatisfiability proof, and it is what noisy near-term quantum hardware cannot give. These are the NISQ devices: small, error-prone processors with tens of usable qubits. They are samplers. They can find good plans, but they cannot certify that none remain.

This note proposes to stop asking the sampler for that proof. A deliberately simplified pricing model, built to only ever underestimate the true cost of a plan, supplies a cheap certified lower bound on the best possible improvement. Standard column-generation duality turns that bound into a valid lower bound on the whole problem, and that bound can prune parts of the search on its own. The noisy sampler hunts for good columns, the simplified model supplies the proof, and an exact classical pricer runs only when the bound and the sampler disagree by too much. The central claim is that model simplification, normally a source of silent error, becomes a source of soundness when the direction of the simplification is controlled. A relaxation that drops constraints is safe for bounds, while candidates it produces are checked against the full model. Under this design, noisy quantum pricing no longer causes the premature, unsound termination that existing quantum decompositions suffer from.

Where the gap is

The closest work is Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness. It verifies small ReLU networks by Dantzig–Wolfe decomposition and sends the pricing problem to a D-Wave annealer as a quadratic unconstrained binary problem (QUBO). Each quantum call stays at roughly 13–17 qubits, up to 90% fewer than Benders decomposition. Its own stated limitation is the one this note targets. If the annealer misses an improving column, the classical master stops early and the robustness "proof" is no longer a proof. Our design keeps its constant-qubit pricing and adds a certified stopping and pruning rule.

The second neighbor is A Hybrid Quantum-Classical Approach to Solving Scheduling Problems. It uses annealer samples to guide branching inside a complete classical tree search. Average explored nodes fall, for example from 45.72 to 31.58 on airport runway scheduling. However, hardware call latency outweighs the savings. That paper keeps completeness by leaving all proof work to classical branching. We keep completeness through a bound inside each node, which can prune without branching at all.

The classical background constrains the design. Systematic Versus Stochastic Constraint Satisfaction explains why samplers cannot refute. Online Bayesian Moment Matching based SAT Solver Heuristics shows that statistical guidance gives negligible help on unsatisfiable instances. Together they rule out any design in which the sampler itself is expected to contribute to the proof.

The application regime comes from Industrial and Tramp Ship Routing Problems: Closing the Gap for Real-Scale Instances. That paper removed earlier simplifications such as static fuel burn and fixed cargo sizes, and solved the resulting capital-versus-operating trade-off with exact branch-and-price. It reports that mixed-load pricing, where pickups and deliveries need not alternate, remains the classical bottleneck. That is where an incomplete but fast pricer is most worth making safe.

Core claim

Each ship $k$ appears in the restricted master problem through a constraint saying it uses exactly one plan. Let $z_{\text{RMP}}$ be the current master objective. Let $\underline{c}_k \le 0$ be any certified lower bound on the most negative reduced cost (net cost improvement) of a feasible plan for ship $k$. Then

$$z_{\text{LB}} = z_{\text{RMP}} + \sum_k \underline{c}_k$$

is a valid lower bound on the optimum at that node. This is the standard Lagrangian bound of column generation; it holds because each ship contributes at most one column.

Nothing in this bound depends on the sampler. The proposal is to obtain $\underline{c}_k$ from a simplified pricing model in three steps. First, the plan is collapsed to a choice of which cargoes ship $k$ carries, one binary variable per cargo, which fits NISQ budgets. Second, route cost is replaced by a pairwise quantity that never exceeds the true cost. Third, time-window and load constraints are dropped rather than penalized. Solving this relaxation exactly is cheap in the restricted regime: a convex or semidefinite relaxation of a QUBO with a few dozen variables, or enumeration when the variable count is small. The sampler then proposes cargo subsets. A classical routine routes them against the full model, with time windows, draft limits and load-dependent fuel, and it either adds them as columns or discards them.

A node is closed when $z_{\text{LB}}$ meets the incumbent or $\sum_k \underline{c}_k \ge 0$. Exact classical pricing is called only when the certified bound is weak and the sampler has stopped finding columns. Gauged by the gap between that bound and the best sampled reduced cost, quantum shots become an operating expense to be budgeted. We borrow the adaptive-shot idea of An Adaptive Optimizer for Measurement-Frugal Variational Algorithms, which allocates measurements per parameter by expected gain. Here the analogous rule spends samples where the bound gap is largest.

Research program

The work has three parts. The first is the underestimating pricing relaxation for the ship routing problem with chartering. It comes with an explicit proof that it never overestimates route cost, and with an empirical audit on every column ever generated: zero violations are required. The second is the node-level controller that decides among sampling more, tightening the relaxation, and calling exact pricing. The third is a port of the same certification rule to the Dantzig–Wolfe verification setting of Franco et al. There, the pricing QUBO is already given and the question is purely whether certified stopping removes their unsoundness.

The sampler is pluggable. It can be a physical annealer if access allows, or a QAOA circuit (the quantum approximate optimization algorithm, a shallow variational circuit) under a simulated noise model sized to 15–40 qubits. It can also be classical simulated annealing on the identical QUBO. Model simplification thus appears twice: as the deliberate relaxation that makes proofs cheap, and as the measured quantity we ask about. How loose can the relaxation be before exact pricing dominates the runtime?

Baselines

The naive reference point is unsound early termination. Column generation stops as soon as the sampler returns no improving column, exactly as in the published quantum Dantzig–Wolfe scheme. We run it on the same instances and pricing QUBOs. Against the exact optimum computed offline, we record how often it returns a wrong bound or a wrong verification verdict. No reported result found on Lacuna for the rate of premature termination in Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness, so we measure it. Beating this baseline means zero unsound terminations, which the certified bound guarantees by construction. The question is the cost in time.

The strongest existing method is classical exact branch-and-price from Industrial and Tramp Ship Routing Problems: Closing the Gap for Real-Scale Instances. It uses decremental state-space relaxation for pricing, strong branching, route enumeration and subset-row cuts, and it optimally solves 239 of 240 Hemmati et al. instances within one hour, with the last taking just over four hours. We reimplement its pricing as our exact fallback, run both on identical hardware and time limits, and report results separately for mixed-load instances. No reported result found on Lacuna for a mixed-load-only breakdown of that paper's runtimes. Beating it means solving more mixed-load instances to proven optimality within the hour, or the same instances with fewer exact-pricing calls and lower wall-clock time including all sampler latency.

The key ablation swaps the quantum sampler for simulated annealing, and separately for no sampler at all. In the no-sampler variant, columns come only from exact pricing, while the certified bound is still used. This isolates the two ingredients. The certified relaxation's contribution is measured by the fraction of nodes closed without exact pricing. The sampler's contribution is measured by columns found per second at matched sample budgets. A second ablation fixes shot counts instead of allocating them by bound gap, testing whether the measurement-frugality idea transfers from continuous optimization to tree search.

Why not just…?

Why not just use the classical branch-and-price solver, which already solves 239 of 240 instances? Because that result concerns the benchmark mix as a whole, while its authors identify mixed-load pricing as the place exact pricing becomes prohibitive. There the question is whether a fast incomplete pricer can be used safely. If classical branch-and-price matches us on mixed-load instances at equal wall-clock time, the quantum part has no case, and we will report that. The certified-bound controller would still stand as a classical contribution, because it applies to any heuristic pricer.

Why not just replace the quantum annealer with simulated annealing on the same QUBO? This is the most serious threat, and we expect it to win at current latencies, given the overhead A Hybrid Quantum-Classical Approach to Solving Scheduling Problems observed. The proposal is built so this does not sink it. Soundness comes from the relaxation, not the sampler. The sampler ablation then states plainly, for each instance size, whether quantum samples find more improving columns per unit of wall-clock time and per unit of sample cost. Any quantum claim is conditional on that comparison.

Why not just run heuristic pricing and then exact pricing at every node, the usual practice? That is sound, but it pays for the full proof at every node, and on mixed-load instances that proof is the bottleneck. The decisive measurement is the share of nodes our bound closes without exact pricing, and the time saved net of computing the relaxation. If that share is near zero because the cargo-selection relaxation is too loose, the idea fails, and the experiment tells us so directly.

Why not just use a GPU complete verifier like MN-BAB for the verification testbed? Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Bound raises certified accuracy on ResNet8-A from 18% to 46% and is far stronger on large networks than any quantum decomposition. We use the MNIST MLP-2x[20] testbed only to show that certified stopping repairs the unsoundness of quantum Dantzig–Wolfe at its published 13–17-qubit size, not to compete with MN-BAB. MN-BAB is run as the reference for correct verdicts.

Proposed experiments

The primary benchmark is the Hemmati et al. ship routing set used by Homsi et al., where chartering versus own-fleet voyages is the capital–operating trade-off. We use the full-load and mixed-load subsets, plus the 32 larger instances from the same paper where runtime permits. Pricing subproblems are restricted to cargo sets that fit 15–40 binary variables, so quantum or simulated QUBOs are realistic. The metrics are proven-optimal count within one hour, final optimality gap, wall-clock time including sampler latency, exact-pricing calls per node, nodes closed by the certified bound alone, and the relaxation audit (any column whose true cost falls below its relaxed estimate is a bug).

The secondary benchmark is Franco et al.'s MNIST MLP-2x[20] and PGD-2x[20] robustness queries, with verdicts checked against MN-BAB. Here we measure unsound terminations under naive stopping versus zero under certified stopping, along with the added classical time.

Three checks are decisive. Certified stopping must eliminate wrong verdicts at modest time cost. On mixed-load instances, the fraction of nodes closed without exact pricing must be large enough to cut wall-clock time below the classical branch-and-price fallback. And the sampler ablation must show whether quantum samples beat simulated annealing per unit of cost. If only the first two hold, the result is a sound classical method for using incomplete pricers, with noisy quantum hardware as one admissible sampler and no claimed quantum advantage. If all three hold, it is the first exact quantum-priced decomposition whose correctness does not depend on the sampler.