math.OCJul 15, 2026

Learned Pairwise Deep Dual-Optimal Inequalities for Stabilizing Column Generation

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

Organizations: 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

Abstract

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.

Explore similar work

CardsList
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
Mixed-Integer Linear ProgrammingPricesGenerating
AskPDF
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 O(N3)\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 O(N2)\mathcal{O}(N^{2}) memory bottleneck of graph models, enabling scalable neural warm-starting up to N=16,384N=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
Patient-To-Room Assignment ProblemMixed-Integer Linear ProgrammingCombinatorial OptimizationNeural SolversJoint OptimizationLightweight Convolutional Neural Network Hardware Accelerator
AskPDF
May 18, 2026stat.ML

Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming

Lagrangian Relaxation (LR) is a powerful technique for solving large-scale Mixed Integer Linear Programming (MILP), particularly those with decomposable structures, such as vehicle routing or unit commitment problems. By relaxing the coupling constraints, LR enables parallel subproblem solving and often yields tighter dual bounds than standard linear programming relaxations, which is crucial for efficient branch-and-bound pruning. While recent empirical work has shown promising results using machine learning to predict these multipliers, a theoretical understanding of such methods remains an open question. In this work, we bridge this gap by analyzing the problem of learning LR through the lens of Data-driven Algorithm Design, i.e., a statistical learning problem over a distribution of problem instances. Our contributions are as follows: first, we derive a generalization bound of O(s1.5/N)\mathcal{O}(s^{1.5}/\sqrt{N}) for the learned multipliers, where ss is the number of coupling constraints and NN is the sample size. Second, we provide a minimax lower-bound of Ω(s/N)Ω(s/\sqrt{N}), proving that a linear dependency is unavoidable. Third, we constructively close this theoretical gap by proving that Stochastic Gradient Ascent (SGA) with averaging achieves the minimax optimal rate Θ(s/N)Θ(s/\sqrt{N}). Finally, we extend our framework to the learning-to-warm-start setting, proving that it achieves a fast, minimax-optimal rate of Θ(s/N)Θ(s/N) and establishing a theoretical advantage over direct multiplier prediction.
Tung Quoc Le, Anh Tuan Nguyen, Viet Anh Nguyen
Mixed-Integer Linear ProgrammingLagrangian RelaxationStochastic Gradient DescentData-Driven
AskPDF