acceptodds
Under review as a conference paper at ICLR 2027

Predictive Dual Smoothing for Column Generation

Abstract

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.

Primary area:
optimization
Keywords:
Column Generation, Dual Stabilization, Dual Smoothing, Linear Programming, Linear Optimization, Learning to Optimize

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_54HVOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes predictive dual smoothing for column generation. Instead of smoothing the current dual solution toward past duals, it predicts a future dual state with a lightweight per-constraint MLP trained offline from standard CG trajectories. The predicted dual is used only to guide pricing; columns are checked with the current dual, with exact pricing as a fallback, preserving correctness. Experiments on cutting stock and generalized assignment show fewer generated columns and lower runtime than standard CG and several stabilization baselines, including when combined with Du Merle stabilization.

Critical strengths
  1. The method is conceptually simple and integrates naturally into the CG loop.
  2. The empirical improvements are substantial and consistent across the two studied problems.
Critical weaknesses
  1. The claim that the feature representation is generic is not fully demonstrated, since the empirical scope is limited to two synthetic problem families, with only instance-size generalization studied for CSP.
  2. The paper does not sufficiently compare against a simpler learned tie-breaking baseline. The main gains may partly come from breaking ties among many equally optimal pricing solutions
Questions for authors
  1. Could you provide a runtime breakdown separating predictor inference, RMP solution time, pricing time, fallback pricing, and the number of CG iterations?
  2. How robust is the method to distribution shift beyond instance size, such as different demand or coefficient distributions?
2 comments

Thank you for your positive review of our paper. We found your suggestion regarding learned tie-breaking particularly interesting and have conducted additional experiments to investigate this. We address your comments and questions below.

Generic feature representation. We would like to clarify what we mean by a ‘generic’ feature representation. Our claim is not that the proposed features necessarily lead to good predictive performance on every problem class, but rather that they can be constructed independently of the problem class. We provide a generic way to construct features from quantities available in the CG procedure itself. This allows the feature representation to be applied to new problem classes without requiring problem-specific feature engineering. This is in contrast to most existing work, which relies on features derived from the structure of a particular optimization problem.

Whether our generic feature representation provides sufficient predictive information to perform well on a particular problem class is a separate, empirical question. We agree that experiments on additional problem classes would further strengthen the evidence for this, but distinguish this from the features being generic or not. We will clarify this distinction in the revised paper.

Learned tie-breaking baseline. Yes, this is something we looked into extensively when developing the method. As we mention in the paper (lines 408–412), even a very small smoothing weight (α0=0.01\alpha_0=0.01) leads to a substantial improvement on CSP: "a small perturbation towards the predicted future dual already acts as an informed tie-breaker among these columns." We therefore agree that part of the improvement can be explained by tie-breaking, at least for CSP.

Following your suggestion, we implemented a baseline that solves the pricing problem using the current RMP duals and, among the optimal pricing solutions, selects the column with the best objective value under our predicted future duals. We use the same kk-step predictors as in predictive smoothing. The results on our validation sets are as follows:

CSPColumnsRuntime (s)
Standard CG240529.82
Learned tie-breaking179128.23
Predictive smoothing173720.84
GAP (with Du Merle for learned methods)ColumnsRuntime (s)
Standard CG18779384.47
Du Merle stabilization333230.42
Du Merle + Learned tie-breaking334028.21
Du Merle + Predictive smoothing257214.11

On CSP, learned tie-breaking comes quite close to predictive smoothing in terms of the number of columns generated. On GAP, however, the difference is considerably larger. We also measured how often predictive smoothing generates columns that are not optimal solutions under the current RMP duals. This is the case for 49% and 63% of the accepted columns on CSP and GAP, respectively. Thus, while informed tie-breaking can be useful, there is also a benefit to moving away from optimal pricing solutions.

