- Rating
- 1
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The authors propose a heterogeneous GNN-based primal heuristic for the dial-a-ride problem, which aims to speed up the optimization process of exact solvers, while maintaining their guarantees and certifications. Beyond the heterogeneous graph representation of the MIP, the authors contribute with a score-refinement step and a confidence-guided primal-search step. Experimentally, the HGNN-based heuristic is shown to both produce accurate arc-level predictions and speed up the end-to-end optimization process across 10 DARP instances.
Critical strengths
-
Section 5.2 shows the proposed method is effective at predicting arc inclusion/exclusion, balancing precision and recall better than the two baselines/ablations. Section 5.3 similarly demonstrates speed-ups and optimality advantages in the end-to-end setting.
-
Overall, the idea of learning-augmented optimization via primal-search is principled and sound. The two additional proposed stages also seem sound, although their presentation is somewhat dense.
Critical weaknesses
I have two main points of criticism, both individually grounds to reject the paper in my opinion:
- The related work on learning-based methods is limited to a single paragraph and does not position the methodological contribution sufficiently against prior work.
- The paper cites Ding et al. (2020) and Nair et al. (2020), but does not explain how the method differs from them. This is especially relevant for Ding et al., who also uses a MIP graph representation to predict variable values.
- There is a substantial amount of related work that also work in a related way [1-4], using predictions on the MIP graph with a subsequent solver-based search. How do these methods, and others, compare to your approach?
- Overall, learning for the DARP and related pickup-and-delivery problems is not reviewed at all. For example, [5] uses a GNN to score arcs of a DARP-variant graph in order to restrict the solver's search space.
- If the difference is only the heterogeneous graph formulation designed specifically for the DARP together with the refinement and search steps, the methodological contribution seems insufficient for a top deep learning venue like ICLR.
- My impression is that the work might be better suited to an optimization or transportation venue, where the problem itself would be of interest. At the moment, it is unclear to me what wider conclusions could be relevant for the ICLR community.
- The benchmark suite is relatively slim. Results are only presented for 10 test instances across one problem size. While the authors acknowledge this, I think a broader comparison is needed to properly assess the method.
- Primarily, I would have liked to see comparisons with other primal heuristics, including classical ones and general learning-based ones (see point above about related work), in the end-to-end optimization experiments. Does the HGNN improve convergence speed and solution quality over strong baselines, not just the cold start approach?
- I also think a scalability study is needed. The instances considered here are rather small.
[1] Khalil, Morris, Lodi, "MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers," AAAI, 2022.
[2] Han et al., "A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming," ICLR, 2023.
[3] Huang et al., "Contrastive Predict-and-Search for Mixed Integer Linear Programs," ICML, 2024.
[4] Huang et al., "Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning," ICML, 2023.
[5] Lu et al., "Boosting Column Generation with Graph Neural Networks for Joint Rider Trip Planning and Crew Shift Scheduling," arXiv:2401.03692, 2024.
Questions for authors
- How does the method scale with problem size? At the moment the evaluated graphs/instances are rather small. Does the heterogeneous MIP graph become prohibitively large for substantially larger instances?
- Relatedly, the label generation seems computationally intensive, how much time does this step take with the given hardware?