Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt

Summary

The paper introduces a learning-to-search (L2S) solver called Neural k-Opt (NeuOpt) for routing problems. NeuOpt learns to perform flexible k-opt exchanges using a tailored action factorization method and a customized recurrent dual-stream decoder. The paper also proposes the Guided Infeasible Region Exploration (GIRE) scheme, which allows the autonomous exploration of both feasible and infeasible regions. The experiments on TSP and CVRP with up to 100 nodes show that NeuOpt could outperform other learning-based methods slightly. However, the solving speed could be very slow. It also cannot outperform HGS and LKH3 from OR fields. Overall, I think the topic and proposed method are interesting, however, the results are not significant.

Strengths

* The paper is mostly well-written, except that Figure 1 is too complex to help the reviewer to understand the basic ideas of the proposed method. * The literature reviews are quite impressive, which include necessary classic and SoTA methods. * The proposed NeuOpt and Guided infeasible region exploration seem reasonable. * The proposed MDP for k-opt is interesting

Weaknesses

* The experiments on TSP and CVRP with up to 100 nodes show that NeuOpt could outperform other learning-based methods slightly. However, the solving speed could be very slow. It also cannot outperform HGS and LKH3 from OR fields. Overall, I think the results are not significant. * Given the complexity of the method and the code is not provided, reproducibility could be a problem.

Questions

The feasibility of solutions is not discussed in the experiments. To what extent does the Guided Infeasible Region Exploration method impact the feasibility? The reviewer encourages the authors to evaluate the method on VRPTW or TSPTW to make a more solid benchmark.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The limitations have been discussed in the main body. In Section 7, the first point "it falls short against some L2P solvers (e.g., [5, 6]) for larger-scale TSPs" is a good discussion about the limitation. However, the second and third points are actually the advantages of the paper, rather than the limitations.

Summary

The paper aims to learn the k-opt operation, one of the famous local search methods, via neural networks. In particular, the authors model the k-opt operation as a sequential node selection process and use a recurrent dual-stream (RDS) decoder. Furthermore, a guided infeasible region exploration (GIRE) is suggested to encourage the policy to escape local optima. The paper models the k-opt as a sequence of basic moves on open Hamiltonian paths (not cycles), which allows the neural network model easily learns the k-opt operation. Since the end of the sequence (i.e., E-move) is a kind of I-moves, k can be flexibly adjusted according to states. GIRE allows the model to explore infeasible regions, not only feasible regions; it encourages the model to escape local optima. In addition, the portion of infeasible solutions is dynamically adjusted.

Strengths

The paper is well-written in general, and the key ideas are clearly delivered. The extensive experiments with various baselines suggest that the proposed method can mitigate the inefficiency of L2S solvers. One of the main benefits is that we can choose the proper K, the number of DA, and T according to the available computation budget. Also, the results show that NeuOpt gives promising performances with similar time with L2C algorithms.

Weaknesses

There is no analysis of where the performances come from. the k-opt operations are well-working with fixed k. Comparisons between the original k-opt and NeuOpt are required. Some detailed but important information is missing or hard to be found (e.g., encoding scheme, dynamic augmentation, initial tour)

Questions

I have some questions about the details. 1. Effectiveness of learning the S-move. I think that choosing the S-move also gives good performances. 2. Why is LKH3 (known as better than LKH2) not employed as a baseline? 3. Whether the encoding is necessary for every t? 4. How is the problem augmented in detail? I’ve read through the appendix but couldn’t find it. Minor Comments: 1. I think further explanation for ES features is required (maybe in the appendix) 2. For better readability, additional cross-references for contents in the appendix are recommended. 3. There is no explanation when the other papers are referenced (e.g., line 192, 257). I recommend adding further descriptions.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

I think the dual-stream structure is restricted to consider additional context information.

Summary

