- 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
-
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.
-
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.
-
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
-
The choice of may not satisfy the theoretical assumptions. In Section 2.1, the authors require 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 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.
-
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.
-
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.
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, and our own revisions, mainly to the discussion of the experimental results for clarity, are marked in navy. The main changes are:
We are happy to answer any further questions during the discussion period.