We would also argue that predictive smoothing is actually simpler to implement than learned tie-breaking. While learned tie-breaking requires optimizing a secondary objective over the set of optimal pricing solutions, predictive smoothing simply changes the objective coefficients of the pricing problem, allowing us to use the existing pricing solver without modification. This is an important practical advantage, and the additional computational work required for explicit tie-breaking is also reflected in the runtimes above.

We will include these experiments and the corresponding discussion in the revised paper.

Runtime breakdown. We did not log the individual runtime components in our original experiment, so we reran predictive smoothing on both the CSP and GAP test sets with additional timing code. The runtime breakdown is reported below.

MetricCSPGAP
Total runtime (s)24.54 (2.68)15.18 (0.24)
RMP solution time (s)14.00 (2.01)13.73 (0.22)
Feature construction (s)0.17 (0.01)0.49 (0.01)
Predictor inference (s)0.15 (0.01)0.02 (0.00)
Primary pricing time (s)9.58 (0.68)0.50 (0.01)
Fallback pricing time (s)0.19 (0.01)0.16 (0.00)
Master-update time (s)0.44 (0.03)0.28 (0.00)
CG iterations1756.6 (102.2)291.5 (3.9)

Other forms of distribution shift.

We expect the effectiveness of predictive smoothing under other forms of distribution shift to depend on the nature and magnitude of the shift, as is generally the case for supervised learning methods. An important property of our approach, however, is that poor predictions do not compromise the correctness of CG. The fallback mechanism ensures that the procedure will converge even when the predictor is applied to instances that differ significantly from those seen during training. Whether the predictor still accelerates CG on such instances is a separate question. Beyond instance-size generalization, we have not systematically investigated this and will acknowledge it as a limitation in the revised paper.

Reviewer_bzaCOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces predictive dual smoothing for column generation. A shared row-wise MLP predicts finite-horizon dual values from the current restricted master problem state, using supervision extracted from recorded column-generation trajectories. The predictions are combined with current dual values to modify the pricing objective. Generated columns are checked using current duals, and unsuccessful predictive pricing triggers exact fallback pricing and a reduction in the prediction weight. Experiments on cutting stock and generalized assignment evaluate runtime, generated columns, prediction horizons, smoothing strength, training-data requirements, and generalization across cutting-stock instance sizes. The method is also evaluated in combination with Du Merle stabilization.

Critical strengths
  1. Using finite-horizon future duals as smoothing reference points is a useful methodological contribution. It extends historical dual smoothing without requiring direct learning of a column-selection policy. Supervision can be extracted from ordinary column-generation trajectories, and the same trajectories can support different prediction horizons. This provides a relatively simple way to incorporate predictive information into pricing.

  2. The learned component is lightweight and acts only on the pricing objective. The shared row-wise predictor has a parameter count independent of the number of master constraints, while the pricing feasible set remains unchanged. Current-dual reduced-cost checks and exact fallback pricing provide a clear separation between learned search guidance and optimality certification in the ordinary, unstabilized column-generation setting.

Critical weaknesses
  1. The runtime statistics in Table 1 are internally inconsistent under the stated evaluation protocol. Let bib_i be the Standard CG runtime, tit_i the method runtime, and ri=ti/bir_i=t_i/b_i. For the same N=50N=50 instances, with conventional across-instance standard errors, these quantities must satisfy ∣tˉ−rˉbˉ∣≤(N−1)SE(r)SE(b)|\bar t-\bar r\bar b|\leq(N-1)\mathrm{SE}(r)\mathrm{SE}(b). For predictive smoothing, the reported means give ∣24.84−0.630×33.49∣=3.7413|24.84-0.630\times33.49|=3.7413, while the reported standard errors give an upper bound of 49×0.016×3.11=2.438249\times0.016\times3.11=2.4382. Neame smoothing also violates this bound: ∣30.22−0.865×33.49∣=1.2512|30.22-0.865\times33.49|=1.2512, compared with an upper bound of 49×0.005×3.11=0.762049\times0.005\times3.11=0.7620. These discrepancies cannot be explained by rounding.

  2. The correctness argument does not fully specify the stopping conditions for the stabilized GAP implementation. Section 4 allows πt\pi_t to be the dual solution of a stabilized RMP, whereas the usual termination argument requires a dual certificate consistent with the original, unmodified master problem. Exact pricing at a stabilized dual can establish that no column violates that dual vector, but this alone does not establish equality between the original primal and dual objectives. Appendix B.3 states that the Du Merle parameter is halved and that termination requires final exact pricing, but does not explain when stabilization becomes inactive or how its remaining effect is accounted for. The paper needs to specify which dual is used for final pricing and how original-problem feasibility and optimality are verified. This matters both to the correctness claim and to whether runtime comparisons use a common, valid stopping criterion.