In this paper, the authors propose Neural k-Opt (NeuOpt) that factorizes a generic k-opt exchange operation as a series of base operations. They also introduce Guided Infeasible Region Exploration (GIRE) scheme for Capacitated Vehicle Routing Problem (CVRP) where one augments a reward function for RL with signals about exploring infeasible solution spaces. On the model architecture side, the authors propose a recurrent dual-stream decoder that consumes both moves and edges. The authors provided a comprehensive comparison with baseline methods for problems of sizes up to 100 cities.

Strengths

1. I found the action factorization novel and general. A limitation of past k-Opt based learning-to-search methods is that they require a pre-determined value of k. The proposed factorization method can accommodate arbitrary k given an agent enough number of steps. 2. GIRE seems a promising approach to incorporating information about near-feasible regions into explorations. As far as I know, this contribution is novel. 3. The empirical comparisons with baseline methods are comprehensive. I appreciate the authors including an up-to-date list of baseline methods. There are some expected issues with reproductions but I definitely applaud the authors’ efforts here. 4. The paper is relatively well-written. The authors did a good job of packing a dense set of information within the page limit.

Weaknesses

1. The problem sizes considered are relatively small. Methods like DIFUSCO experimented with sizes up to 10000 cities. It is unclear how practically useful this method is with small problem sizes. 2. Another common evaluation mode for these classes of problems is for the generalization ability of a trained model. That is, extrapolate the model performance on problems of larger sizes than those in the training set. This is not considered in this paper. 3. In general, the empirical results are mixed. On TSP, NeuOpt is not better than DPDP and Att-GCN+MCTS. The comparison with DIFUSCO is obfuscated by a large time discrepancy from the original paper, possibly due to difficulty in reproducing their results. On CVRP, POMO+EAS+SGBS methods are comparable with NeuOpt. 4. The main advantage of the factorized action representation is that one could potentially handle arbitrary k-Opt in a general way. However, in the experiments, the authors used a value of 4 for k which seemed limiting. In addition, in the ablation on values of k, larger k values worked better, so why did the authors not choose a larger value of k for the main evaluations? 5. There are some places where the exposition could be improved. Please see my questions below.

Questions

1. In section 5 about the reward shaping (near line 266), how to compute $P_t(\mathcal{U}|\mathcal{U})$ exactly? 2. In the entropy computation, why $P_t(\mathcal{U}|\mathcal{F})$ and $P_t(\mathcal{F}|\mathcal{U})$ are not included? It is possible to transition between feasible and infeasible solution spaces. 3. The actual entropy calculation involves hyperparameters $c_1$ and $c_2$. Can the authors provide more context on how they were chosen and their impact on the stability of training? 4. In Table 1, for different variants of NeuOpt, what does the DA number refer to? Is that the $T_{DA}$ mentioned in section 4.3? 5. In Figure 5(a), the results for K = 5 and 6 w/o E-move are missing.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors could add discussions about the generalization ability of trained models as well as scaling to larger problem sizes.

Summary

The paper introduces Neural k-Opt (NeuOpt), a deep learning-based vehicle routing solver, designed to handle k-opt exchanges for any k≥2. Unlike existing Learning-to-Search (L2S) solvers, NeuOpt employs a tailored action factorization method, which allows complex k-opt exchanges to be broken down into simpler basis moves. This approach grants the model the flexibility to determine an appropriate k for each search step, enabling a balance between coarse-grained (larger k) and fine-grained (smaller k) searches. Moreover, the paper introduces Guided Infeasible Region Exploration (GIRE) scheme that promotes exploration of both feasible and infeasible regions in the search space. GIRE enriches the policy network with additional features to indicate constraint violations and exploration behavior statistics, aiding in escaping local optima, discovering shortcuts to better solutions, and enhancing the model's understanding of the problem landscapes. NeuOpt is trained using reinforcement learning (RL) and incorporates a dynamic data augmentation method during inference for improved efficiency. Extensive experiments on classic vehicle routing problem variants (TSP and CVRP) demonstrate the superiority of NeuOpt and GIRE over some existing approaches, including traditional hand-crafted solvers.

