# Learned Pairwise Deep Dual-Optimal Inequalities for Stabilizing Column Generation

arXiv: https://arxiv.org/abs/2607.13373 · HTML: https://mlsanity.com/paper/2607.13373/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 41 references that are in the map.
- First posted on arXiv 15 Jul 2026.

## Builds on (most cited first, 10 of 10)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Machine-learning-based arc selection for constrained shortest path problems in column generation](https://mlsanity.com/paper/2201.02535/) (2022)
- [Use of Machine Learning Models to Warmstart Column Generation for Unit Commitment](https://mlsanity.com/paper/2110.06872/) (2021)
- [Enhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problems](https://mlsanity.com/paper/2310.09686/) (2023)
- [A Reinforcement-Learning-Based Multiple-Column Selection Strategy for Column Generation](https://mlsanity.com/paper/2312.14213/) (2023)
- [Smooth and flexible dual optimal inequalities](https://mlsanity.com/paper/2001.02267/) (2020)
- [Adaptive Stabilization Based on Machine Learning for Column Generation](https://mlsanity.com/paper/2405.11198/) (2024)
- [Accelerating Column Generation via Flexible Dual Optimal Inequalities with Application to Entity Resolution](https://mlsanity.com/paper/1909.05460/) (2019)
- [Detour Dual Optimal Inequalities for Column Generation with Application to Routing and Location](https://mlsanity.com/paper/2108.09233/) (2021)
- [Large-scale optimization with the primal-dual column generation method](https://mlsanity.com/paper/1309.2168/) (2013)

## Abstract (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.