acceptodds
Under review as a conference paper at ICLR 2027

Unsupervised Learning of Self-Consistent Dual Prices for Column Generation

17 views

Abstract

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.

Primary area:
optimization
Keywords:
Column Generation, Unsupervised Learning, Perturbed Optimizers, Self-Consistent Dual Prices

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_QtVWOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes an unsupervised learning method to improve the efficiency of column generation (CG). The main idea is to predict self-consistent dual prices (SCDP) using a neural network, which can help reduce the slow convergence caused by degeneracy in the restricted master problem (RMP). The authors design a training loss based on the smoothed Lagrangian dual function and use perturbed pricing results to estimate the gradient without requiring optimal dual labels. They also propose a column pool replay method to reduce the training cost and provide theoretical results for dual improvement and unbiased gradient estimation. The experiments are conducted on CVRP, CVRPTW, and CSP. The results show that the proposed method can reduce the running time compared with standard CG and several existing methods.

Critical strengths

Strengths

  1. The problem is important and well-motivated. Degeneracy is a common problem in column generation and may lead to slow convergence. The paper focuses on this problem and tries to improve the efficiency of CG by learning better dual prices.

  2. The proposed learning framework is interesting. The authors propose a self-consistent condition and use it to design an unsupervised training loss. Unlike supervised methods, this method does not require optimal dual labels. The paper also provides theoretical results to support the proposed method.

  3. The replay method improves the practical applicability of the framework. Training with perturbed pricing may require solving many expensive pricing subproblems. The proposed column pool replay method reduces the number of pricing solves needed for gradient estimation. This is an important computational improvement and makes the learning framework more practical for problems with expensive pricing subproblems.

Critical weaknesses
  1. The choice of UU may not satisfy the theoretical assumptions. In Section 2.1, the authors require UU to be an upper bound on the total column weight without changing the optimal value of the original problem. However, in Appendix E.2, the authors set UU to the total demand divided by vehicle capacity, rounded up, for CVRP and CVRPTW. This value is generally a lower bound on the number of vehicles, rather than an upper bound on the total column weight. Therefore, it is not clear whether the theoretical assumptions are satisfied in the experiments. This may also affect the validity of the proposed dual bound.

  2. The theoretical guarantee does not directly apply to the learned dual prices. Theorem 1 guarantees dual improvement when the self-consistency condition is exactly satisfied. However, the neural network only predicts an approximate solution. Although the authors provide an error bound in Appendix C.2, it is not clear how often the learned dual prices satisfy the sufficient ascent condition in practice. More experimental results on the self-consistency residual would be helpful.

  3. The generalization ability is not fully evaluated. The authors train the model on small instances and test it on larger instances, which shows some ability to generalize across problem sizes. However, the training and test instances may still have similar distributions. It is not clear whether the learned model can work well when the problem distribution changes, such as different customer locations, demands, or vehicle capacities. Also, the authors train separate models for different problem types, so the experiments do not show generalization across different problems. More experiments on different instance distributions would help demonstrate the generalization ability of the proposed method.

Questions for authors

Please see "Critical Weakness". I would like to increase my score my concerns are resolved.

Reviewer_Xaj4OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper attempts to tackle the primal degeneracy issue in column generation via an unsupervised learning approach. The proposed method is hinged on a self-consistent dual price (SCDP) scheme, which aims to establish a self-consistent condition, that can learn the dual without computing them directly. More specifically, the paper comes up with a loss function that build the pricing function by perturbing duals. The paper proposes proposition and theorem to support its claim that such constructed pricing problem is convex and a gradient can be easily and cheaply computed, hence deriving a global minimizer. Tackling the degeneracy issue (or stabilization) is an important topic, and recent machine learning approach is showing great promise in tackling this challenge.

Critical strengths

One advantage of the proposed unsupervised approach is that the machine learning model can be trained from pricing feedback without computing dual with a label. But the paper has not spent much space in describing this aspect.

Reducing the computational cost of the pricing problems in the CG process is very interesting. The paper has some great ideas in this regard. If the authors can improve the convexity of the pricing problem (through perturbation), then this could be a very valuable contribution to this area, as it has the potential to generalize across different combinatorial optimization problems.

Critical weaknesses

Unsupervised learning aspect is not clearly described.

The proposition and theorem need to be enhanced, so the assumption of the convexity holds across different problems.

Questions for authors

Q1: How do you determine if D_r is concave? I suppose your Proposition 1 (and your self-consistent dual price, and Theorem 1) all depend on this assumption, so it needs to be very clearly explained in B1. Furthermore, your gradient method would work if you had a concave (or unimodal) dual function, but it does not guarantee if you have a non-convex shape, which means it is possible to get trapped in local optima.

Q2: what is the rationale to perturb the pricing, ie., why such a sampling approach is more effective? I find it confusing since you use the perturbation of the pricing to work out the gradient, but if your constructed model from perturbation were low-quality, then the estimated gradient would be also poor. Is that correct? Your method relies heavily on perturbing price problem, but you also admit that "solving the pricing problem under multiple perturbations" can be very costly, hence what is the reasoning here?

Q3: One central question is whether different pricing structures for different problems (in your experiments) all have a convex shape for the dual, hence guarantee finding a minimizer? I feel that you need to provide more evidence to prove this is indeed the case.

Reviewer_MNHAOpenReview ↗
Rating
3(+1)
Confidence
1
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper considers the problem of accelerating the column generation (CG) process for solving LP relaxations of large-scale integer programs (IPs). Essentially, given a master problem (MP), at time t with the corresponding columns Rt\mathcal R_t, CG will: (1) solve the restricted master problem (RMP) corresponding to Rt\mathcal R_t to obtain the optimal dual solution yty_t, (2) use yty_t to solve the pricing problem to obtain the next column candidate xtx_t, and (3) add xtx_t (if it has a negative reduced cost) to the current column set Rt\mathcal R_t to acquire Rt+1\mathcal R_{t+1} and continue the process.

However, the authors argue that using yty_t to acquire xtx_t can sometimes be problematic (for degenerate problem instances), leading to a column xtx_t that, when added to Rt\mathcal R_t, does not improve the RMP objective, resulting in a slow CG process. To tackle this challenge, the authors propose to learn qtq_t, called the self-consistent dual price, as an alternative to yty_t, and use it in the process of generating column xtx_t. They then propose training a NN to predict qtq_t from the current CG state with an unsupervised training procedure. Specifically, they construct a proximal learning objective based on the smoothed full Lagrangian dual function, whose gradient can be estimated using perturbed pricing problems without requiring optimal dual labels. They also develop an efficient gradient estimation procedure based on reusing generated columns.

The authors then provide theoretical results guaranteeing that the exact self-consistent dual price yields sufficient ascent in the smoothed full-dual bound, even when the RMP objective stalls. They also establish conditions for unbiased gradient estimation during training. Finally, experiments on vehicle routing and cutting-stock problems demonstrate substantial reductions in CG runtime compared to existing methods.

Critical strengths

First things first, I am not an expert in this topic, so my assessment might be off.

The paper presentation is clear and easy to follow (for a general audience like me). I think the motivation is clear and the proposed method is sound.

Critical weaknesses

My main concern is mostly about the novelty of some claims in this paper, especially compared to the paper [1]. As far as I understand, that paper already proposed learning the dual prices to accelerate the CG process using an unsupervised training procedure, where the training objective is also based on the Lagrangian dual bound and the gradients are estimated using the pricing subproblem. Moreover, I think the quadratic regularization has already been considered in that paper.

While I know that the learning objective of this paper is different (based on self-consistency) and uses the learned dual prices throughout the CG process rather than only for warm-starting the CG process like [1], I am not fully convinced that the two methods are substantially different. I mean, there are many theoretical analyses and tricks used in this paper that are borrowed from [1]. Can the authors comment on this point?

Reference

[1] Sugishita et al. Use of machine learning models to warmstart column generation for unit commitment, INFORMS Journal of Computing, 2024

Questions for authors

See weaknesses

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revised Manuscript Uploaded

We thank all reviewers for their constructive feedback. We have uploaded a revised manuscript. Revisions made in response to the reviewers are marked in blue\color{blue}{\textbf{blue}}, and our own revisions, mainly to the discussion of the experimental results for clarity, are marked in navy\color{#000080}{\textbf{navy}}. The main changes are:

  • Reviewer Xaj4. After Proposition 1, we explain why DD and DτD_\tau are concave for every CG master. We state Theorem 1 under the assumptions of Proposition 1 and note in Section 2.3 that the minimizer of the strongly convex loss is unique. We describe in Section 2.3 how the unsupervised training uses the perturbed pricing responses (Eq. (8) and Algorithm 1).
  • Reviewer QtVW. We correct the description of the weight bound UU used in the experiments (Appendix E.2). We report in Section 4.2 how often the learned prices raise DD and DτD_\tau and satisfy the strict-ascent condition of Proposition C.1. We add two additional CG benchmarks: the generalized assignment problem and the graph coloring problem (Appendix E.5), and an analysis of SCDP generalization outside the training range (Appendix E.6).
  • Reviewer MNHA. We discuss the relation to Sugishita et al. (2024), Nair et al. (2018), and Briant et al. (2008) in Section 5.

We are happy to answer any further questions during the discussion period.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.