Strengths

- Novel Approach: The paper introduces a novel approach called Neural k-Opt (NeuOpt) to handle k-opt exchanges for vehicle routing problems. This approach offers flexibility by allowing k to be any value ≥2, which can potentially lead to better solutions and more efficient search processes. - Guided Infeasible Region Exploration (GIRE): The introduction of GIRE is a significant contribution that promotes exploration of both feasible and infeasible regions in the search space. This unique scheme bridges feasible regions, helps escape local optima, and forces explicit awareness of the VRP constraints, potentially leading to improved performance in constrained VRPs. - Comprehensive Evaluation: The paper claims to have extensive experiments on classic VRP variants (TSP and CVRP) to validate the proposed NeuOpt and GIRE. A thorough evaluation of the model's performance on various VRP instances can demonstrate its effectiveness and potential advantages over existing methods.

Weaknesses

- Scalability: While the paper claims that NeuOpt outperforms other methods, including hand-crafted solvers, there is no mention of its scalability to larger and more complex instances of vehicle routing problems. The effectiveness of NeuOpt on larger and real-world datasets should be explored. - Complexity of Action Factorization: Although the tailored action factorization method is introduced to handle k-opt exchanges flexibly, it may introduce increased complexity in the model's architecture and training process. The paper should discuss potential trade-offs and computational costs associated with the proposed factorization.

Questions

- Figure 1 is very hard to process... - lines 122-123: I believe the definition of TSP is slightly inaccurate. The main objective of the TSP is to find the optimal Hamiltonian cycle that **minimizes** the total distance or cost required to visit all the nodes exactly once and return to the starting node. - Can authors provide more discussions on why choosing k dynamically should escape local minimas?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

2 fair

Contribution

3 good

Limitations

see Weaknesses

Thank you for the response

I want to thank the authors for their detailed responses to my questions. I would suggest including the generalization results in the main paper in a revision since that is an important set of experiments showcasing the effectiveness of the proposed method. As my questions are well addressed, I will raise my score to 7.

Thank you for the responses.

Thank you for faithfully answering my responses. I will maintain my score.

Thanks for authors' rebuttal!

Reviewer 2dzf, did the authors address your concerns about significance of the performance, code availability and other concerns? Thanks.

Thank you for the response

I truly appreciate the authors for taking the time to address my concerns. Upon thorough consideration of all responses including mine and others, I maintain my viewpoint that the results, in comparison to baseline LKH-3 and HGS, still lack significance. This is especially noteworthy given the relatively small scale of the routing problem and the time required for solving (spanning hours and days). While I acknowledge that the proposed method could potentially be integrated into approaches like TAM (Two-stage Dividing Method) [1] and L2D (Learn-to-Delegate) [2] to tackle larger-scale VRPs as sub-solvers, it's concerning that the execution time would considerably increase when employing the proposed method as opposed to utilizing LKH-3 or HGS (could obtain good results fast for small-scale VRPs). The discussion about the feasibility and extension to other constraints still has a lot of room to improve. An additional point of consideration is the method employed to measure the solving time of the proposed approach, as well as the corresponding benchmarks like LKH-3 and HGS. Clear elaboration on this matter is necessary. Despite the aforementioned lingering concerns, I do find the proposed ideas interesting, particularly the MDP formulation for k-opt. I am also anticipating the release of the code. On the whole, I am inclined to raise and finalize my evaluation score to 5, with the expectation that the outlined matters will be duly addressed and clarified. [1] Hou Q, Yang J, Su Y, et al. Generalize Learned Heuristics to Solve Large-scale Vehicle Routing Problems in Real-time[C]//The Eleventh International Conference on Learning Representations. 2023. [2] Li S, Yan Z, Wu C. Learning to delegate for large-scale vehicle routing[J]. Advances in Neural Information Processing Systems, 2021.