Predictive Dual Smoothing for Column Generation

Senne Berden; Noah Schutte; Andrea Lodi; Tias Guns

cs.LGSep 28, 2026

Predictive Dual Smoothing for Column Generation

Authors: Senne Berden, Noah Schutte, Andrea Lodi, Tias Guns

Organizations: KU Leuven · TU Delft · Cornell Tech

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.

Figures & tables

Panel of Figure 1 — Figure 1: Predictive dual smoothing. The learned predictor and the smoothing step (blue) replace conventional dual smoothing. A column proposed under $\widetilde{\bm{\pi}}_{t}^{(k)}$ is accepted only if its reduced cost is negative under the true current dual $\bm{\pi}_{t}$ . When the test fails, standard pricing with $\bm{\pi}_{t}$ either supplies an improving column or certifies LP optimality.

Method	Paired runtime ratio $\downarrow$	Columns added $\downarrow$	Runtime (s) $\downarrow$
Standard CG	1.000 (0.000)	2394 (97)	33.49 (3.11)
Du Merle stabilization	1.266 (0.019)	2500 (93)	43.21 (4.30)
Neame smoothing	0.865 (0.005)	2119 (92)	30.22 (2.88)
Kraul et al. (2023)	0.987 (0.036)	2207 (93)	29.24 (2.70)
Predictive smoothing (Ours)	0.630 (0.016)	1756 (102)	24.84 (2.70)

Table 1: CSP results. Reported values are means and standard errors of per-instance metrics.

Figure 2: Validation performance of predictive dual smoothing as a function of horizon $k$ and initial smoothing weight $\alpha_{0}$ . The best configuration is marked in orange.

$N$	Validation $R^{2}$ $\uparrow$	Paired ratio $\downarrow$	Cols. $\downarrow$	Validation $R^{2}$ $\uparrow$	Paired ratio $\downarrow$	Cols. $\downarrow$
	Predictive Smoothing (Ours)			( Kraul et al., 2023 )
1	-0.858	1.559	3211	0.017	1.222	2507
5	0.836	0.744	1904	0.424	0.920	2193
10	0.857	0.712	1853	0.700	0.920	2176
20	0.869	0.703	1852	0.738	0.930	2150
50	0.873	0.678	1823	0.765	0.935	2114

Table 2: Training data efficiency results for the CSP.

	Paired runtime ratio $\downarrow$
	Smaller than training	Larger than training
Method	$n=250$	$n=2000$	$n=2500$
Standard CG	1.000 (0.000)	1.000 (0.000)	1.000 (0.000)
Neame smoothing	0.849 (0.018)	0.843 (0.018)	0.902 (0.014)
Du Merle stabilization	1.253 (0.035)	1.187 (0.036)	1.312 (0.044)
Kraul et al. (2023)	1.187 (0.073)	0.853 (0.054)	0.895 (0.057)

Table 3: Paired runtime ratios relative to standard CG on out-of-distribution test sets.

Method	Paired runtime ratio $\downarrow$	Columns added $\downarrow$	Runtime (s) $\downarrow$
Standard CG	1.000 (0.000)	18991 (104)	388.93 (5.55)
Du Merle stabilization	0.078 (0.001)	3327 (12)	30.42 (0.43)
Du Merle + Neame smoothing	0.077 (0.001)	3063 (10)	29.74 (0.44)
Du Merle + Pred. smooth. (Ours)	0.041 (0.001)	2598 (27)	15.87 (0.27)

Table 4: GAP results. Reported values are means and standard errors of per-instance metrics.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Prediction horizon $k$	1	3	5	10	50	100	200	Terminal
Validation RMSE	0.078	0.091	0.090	0.097	0.112	0.119	0.124	0.131
Validation $R^{2}$	0.938	0.916	0.918	0.906	0.873	0.855	0.838	0.802

Appendix

Table 5: Predictive accuracy of the predictor as a function of the horizon

k

Figure 3: Evolution of the smoothing strength

\alpha_{t}

over normalized CG progress for the selected CSP configuration (

k=50

\alpha_{0}=1

\gamma=0.9

). The line shows the mean across validation instances and the shaded region shows SEM across instances.

Panel of Figure 4 — Figure 4: Effect of smoothing decay $\gamma$ on CSP validation performance. Each panel reports the paired runtime ratio and number of fallback pricing problems across prediction horizons $k$ and initial smoothing weights $\alpha_{0}$ .

Explore similar work

Learned Pairwise Deep Dual-Optimal Inequalities for Stabilizing Column Generation
Jul 15, 2026Zhengzhong Ricky You, Bo Tang, Haoran Liu +1Vehicle Routing Problem Primal-Dual Methods
Department of Civil Engineering, Tsinghua University, Beijing 100084, China · MIT Sloan School of Management, Massachusetts Institute of Technology, 100 Main Street, Cambridge, MA 02142, USA · Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, USA
Column Generation with Domain-Independent Dynamic Programming
Oct 16, 2025Ryo Kuroiwa, Edward LamMixed-Integer Programming Data Generation
Department of Data Science and Artificial Intelligence, Monash University, Melbourne, Australia · The Graduate University for Advanced Studies, SOKENDAI, Kanagawa, Japan
Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts
May 10, 2026Ilay Yavlovich, Jad Agbaria, Muhamed Mhamed +2Repair-Assignment Problem Combinatorial Optimization
Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology, Haifa, Israel.

Jul 15, 2026, math.OCJ/K move · Enter open · S save

Learned Pairwise Deep Dual-Optimal Inequalities for Stabilizing Column Generation

Zhengzhong Ricky You, Bo Tang, Haoran Liu, Baichuan Mo

Department of Civil Engineering, Tsinghua University, Beijing 100084, China · MIT Sloan School of Management, Massachusetts Institute of Technology, 100 Main Street, Cambridge, MA 02142, USA · Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, USA

Vehicle Routing Problem Primal-Dual Methods Data Generation

Open paper AskPDF arXiv

Column generation (CG) is central to many large-scale optimization algorithms, including branch-price-and-cut methods for vehicle routing problems, but unstable dual solutions can substantially slow its convergence. Existing deep dual-optimal inequalities can reduce this instability by restricting the dual space. Their construction, however, typically relies on problem-specific exchange arguments that are difficult to establish for routing problems with capacity limits, time windows, and other resource constraints. We introduce learned pairwise deep dual-optimal inequalities (L-PDDOIs), a learning framework that predicts pairwise orderings between dual variables and incorporates their primal counterparts directly into the master problem. To construct training labels, the framework samples optimal dual solutions and selects pairwise order relations that hold simultaneously on a sufficiently large common subset of the samples. A classifier then assigns a score to each candidate relation. Because conflicts and redundancies among the predicted relations can impair performance, graph-based postprocessing filters and compresses the candidate set before deployment. We further introduce a recovery procedure that selectively relaxes learned inequalities and provides a certificate when the baseline CG bound has been restored. On the main test sets for the capacitated vehicle routing problem and the vehicle routing problem with time windows, direct deployment of L-PDDOIs reduces the geometric mean root CG time by 89.7% and 93.9%, respectively, while incurring mean bound losses of only 1.3% and 0.5%. The recovery procedure retains corresponding time reductions of 54.8% and 83.1%, respectively, while guaranteeing no loss in the CG bound.

Abstract

Explore similar work

Learned Pairwise Deep Dual-Optimal Inequalities for Stabilizing Column Generation

Column Generation with Domain-Independent Dynamic Programming

Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts