- Rating
- 3
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes predictive dual smoothing for column generation. Instead of smoothing the current dual solution toward past duals, it predicts a future dual state with a lightweight per-constraint MLP trained offline from standard CG trajectories. The predicted dual is used only to guide pricing; columns are checked with the current dual, with exact pricing as a fallback, preserving correctness. Experiments on cutting stock and generalized assignment show fewer generated columns and lower runtime than standard CG and several stabilization baselines, including when combined with Du Merle stabilization.
Critical strengths
- The method is conceptually simple and integrates naturally into the CG loop.
- The empirical improvements are substantial and consistent across the two studied problems.
Critical weaknesses
- The claim that the feature representation is generic is not fully demonstrated, since the empirical scope is limited to two synthetic problem families, with only instance-size generalization studied for CSP.
- The paper does not sufficiently compare against a simpler learned tie-breaking baseline. The main gains may partly come from breaking ties among many equally optimal pricing solutions
Questions for authors
- Could you provide a runtime breakdown separating predictor inference, RMP solution time, pricing time, fallback pricing, and the number of CG iterations?
- How robust is the method to distribution shift beyond instance size, such as different demand or coefficient distributions?
2 comments
Runtime breakdown. We did not log the individual runtime components in our original experiment, so we reran predictive smoothing on both the CSP and GAP test sets with additional timing code. The runtime breakdown is reported below.
| Metric | CSP | GAP |
|---|---|---|
| Total runtime (s) | 24.54 (2.68) | 15.18 (0.24) |
| RMP solution time (s) | 14.00 (2.01) | 13.73 (0.22) |
| Feature construction (s) | 0.17 (0.01) | 0.49 (0.01) |
| Predictor inference (s) | 0.15 (0.01) | 0.02 (0.00) |
| Primary pricing time (s) | 9.58 (0.68) | 0.50 (0.01) |
| Fallback pricing time (s) | 0.19 (0.01) | 0.16 (0.00) |
| Master-update time (s) | 0.44 (0.03) | 0.28 (0.00) |
| CG iterations | 1756.6 (102.2) | 291.5 (3.9) |
Other forms of distribution shift.
We expect the effectiveness of predictive smoothing under other forms of distribution shift to depend on the nature and magnitude of the shift, as is generally the case for supervised learning methods. An important property of our approach, however, is that poor predictions do not compromise the correctness of CG. The fallback mechanism ensures that the procedure will converge even when the predictor is applied to instances that differ significantly from those seen during training. Whether the predictor still accelerates CG on such instances is a separate question. Beyond instance-size generalization, we have not systematically investigated this and will acknowledge it as a limitation in the revised paper.
Thank you for your positive review of our paper. We found your suggestion regarding learned tie-breaking particularly interesting and have conducted additional experiments to investigate this. We address your comments and questions below.
Generic feature representation. We would like to clarify what we mean by a ‘generic’ feature representation. Our claim is not that the proposed features necessarily lead to good predictive performance on every problem class, but rather that they can be constructed independently of the problem class. We provide a generic way to construct features from quantities available in the CG procedure itself. This allows the feature representation to be applied to new problem classes without requiring problem-specific feature engineering. This is in contrast to most existing work, which relies on features derived from the structure of a particular optimization problem.
Whether our generic feature representation provides sufficient predictive information to perform well on a particular problem class is a separate, empirical question. We agree that experiments on additional problem classes would further strengthen the evidence for this, but distinguish this from the features being generic or not. We will clarify this distinction in the revised paper.
Learned tie-breaking baseline. Yes, this is something we looked into extensively when developing the method. As we mention in the paper (lines 408–412), even a very small smoothing weight (α0=0.01) leads to a substantial improvement on CSP: "a small perturbation towards the predicted future dual already acts as an informed tie-breaker among these columns." We therefore agree that part of the improvement can be explained by tie-breaking, at least for CSP.
Following your suggestion, we implemented a baseline that solves the pricing problem using the current RMP duals and, among the optimal pricing solutions, selects the column with the best objective value under our predicted future duals. We use the same k-step predictors as in predictive smoothing. The results on our validation sets are as follows:
On CSP, learned tie-breaking comes quite close to predictive smoothing in terms of the number of columns generated. On GAP, however, the difference is considerably larger. We also measured how often predictive smoothing generates columns that are not optimal solutions under the current RMP duals. This is the case for 49% and 63% of the accepted columns on CSP and GAP, respectively. Thus, while informed tie-breaking can be useful, there is also a benefit to moving away from optimal pricing solutions.
We would also argue that predictive smoothing is actually simpler to implement than learned tie-breaking. While learned tie-breaking requires optimizing a secondary objective over the set of optimal pricing solutions, predictive smoothing simply changes the objective coefficients of the pricing problem, allowing us to use the existing pricing solver without modification. This is an important practical advantage, and the additional computational work required for explicit tie-breaking is also reflected in the runtimes above.
We will include these experiments and the corresponding discussion in the revised paper.