Questions for authors
  1. Can the authors provide the per-instance Standard CG runtimes, method runtimes, paired ratios, and the aggregation code underlying Table 1? Were the paired ratios and absolute runtimes computed from the same measurements with identical timing boundaries? Please also specify exactly how the standard errors were calculated and reconcile the numerical inconsistencies above. Does correcting the statistics change the reported 37% mean paired runtime reduction or the ranking of methods?

  2. Can the authors provide the complete termination procedure for Du Merle stabilization combined with predictive smoothing? In particular, does final exact pricing use the optimal dual of an unstabilized RMP, or a dual from the stabilized problem? How are stabilization penalties or auxiliary variables handled before termination, and what original-primal feasibility, dual feasibility, and optimality-gap checks are performed? Please report the final checks for the GAP methods being compared.

2 comments

Thank you for your review of our paper. We have looked into both issues in detail and hope that the clarifications and additional results below address your concerns.

Runtime statistics Table 1. We looked into this and found two details of our evaluation protocol that were not correctly described in the submitted paper. First, we wrote that the number of test instances was N=50N=50, while the results in Table 1 were actually computed over N=150N=150 test instances. N=50N=50 only applies to the GAP results of Table 4.

Second, we organized the evaluation scripts to produce one complete result row per method. For each instance, a method-specific script ran both the method and a standard CG control, allowing it to compute the paired runtime ratio. The standalone standard CG row was generated by a separate evaluation of standard CG. So, the method runtimes used in the ratios are the same measurements reported in the corresponding method rows, but the denominators in the paired runtime ratios come from method-specific standard CG controls rather than from the standalone standard CG row.

In retrospect, using the standard CG runtimes from the standalone row as a common denominator is cleaner. The table below reports the results after recomputing the ratios this way. All results now satisfy the inequality stated in your review. The differences are minor: the ratio for predictive smoothing changes from 0.630 to 0.633, and the largest change across methods is 0.012. The ranking of the methods remains unchanged, and the reported mean runtime reduction of 37% still holds after rounding. We will use this common-baseline presentation in the revised paper.

MethodPaired runtime ratio ↓Columns added ↓Runtime (s) ↓
Standard CG1.000 (0.000)2394 (97)33.49 (3.11)
Du Merle stabilization1.268 (0.019)2500 (93)43.21 (4.30)
Neame smoothing0.877 (0.004)2119 (92)30.22 (2.88)
Kraul et al.0.987 (0.036)2207 (93)29.24 (2.70)
Predictive smoothing (Ours)0.633 (0.017)1756 (102)24.84 (2.70)

For transparency and completeness, we have attached the requested aggregation code and per-instance results of Table 1, including standard CG runtimes, method runtimes, paired ratios and generated-column counts, to the supplementary materials. All runtimes measure a complete CG run using the same timing boundary, and standard errors are computed as the standard deviation divided by 150\sqrt{150}.

