PaperlayerView exact revision on arXiv

Source-linked AI summary

Predictive Dual Smoothing for Column Generation

Senne Berden, Noah Schutte, Andrea Lodi, Tias Guns

arXiv:2609.34740v1cs.LGcs.AI

TL;DR

Dual oscillations can slow column generation, and past-dual smoothing may not guide pricing toward useful later columns. This paper predicts future duals from CG states and uses them as smoothing references; experiments report fewer generated columns and lower runtime across two problem classes.

  • Problem

    Dual oscillations can slow column-generation convergence, while references based on past duals may continue directing pricing toward needs already addressed.

    Source: §1 · pp. 1–2

  • Method

    Predictive dual smoothing combines current pricing duals with learned predictions of future duals, with the predictor trained from standard CG trajectories.

    Source: §1 · p. 2, §4 · p. 5

  • Results

    Experiments on cutting stock and generalized assignment report substantial reductions in generated columns and runtime versus standard CG and existing classical and learned stabilization methods.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Reduced-cost checks and fallback pricing preserve CG correctness, while predictive smoothing also provides gains when combined with strong classical stabilization.

    Source: §6 · p. 9

    Under the authors' setting with less training data and larger instances, the Kraul et al. (2023) result is weaker than in their original study.

    Source: §5.1 · p. 7

Abstract

from arXiv · show

Solving large-scale linear programs efficiently is an important challenge in many optimization settings. A key technique is column generation, which alternates between solving the master problem over a restricted subset of the variables, and using a pricing subproblem to identify new variables to add. The pricing subproblem is guided by the dual solution of the current restricted master problem, but oscillations in these dual solutions can substantially slow convergence. Dual stabilization methods address this issue. Dual smoothing is a common stabilization method, which guides the pricing subproblem using a combination of the current dual solution and duals from previous iterations. However, while past dual solutions can stabilize the dual trajectory, they do not necessarily guide pricing towards useful new variables. We therefore introduce predictive dual smoothing, which instead combines the current dual solution with a learned prediction of future duals to steer pricing towards variables that are more useful in subsequent iterations. The predictor is trained offline using supervision extracted from standard column generation trajectories and is used only to modify the pricing subproblem's objective function, while exact reduced-cost checks and fallback pricing with the unsmoothed duals preserve correctness. Experiments on cutting stock and generalized assignment problems show that predictive dual smoothing substantially reduces generated columns and wall-clock time relative to standard column generation and existing classical and learned stabilization methods. These gains extend to out-of-distribution instance sizes, and predictive smoothing provides further improvements when combined with strong classical stabilization.

1 INTRODUCTION

Column generation relies on dual-guided pricing, but dual oscillations can slow convergence and past-dual smoothing may continue targeting needs already addressed. Predictive dual smoothing instead uses predicted future duals as pricing references, trained from ordinary trajectories, with exact checks and fallback pricing preserving correctness.

1 INTRODUCTION

  • Dual oscillations can prompt pricing to generate columns attractive only under temporary prices, enlarging the restricted master and slowing convergence.Past-dual smoothing can reduce sensitivity to oscillations, yet its reference may keep directing pricing toward needs already addressed by added columns.Source: §1 · pp. 1–2
  • Predictive dual smoothing combines current duals with predicted future duals to guide pricing toward columns useful as the restricted master evolves.The prediction horizon sets how far ahead the reference looks, and smoothing strength controls its influence.Source: §1 · p. 2
  • The predictor is trained offline from standard column-generation trajectories, which supply supervised pairs between visited states and later duals.A recorded trajectory can be reused across prediction horizons by changing the target iteration.Source: §1 · p. 2
  • Experiments on cutting stock and generalized assignment show substantial reductions in generated columns and runtime versus standard CG and existing stabilization methods.The introduction also reports out-of-distribution evaluation and additional gains when predictive smoothing is combined with strong classical stabilization.Source: §1 · p. 2

2 RELATED WORK

