G-2026-51
Penalty function-based dual stabilization for column generation with graph neural networks: Application to the vehicle routing problem with stochastic demands
, , , and
BibTeX referenceColumn generation is a widely used dual-guided approach to solve highly degenerate problems. During the resolution, the degeneracy of the master problem often manifests through dual oscillations, which results in many iterations in which no progress is made towards the optimal solution. To mitigate the impact of degeneracy, dual stabilization techniques can be added to the process, with the aim of preventing strong dual oscillations and speeding up convergence. Such methods involve numerous design choices, including the choice of the initial stability center, which requires accurately estimating the optimal dual values. This paper introduces a machine-learning framework leveraging graph neural networks to predict these values and use them as the initial stability center in a dual stabilization framework with dynamic parameter updates. Our experiments focus on the vehicle routing problem with stochastic demands (40 instances with up to 60 customers), a challenging variant of the classical VRP for which an accurate estimate of the optimal dual values is hard to retrieve. Our method outperforms all algorithm variants considered.
Published October 2026 , 21 pages
Research Axes
Research application
Document
G2651.pdf (1 MB)