Termination condition for GAP. In Section 4.1, we described how predictive dual smoothing preserves the correctness of standard column generation. We agree that this explanation does not fully cover its combination with Du Merle stabilization, as exact pricing at a stabilized dual is not sufficient to certify optimality of the original master problem. We account for this in our implementation, however. The overall procedure is the following:

  1. Solve the stabilized RMP and obtain its dual solution.
  2. Construct the smoothed pricing vector and solve all machine pricing problems.
  3. Evaluate every returned column using the current stabilized RMP dual. If any columns have negative reduced cost, add them and return to step 1.
  4. Otherwise, solve all machine pricing problems using the current stabilized dual without smoothing. If any columns have negative reduced cost, add them and return to step 1.
  5. If exact pricing also fails to find an improving column, halve the stabilization parameter and return to step 1. Once the parameter falls below a fixed threshold (10−810^{-8} in our experiments), deactivate stabilization by fixing its auxiliary variables to zero and reoptimize the ordinary RMP.
  6. Solve all machine pricing problems exactly using the unstabilized RMP dual, without smoothing. If any columns have negative reduced cost, add them, reoptimize the ordinary RMP, and repeat this step. Otherwise, terminate, provided no artificial columns remain active.

At termination, the primal solution is feasible for the original master problem, and the absence of negative reduced cost columns certifies dual feasibility for the full master problem. Since the two solutions are optimal for the unstabilized RMP, their objective values are the same. This certifies optimality for the full master problem. All GAP methods in Table 4 use the same optimality criterion, and the reported runtimes include the final unstabilized CG phase.

We also explicitly checked the final solutions for all instances and all four methods in Table 4. We specifically checked the original job equalities, machine capacities, variable nonnegativity, artificial-column values, reduced costs from pricing for every machine under the unstabilized RMP duals, and the relative primal-dual gap. Every check passed. No artificial columns remained, and all feasibility violations and gaps were zero within numerical precision (tolerance of 10−710^{-7}).

We will clarify this in the revised paper.

Thank you for the detailed responses. My main concerns have been addressed, and I have increased my rating to 3.

Reviewer_jvLcOpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a predicted dual smoothing technique for column generation where at each iteration, the pricing problem defined from a dual produced by the current restricted master problem is modified in a way to consider more future column selection, rather than the standard pricing that considers only the current RMS. The stabilization problem is an important issue to address in CG, and using machine learning to address this is a promising direction and have only been explored by very few works in literature. Dual smoothing was already introduced in literature, but this work aims to further improve it by incorporating look-ahead information (offline trained ML model) into the revised dual, which is then used for defining the pricing problem, in a hope that such a lookahead step can improve the chance of CG in identifying the improving column more directly. In the event if such revised pricing has failed, the method would revert back to the stand CG pricing solving. The paper definitely provides a very interesting perspective, with a very sound and insightful approach, especially the way we can incorporate machine learning to tackle the longstanding stabilization problem in the CG literature.

Critical strengths

The paper is strongly motivated by a longstanding problem faced in the CG literature, ie., the stabilization problem. Although a few smoothing and even machine learning approaches to tackle such a problem exist in literature, there are much room for further improvement. This paper (which is excellently written) provides great insights on the root cause of the problem and develop a predicted smoothing method to address this issue. The story is very compelling, and arguments were well made.

The paper is well written and organized. The writing clarity is extremely high. The authors are very skillful in presentation and logic development. The storyline is very clear and compelling!

Critical weaknesses

Since the proposed method relies on collecting labelled data from previously solved pricing problems in CG iteration, such data collection can be critical. The disadvantage of supervised learning we need to get lots of labelled data. It may pose challenges for problems that are difficult to collect ground truth data. Hence label efficient methods may be more appealing. Having said that, I would not consider this as a critical issue for the problems used in this study.

