Unsupervised Learning of Self-Consistent Dual Prices for Column Generation

Column generation (CG) underpins algorithms for large-scale integer programming by generating columns without explicitly enumerating the full column pool. A fundamental challenge for CG is primal degeneracy in the restricted master problem (RMP), which can lead to repeated costly pricing subproblems that change dual prices without improving primal objective. To address this issue, we propose an unsupervised learning framework that trains a neural network to predict self-consistent dual prices (SCDP), whose displacement from the current RMP dual agrees with the ascent step over the dual objective induced by their own pricing responses. We prove that, at exact self-consistency, following SCDP guarantees sufficient ascent on the smoothed full-dual bound, thereby closing primal-dual gap even when the RMP objective stalls. We derive a proximal loss function from the smoothed full-dual objective and obtain its gradient directly from perturbed pricing responses, enabling gradient-based training. To make training practical, we establish that an unbiased gradient estimate can be obtained with a single perturbed pricing solve per training iteration. At deployment, the trained network predicts dual prices to guide column discovery, while exact pricing at the RMP dual preserves LP optimality. Experiments demonstrate runtime reductions of 63%, 94%, and 47% on the capacitated vehicle routing problem, its variant with time windows, and the cutting stock problem, respectively.