Prior learning-based column-generation work selects columns, changes or restricts pricing, or predicts dual information. Predictive dual smoothing differs in its finite-horizon target, direct use as a pricing reference, and generic state features.

2 RELATED WORK

  • Learning-based column-selection methods use imitation or reinforcement learning to choose generated columns, including one-step-expert supervision and long-term choice objectives.Examples include Morabit et al. (2021) and Chi et al. (2022); later work considers selecting multiple columns (Yuan et al., 2024; Hu et al., 2025).Source: §2 · p. 3
  • Other learning approaches intervene in pricing, remove redundant columns, or predict columns' likelihood of appearing in an optimal integer solution.The passage gives examples including Shen et al. (2022), Morabit et al. (2023), Koutecká et al. (2025), Fang et al. (2023), and Sun et al. (2022).Source: §2 · p. 3
  • Dual-learning methods select among current RMP-optimal duals or predict eventual optimal duals, whereas predictive smoothing forecasts finite-horizon trajectory duals and uses them directly as pricing references.Its predictor uses generic CG-state features rather than problem-specific representations.Source: §2 · p. 3

3 PRELIMINARIES: COLUMN GENERATION

Column generation solves a large linear program through a restricted master problem and dual-guided pricing. In the cutting-stock example, patterns are master variables, while smoothing changes the pricing dual signal rather than the master.

3 PRELIMINARIES: COLUMN GENERATION

  • Column generation maintains a restricted master over a subset of columns and uses its dual solution to identify improving columns through pricing.For cutting stock, each feasible pattern is a vector of item counts that fits within the stock-roll length, and its master variable counts rolls cut according to that pattern.Source: §3 · pp. 3–4
  • Pricing uses the RMP dual values, associated with demand constraints, to find a pattern that can improve the current solution.A negative reduced-cost pattern can improve the objective; if exact pricing finds none, the current RMP solution is optimal for the LP.Source: §3 · p. 4
  • Dual oscillations can make pricing target temporary needs and generate columns useful for only a few iterations, slowing convergence.Unlike master-side stabilization, dual smoothing leaves the RMP unchanged and modifies the dual vector used in pricing.Source: §3 · p. 4
  • Conventional smoothing references past duals, which may reflect needs already addressed, while predictive smoothing uses predicted future duals to guide pricing toward needs as the RMP evolves.The figure caption describes the learned predictor and smoothing step as replacing conventional dual smoothing.Source: §3 · p. 5, Figure 1 · p. 5

4 PREDICTIVE DUAL SMOOTHING

Predictive dual smoothing guides pricing with a blend of the current dual and a prediction of a future dual, aiming to favor columns that remain useful as the RMP evolves. It learns predictions from CG trajectories and uses reduced-cost checks and fallback pricing to preserve correctness.

4 PREDICTIVE DUAL SMOOTHING

  • The pricing vector blends the current dual with a predicted dual k RMP updates ahead, with α controlling prediction influence and k setting the horizon.At α = 0, standard pricing is recovered; at α = 1, pricing uses the predicted future dual.Source: §4 · p. 5

4.1 PRESERVING CORRECTNESS

  • Reduced-cost verification against current duals accepts improving columns, while fallback standard pricing adds any missed improving column or certifies termination.A fallback reduces subsequent smoothing strength, moving pricing toward the current dual as convergence approaches.Source: §4.1 · pp. 5–6

4.2 LEARNING FUTURE DUALS

  • The predictor is trained offline on recorded CG states and dual solutions; each constraint’s future dual is predicted from its state features, using the terminal dual for near-converged states.Changing the horizon changes the target iteration, and one trajectory collection can be reused across horizons.Source: §4.2 · p. 6
  • Features summarize global CG progress, the constraint, pricing structure, and existing columns, using generic CG quantities across problem classes.The predictor uses quantities already available in the current RMP and pricing formulation.Source: §4.2 · p. 6
  • A lightweight single-output MLP predicts one constraint’s future dual at a time, with independent evaluations that can be batched.The shared fixed-dimensional constraint-level model is permutation equivariant and applies to instances with differing numbers of RMP constraints.Source: §4.2 · p. 6