One may think that adopting the optimal dual solution in the final CG iteration may provide a more direct guidance, since the final dual is what counts most perhaps? Or perhaps this could be detrimental? Your sensitivity study on K in Table 2 shows that the medium-sized K values is most effective. And authors' analysis is that "very long horizons may become too detached from the needs of the current RMP". Would it be possible to elaborate this a bit more, and provide experimental results showing such performance degradation as K becomes too large increasingly? More importantly, comparisons with other existing machine learning based dual prediction methods, in addition to Kraul et al. (2023), will further strengthen this paper. I noticed that on GAP in Section 5.2, you did not include any machine learning methods for comparison (Table 4). What is rationale here?

Questions for authors

Q1: how often the predicted smoothing dual step fails in identifying a valid column to add to RMP?

Q2: Since the predicted dual smoothing adopts K-step lookahead strategy with a horizon, but not the eventual optimal dual solution (Shen et al., 2024), why do you think such a tactic is more effective? Sensitivity study on the parameter K in Figure 2 is great, but more empirical evidence and analysis could shed more lights on what is going on here. Can you explain what those numbers in the right panel of Fig. 2 means? large fallback pricing problem calls??

Q3: Could you include baseline comparisons of more machine learning approaches for dual prediction, NOT just classic dual smoothing methods? This will further strengthen your conclusions.

3 comments

Thank you for your positive review and for your thoughtful questions and suggestions. We are glad that you appreciate the paper. Your suggestions have led us to conduct several additional experiments. We address your individual comments and questions below.

Training data efficiency. We agree that collecting training data can be expensive for some CG problems. One advantage of our approach is that supervision is obtained directly from ordinary CG trajectories. Moreover, each trajectory provides many training examples and can be reused across prediction horizons. As shown in Table 2, even when training on only five CSP instances, predictive smoothing achieves a paired runtime ratio of 0.744, corresponding to a reduction of approximately 26%.

Frequency of invalid generated column / fallback pricing problems. The right panel of Figure 2 reports the average number of iterations in which the generated column is not improving (i.e., does not have negative reduced cost). In this case, a fallback pricing problem using the true duals is solved, which we discuss in Section 4.1. For our selected configuration (k=50k=50, α0=1\alpha_0=1, γ=0.9\gamma=0.9), pricing failed to identify a column with negative reduced cost approximately 35 times per instance (which is about 2% of pricing calls). As shown in Figure 3 (in Appendix E), these failures occur predominantly in the later stages of CG, as the RMP approaches convergence. Each failure reduces the smoothing strength by a factor of γ=0.9\gamma=0.9, and thus shifts pricing more towards the current RMP duals. This prevents excessive fallback calls, as also evidenced by the ablation in Figure 4. This figure shows that, without decay (i.e., γ=1\gamma=1), the same configuration requires approximately 960 fallback pricing calls per instance, compared to only 35 with decay.

For GAP, fallback is triggered only when the pricing problems of all 20 machine subproblems fail to produce an improving column. In our experiment, this occurred in approximately 101 iterations (about 35% of RMP iterations). Although this rate is much higher than that of the CSP, it remains highly beneficial to apply predictive dual smoothing, because this generates 22% fewer columns than plain Du Merle stabilization, which keeps the RMPs smaller and easier to solve, and reduces mean wall-clock time from 30.4 to 15.9 seconds as a result.

K-step lookahead strategy. In any iteration, the duals express the shadow prices of that iteration’s RMP, and thus reflect how costly the constraints are to satisfy using the columns available in the RMP in that iteration. For this reason, we hypothesized that predicting duals too far in the future would become too detached from the ‘needs’ of the current RMP, and that therefore an intermediate value for kk works better. Additionally, we show that accurately predicting duals further in the future becomes more difficult (Table 5, Appendix D), which also partly explains why an intermediate kk works well.

To further test these hypotheses, and to separate the usefulness of a terminal reference from the difficulty of predicting it, we have performed an additional experiment on the CSP validation instances, where we smooth using the true terminal duals. We first solved each instance with standard CG, stored its exact terminal dual, and then used this dual as a fixed smoothing reference in an independent run with the same fallback and adaptive-decay mechanism.

The results are:

ReferenceValidation R2R^2Paired runtime ratioRuntime (s)ColumnsFallbacks
Predicted k=10k=100.9060.6726.06191334.4
Predicted k=50k=500.8730.5822.78173735.0
Predicted k=100k=1000.8550.6223.81181337.0
Predicted k=200k=2000.8380.6325.49181141.1
Predicted terminal0.8020.6724.31188638.7
Oracle terminalN/A0.7017.4716416.4

The oracle terminal reference is highly effective. It generates fewer columns, requires fewer fallbacks, and has the lowest absolute runtime. This does provide some evidence against our first hypothesis, and suggests that the advantage of intermediate horizons is primarily that they are easier to predict accurately than the terminal dual. We will add this oracle comparison and refine our discussion in the paper.

Other ML baselines. Most existing approaches to learning dual values for CG have been developed for specific problem classes. For example, Kraul et al. (2023) construct features specific to CSP, and Shen et al. (2024) use features specific to graph coloring. To the best of our knowledge, no learning-based dual prediction method has previously been evaluated on GAP. A comparison on GAP would thus require adapting existing methods rather than directly reproducing them. In fact, this was one of our motivations for developing a generic feature representation based on quantities available in the CG procedure, rather than on the structure of a particular problem. For GAP, we therefore focused on comparing against strong classical stabilization methods, and in particular on whether predictive smoothing can provide further improvements on top of Du Merle stabilization.

Nevertheless, following your suggestion, we revisited the literature and identified a relevant recent preprint, Learning to Control Stabilization in Column Generation (Wang and Khir, 2026), which introduces two strategies for using predicted terminal duals as smoothing reference points: Static Predicted Reference (SPR) and Adaptive Predicted Reference (APR). SPR uses the predicted terminal duals as the reference point only in the first iteration, whereas APR retains them until the RMP objective stagnates. Both methods then revert to conventional smoothing using historical dual information. We adapted both reference-point strategies to our smoothing framework and evaluated them on CSP and GAP, using our generic feature representation to predict the terminal duals. We tuned their smoothing parameters using the same validation protocol as the other methods. The results are reported below.

CSP

MethodPaired runtime ratio ↓Columns added ↓Runtime (s) ↓
Standard CG1.000 (0.000)2394 (97)33.49 (3.11)
Du Merle stabilization1.268 (0.019)2500 (93)43.21 (4.30)
Neame smoothing0.877 (0.004)2119 (92)30.22 (2.88)
Kraul et al. (2023)0.987 (0.036)2207 (93)29.24 (2.70)
SPR0.832 (0.010)2024 (92)30.01 (2.97)
APR0.805 (0.009)2011 (92)29.06 (2.87)
Predictive smoothing (ours)0.633 (0.017)1756 (102)24.84 (2.70)

GAP

MethodPaired runtime ratio ↓Columns added ↓Runtime (s) ↓
Standard CG1.000 (0.000)18991 (104)388.93 (5.55)
Du Merle stabilization0.078 (0.001)3327 (12)30.42 (0.43)
Du Merle + Neame smoothing0.077 (0.001)3063 (10)29.74 (0.44)
Du Merle + SPR0.072 (0.001)3017 (10)27.84 (0.26)
Du Merle + APR0.083 (0.001)2853 (17)32.23 (0.31)
Du Merle + Predictive smoothing (ours)0.041 (0.001)2598 (27)15.87 (0.27)

On CSP, both SPR and APR improve on Neame smoothing. On GAP, SPR also improves upon Neame smoothing, while APR generates fewer columns but increases runtime. Our predictive smoothing consistently outperforms both strategies across all three metrics on both problem classes. This provides further evidence for the benefit of updating the predicted reference point throughout CG, rather than relying on a single prediction of the terminal duals. We will add these results to the revised paper.

Thanks for the detailed explanation, especially on the benefits of intermediate horizons. I am happy with the reply.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.