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

Jul 15, 2026math.OC

Learned Pairwise Deep Dual-Optimal Inequalities for Stabilizing Column Generation

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.

Zhengzhong Ricky You, Bo Tang, Haoran Liu +1

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

Ask PDF

Oct 16, 2025math.OC

Column Generation with Domain-Independent Dynamic Programming

Column generation and branch-and-price (B&P) are leading mathematical optimization methods for large-scale exact optimization, iterating between solving a master problem and a pricing problem. Due to the difficulty of discrete optimization, high-performance column generation often relies on a custom pricing algorithm built specifically to exploit the problem's structure. This bespoke nature of the pricing solver makes column generation a problem-specific method and hinders the use of generic implementations across a wide range of problems. We show that domain-independent dynamic programming (DIDP), a model-based paradigm for dynamic programming, can be used as a generic pricing solver. We develop new modeling features and a solving algorithm for DIDP to achieve better performance in typical pricing problems. We demonstrate that in four problem classes, our implementations of B&P, with pricing by DIDP, empirically outperform an existing automated B&P solver and B&P with pricing by mixed-integer programming or constraint programming.

Ryo Kuroiwa, Edward Lam

Department of Data Science and Artificial Intelligence, Monash University, Melbourne, Australia · The Graduate University for Advanced Studies, SOKENDAI, Kanagawa, Japan

Mixed-Integer Programming Data Generation

Ask PDF

May 10, 2026cs.LG

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

The Linear Assignment Problem is a fundamental combinatorial optimization task where classical exact solvers ensure optimality but suffer from an

\mathcal{O}(N^{3})

bottleneck, while recent neural approximations struggle with scalability and exactness. We propose a learning-augmented framework that accelerates exact solvers by predicting dual variables to warm-start the search, backed by a fallback mechanism to preserve worst-case guarantees. Central to our approach is RowDualNet, a lightweight, row-independent architecture that avoids the

\mathcal{O}(N^{2})

memory bottleneck of graph models, enabling scalable neural warm-starting up to

N=16{,}384

. Feasibility is guaranteed by construction via the Min-Trick mechanism, completely eliminating the need for costly iterative projections. Empirically, our method drastically reduces the search effort of the Jonker-Volgenant (LAPJV) algorithm, yielding robust zero-shot generalization with strict optimality and end-to-end speedups of over 2x on complex synthetic data, 1.25x on real-world tracking, and 1.5x on transportation networks.

Ilay Yavlovich, Jad Agbaria, Muhamed Mhamed +2

Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology, Haifa, Israel.

Repair-Assignment Problem Combinatorial Optimization Neural Network Optimization

Ask PDF