5 EXPERIMENTS

Experiments evaluate predictive dual smoothing on cutting stock and generalized assignment problems, including its baseline performance, sensitivity to tuning and training data, and generalization across instance sizes.

5.1 CUTTING STOCK PROBLEM

  • Predictive smoothing lowers CSP paired runtime ratio by 37% versus standard CG and generates 27% fewer columns than standard CG and 20% fewer than Kraul et al. (2023).It also achieves the lowest paired runtime ratio among the reported baselines.Source: Table 1 · p. 7, §5.1 · p. 7
  • On CSP validation, k = 50 gives the lowest paired runtime ratio; α0 = 0.01 already improves on standard pricing, and α0 = 1 performs best with smoothing-strength decay.A small prediction perturbation can break ties among equal-reduced-cost pricing solutions; stronger initial smoothing increases fallback pricing, but fewer CG iterations more than compensate.Source: §5.1 · pp. 7–8, Figure 2 · p. 8
  • CSP performance remains strong with five training instances, but one-instance training overfits; predictive smoothing benefits more from added data than Kraul et al. (2023).The comparison reports substantial validation-accuracy and runtime improvements as training data increases for predictive smoothing, while Kraul et al.'s downstream performance is largely unaffected.Source: Table 2 · p. 8, §5.1 · p. 8
  • For CSP instances larger than training sizes, paired runtime ratios are 0.646 at n = 2000 and 0.695 at n = 2500, outperforming all baselines; at n = 250, Neame smoothing is faster.The authors suggest k = 50 spans more of the shorter trajectories at n = 250, making prediction behave like a terminal predictor.Source: §5.1 · p. 8, Table 3 · p. 9

5.2 GENERALIZED ASSIGNMENT PROBLEM

  • On GAP, predictive smoothing reduces paired runtime ratio to 0.041 and generated columns from 3327 to 2598, improving on Du Merle stabilization and its combination with Neame smoothing.Du Merle alone yields a ratio of 0.078, while adding Neame smoothing yields 0.077.Source: Table 4 · p. 9, §5.2 · p. 9

6 CONCLUSIONS AND FUTURE WORK

Predictive dual smoothing reduces generated columns and runtime across cutting stock and generalized assignment, including when layered on strong master-side stabilization. The feature representation draws on the current CG state, constraints, pricing structure, and existing columns.

6 CONCLUSIONS AND FUTURE WORK

  • Across cutting stock and generalized assignment, predictive smoothing reduces generated columns and runtime, including on top of strong master-side stabilization.Future work includes branch-and-price, online adaptation of prediction horizon and smoothing strength, and broader transfer evaluations.Source: §6 · p. 9

A FEATURE REPRESENTATION

  • The feature representation uses current CG state, constraint, pricing-formulation, and existing-column information to characterize each master row.Global and constraint features include iteration, column count, RMP objective, mean reduced cost, dual value, right-hand side, and primal activity; pricing features summarize relevant coefficients.Source: A FEATURE REPRESENTATION · p. 12
  • Existing-column context includes row coefficients, the share of columns containing the row, row-specific reduced-cost statistics, and pricing-block summaries.Continuous features are standardized with training-set statistics, and the same transformations are used at validation and test time.Source: A FEATURE REPRESENTATION · p. 12

B.1 PREDICTOR ARCHITECTURE

The predictor maps features for each RMP constraint to future-dual predictions using a shared row-wise MLP. Separate models target several finite horizons and the terminal dual.

B.1 PREDICTOR ARCHITECTURE

  • A separate row-wise MLP predicts a scalar future dual for each horizon, applying the same network independently to every RMP constraint.Its parameter count is independent of instance size.Source: §B.1 · p. 12
  • Each CSP and GAP predictor has one 32-unit ReLU hidden layer and a linear output, with standardized inputs and predictions on the original dual scale.The trained horizon-specific models use k ∈ {1, 3, 5, 10, 50, 100, 200, terminal}.Source: §B.1 · p. 12
  • Training targets are future duals from CG trajectories; GAP predicts job-partitioning duals while leaving machine convexity duals unchanged.CSP targets the dual at min(t+k,T), while the terminal model targets πT at every state.Source: §B.1 · p. 12
  • Using minimum-norm duals as canonical targets did not improve downstream CG performance, so training uses the LP solver’s returned duals.Minimum-norm targets would require a QP per state during data collection.Source: §B.1 · p. 12

B.2 TRAINING PROCEDURE

Training uses disjoint instance seeds, trajectory-derived examples, and validation-based model selection. Hyperparameters are chosen by mean paired runtime ratio, with GAP predictive smoothing also integrated with Du Merle stabilization.

B.2 TRAINING PROCEDURE

  • CSP training samples 50 stratified states and 256 item rows per instance, yielding about 1.28 million examples across 100 training instances.Validation uses 50 instances and about 640,000 examples; sampled states and rows are shared across prediction horizons.Source: §B.2 · p. 13
  • GAP retains job rows from mature Du Merle trajectory states and excludes startup states with artificial Big-M patterns from training, validation, and predictive smoothing at test time.Training, validation, and test instances use disjoint seeds, with 100, 50, and 50 instances respectively.Source: §B.2 · p. 13
  • Predictors minimize mean squared error with Adam at learning rate 10^-2, using batch sizes of 8192 for CSP and 4096 for GAP.Training is capped at 100 epochs, with early stopping based on validation MSE and restoration of the lowest-validation-MSE checkpoint.Source: §B.2 · p. 13

B.3 HYPERPARAMETER SELECTION

  • Hyperparameters are ranked by mean paired runtime ratio across validation instances, giving each instance equal weight rather than letting larger instances dominate.The ratio is each method’s runtime divided by standard CG runtime on the same instance.Source: §B.3 · p. 13
  • Validation selected k = 50, α0 = 1, γ = 0.9 for CSP predictive smoothing and k = 200, α0 = 1, γ = 0.9 for GAP with Du Merle stabilization.For CSP, validation also selected α = 0.75 for Neame and ϵ = 0.125 for Du Merle; for GAP it selected ϵ = 0.5 for Du Merle and α = 0.25 for Du Merle with Neame smoothing.Source: §B.3 · p. 13
  • During mature GAP states, predictive smoothing applies only to job duals and globally falls back to exact current-job-dual pricing when predictive pricing finds no improving pattern.Du Merle’s ϵ is halved only when neither predictive nor exact pricing finds a column, and termination requires a final exact-pricing run.Source: §B.3 · p. 13

B.4 IMPLEMENTATION DETAILS

The experiments used Gurobi 12.0.3 for RMPs and an exact Numba dynamic-programming implementation for pricing.

B.4 IMPLEMENTATION DETAILS

  • RMPs used Gurobi 12.0.3 with one solver thread, while pricing used exact Numba dynamic programming on an AMD EPYC 9334 system.Experiments ran on Ubuntu 24.04.4 LTS with 252 GiB of RAM.Source: §B.4 · p. 14

C GENERALIZED ASSIGNMENT PROBLEM

The generalized assignment problem assigns jobs to machines at minimum cost while respecting machine capacities. Its column-generation formulation uses a pattern-based master and machine-specific knapsack pricing.

D PREDICTIVE ACCURACY ON CSP

CSP validation predictor accuracy is reported across prediction horizons; longer horizons generally correspond to higher RMSE and lower R2.

E ABLATION OF SMOOTHING STRENGTH DECAY γ

In the CSP ablation, decaying smoothing strength after fallbacks improves runtime and reduces fallback pricing problems compared with non-decaying smoothing.

Loading 2609.34740v1…