Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The mTSP with the goal of minimizing the longest route is considered, which minimizes the maximum route. This objective results in a balanced-length set of routes, which compared to the sum of routes obtains a more practical result. A graph representation based on the worker and assigned tasks is defined, then a type-aware graph attention (TGA) embedding procedure is proposed in which it obtains an embedding for node and edge representation. The state for each entity involves the 2D coordinates of the entity and the boolean indicator of idleness and assigned task of the worker. The action is worker-to-task assignment, and the reward is the makespan of finishing the problem, which is a sparse function. In type-aware graph attention (TGA) embedding, the embedding of node and edge are obtained and using the attention mechanism, an important weight for the embedding of each edge is obtained. The embedding functions are type-dependent which means the embedding considers the source node-type. The final message value for each node is obtained by multiplying the weight and edge embedding value of its neighbors. Then, an MLP is used to obtain a value for each source and possible target node, which takes the final value of the source, target, and edge between those as input. Then, the output of the MLP is used to get the final probability of choosing the next node.

Major comment: 
The proposed algorithm looks interesting. Specifically, this problem can be modeled as multi-agent cooperative RL problem, and this paper suggests a model to handles it as a single RL problem. (For example, see paper [1] which suggests a multi-agent approach for a similar problem). However, the numerical results do not suggest a competitive algorithm yet and there are several baselines which obtain smaller objective in a smaller time, and yet it does not make sense to solve mTSP with a RL method. Note that this is not the case in VRP, since the current non-learning/non-commercial algorithms are not powerful in solving even medium-size problems with 50 nodes.

[1] Zhang, Ke, et al. "Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach." arXiv preprint arXiv:2002.05513 (2020).

+

minor comment:
The citation of mTSPLib is missing. 
review_title: It proposes an RL algorithm to solve mTSP problem.  

final_score: rating: 4: Ok but not good enough - rejection
review_content: The authors propose an RL framework, called ScheduleNet trained by clipped REINFORCE, for minmax multiple traveling salesman problem (minimax mTSP), which uses a clipping idea to stabilize learning process as PPO does. The authors empirically show the feasibility of the proposed framework.

- Unfortunately, the proposed method has poorer performance than existing works, in particular, OR-Tool. This decreases the merit significantly.

- In addition, it is hard to find contribution from proposing new RL method since the stabilizing effect of the clipped REINFORCE is shown in only limited environment (only minimax mTSP).

- Table 2 is not completed.

- The nature of "minimax" mTSP should be more clearly represented and exploited. Currently, the proposed RL framework seems to work for other formation of mTSP, and also it seems not to exploit the nature of minimax.

- In order for showing novelty of the proposed method, it might be useful to devise and investigate actor-critic methods sharing the main idea. In the submission, only footnote 1 simply mentions the hardness of learning value function.

- The behavior of ScheduleNet need to be studied further, e.g., when your algorithm works well, and not.
review_title: Insufficient performance and contribution

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary of the paper:
This paper proposes a deep reinforcement learning (DRL) approach for learning a solution strategy for the minimum-makespan multiple Traveling Salesman Problem (mTSP). The makespan mTSP is a challenging combinatorial optimization problem in which we are given the 2-dimensional locations of a set of customers that must be visited by a (much smaller) set of trucks. The trucks depart from the same depot, and must return to it after their tours. The minimum makespan version of mTSP asks for a set of such tours such that the length of the longest tour is minimized.

This work is part of a recent interest in using machine learning to design algorithms for hard discrete optimization problems. A number of such methods have been proposed for the standard TSP problem, but the minimum-makespan mTSP brings a number of challenges: the makespan is a sparse reward signal in RL terms, in that it is realized only after a full solution has been constructed (at the end of the episode); unlike the TSP, the mTSP has multiple trucks to be managed at every iteration of a sequential constructive algorithm.

The authors make two main contributions towards establishing a DRL approach to min-makespan mTSP:

1- They propose a specialized graph neural network architecture which combines known ingredients in a way that is suitable to the structure of the mTSP;

2- They modify the RL training algorithm to take into account the intricate discrete structure of the makespan objective, which stabilizes the training process.

Experimentally, the proposed ScheduleNet method is trained on a single set of random instances with a small number of customers and trucks, then tested on similar and larger random instances, as well as some benchmark mTSP instances from the literature. Compared to some other learned and non-learned algorithms, ScheduleNet seems to be competitive.    

Strengths:
1- Interesting engineering of the graph network model and of the RL training procedure to take into account mTSP and makespan structure;

2- Generalization from very tiny instances to much larger ones (though not too large in an absolute sense).

Weaknesses:
1- Experimental evaluation leaves many questions unanswered;

2- Motivation for tackling yet another variant of the TSP is not very strong, in that it is unclear that practitioners solving mTSP in practice would be interested in using the proposed method. No discussion of how the ideas presented here could extend to other variants of TSP or significantly improve performance on some class of instances that are of great interest to the community or an application domain. 

3- Submission seems to have been rushed, with missing citations and weird captions in a couple places.

Recommendation: Overall, I have to recommend a rejection, but I do think that the authors are on a good path towards a paper if they strengthen the motivation and experiments. I don't know if that will be possible within the ICLR rebuttal.

Questions to the authors:

1- Table 1: how many instances are considered for each (N, m) pair here? Please provide standard deviations for the values provided here, without which it's hard to tell how stable the reported average makespan is.

2- Table 1: Why was CPLEX not run on the MTSP Uniform instances as was done in Table 2? This way you can compute the exact approximation ratio.

3- Table 1: Are the results reported for Hu et al. copied from that paper? If so, are you using the exact same set of graphs? If not, a direct comparison such as that claimed in Table 1 is not possible.

4- Table 2: The caption is hard to parse. The following does not make sense: "CPLEX results are reported as the average of the upper and lower bound." Instead, you should report the best solution found by CPLEX (i.e., the best upper bound at termination).

5- Table 2: Please define SOM, ACO and EA, and cite the respective papers as well as any additional implementation details.

6- OR-Tools: You should tune the parameters of OR-Tools (e.g., https://developers.google.com/optimization/routing/routing_options) on the same training set of instances that you train your model on. The tuning can be performed using some kind of grid search or more sophisticated tuning tools such as SMAC (https://github.com/automl/SMAC3).

7- Running time results: There is no mention whatsoever of the running time of ScheduleNet (in training, but more importantly at test time), and how it compares to OR-Tools and the other heuristics of Table 1-2.

8- ScheduleNet hyperparameters: You list the values but no mention of if/how they were tuned.

9- Relation to VRP: mTSP is a special case of VRP in which there are no worker (truck) capacities. Have you considered comparing ScheduleNet to VRP learning approaches from the literature, such as Nazari et al. (which you cite)?

Minor:
- "In this study, we formulate (MinMax mTSP as a Markov" --> remove "("
- Section 3.1, "Transition": I find this paragraph hard to parse.
- "is equals to the makespan" --> "is equal to the makespan"
- "since the following operations only for the given time step" --> "since the following operations only apply to the given time step"
- "instances whose number m of tasks and the number N of workers are sampled" --> shouldn't this be the opposite?
- "benchmark problems in mTSPLib (cite)," --> please add the appropriate citation: https://profs.info.uaic.ro/~mtsplib/
- Appendix: "and produces and produces “type-aware”"
- Appendix: "The computation steps of equation 11, 12,and ??"
- Appendix: "hyperparameters of SchduleNet" --> "hyperparameters of ScheduleNet"
review_title: Good initial results, but not enough at this point.

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary
-------------
The paper proposes a reinforcement learning approach to solve the min-max multiple TSP, where there are multiple salesmen and the goal is to minimize the longest subtour while every city is visited by one salesman. The authors propose an architecture, ScheduleNet, that encodes a partial solution or state and outputs a policy, i.e. a probability distribution over the actions. They train the model using a variant of the REINFORCE algorithm. The approach is validated on randomly generated mTSP instances as well as the standard literature benchmark TSPlib.


Strong points
-------------------
1. The addressed problem, TSP with multiple salesmen is an important combinatorial problem that is more challenging than the standard TSP because of the multi-agent cooperation that it involves. It is true that although there is a lot of literature on learning-based approaches that solve the TSP, only a few very recent papers deal with the multiple agent setting
2. The MDP formulation with the notion of events is sound and clearly explained. It is more sophisticated than the standard MDPs used in the “one agent” setting
3. The type-aware embeddings are interesting here to differentiate the interactions between the different types of nodes.


Weak points
-----------------
4. The numerical experiments are not convincing me that the approach would be useful in practice  
5. To be informative, results in Table 1 should be the average over a number of random instances for each characteristic. Maybe it’s already the case but it is not mentioned. Moreover, the random instances should also follow different distributions to be varied and really helpful to evaluate the method.
6. Table 1 and 2: I found the reported gap (fraction of objectives) not so clear to get a precise sense of the performance. In Table 2, using the standard (approximate) optimiality gap would be better (obj_heuristic – obj_cplex)/obj_cplex. 
7. It would be informative to report CPLEX results for the randomly generated instances as well.
8. Although the TSP is a natural special case of mTSP, the performance on of the approach on randomly generated TSP instances (cf Table 3) is significantly poorer than that of other learned heuristics. It would be useful to report the results for TSPlib as well.
9. The authors claim that they propose a new approach for training “Clipped REINFORCE, a variant of clipped PPO without the learned value function”. It would be useful to give more explanations for this choice.
10. In equation (9), I believe there is a missing sum over \tau. This does not help in understanding 


Recommendation
-------------------------
I would vote for reject. In summary, the proposed approach is an adaptation of known techniques, to a specific interesting problem, that does not lead to a clear gain in performance.

Arguments for recommendation
---------------------------------------------
11. The MDP framework and type-aware GNNs are interesting and new in this context but not novel 
12. To me, the numerical experiments are very limited and do not demonstrate the added-value of this method, see weak points above


Questions to authors
-----------------------------
13. Sec 4.1: It is said that you consider the complete graph and that the edge features are the Euclidian distance which is symmetric. So what is the point of using a *directed* graph?
14. Sec 4.1: “v_i denotes the node corresponding entity i in mTSP problem”. It sounds like v_i is a node of the graph. But if at \tau a worker is in between two cities, what would be v_i?
15. Sec 4.1: what are the types exactly? You give an example “active-worker” but it would be useful to list them all.
16. Sec 4: There is a confusion between source and destination indices. “eij denotes the edge between between source node vi and destination node vj” but then for the edge embedding “the specific type kj of the source node vj” and “the message from the source node vj to the destination node vi”. Similarly, equation (2), it is confusing to use j as a source index.
17. Sec 4.2: the definition of Nk(i) = {vj |kj = k, ∀l ∈ N (i)} does not make sense. What is the correct one? Because the graph is complete, is N(i) different from the entire V? 
18. Sec 5: “\pi_b is the evaluation and baseline policy”. What baseline did you use?
19. Sec 5: equation 8, can you explain the choice of the exponent of gamma?
20. Sec 6:  “m ∼ U(2, 4) and N ∼ U(10, 20)”. Are m and N switched here? Otherwise there would be more workers than cities.
21. Table 2: what are SOM, ACO and EA? These baselines should be described (at least named) in the text.

Feedback to help improve the paper
--------------------------------------------------
22. “For the clarity of explanation, we will refer to salesman as a workers, and cities as a tasks.” I actually found it more confusing. Especially because task is standardly used to refer to the entire problem that the RL algorithm is addressing
23. “We define the set of m salesmen VT = {1, 2, ..., m}, and the set of N cities VC = {m+1, 2, ..., m+ N}” -> set of m salesmen *indexed by* VT = {1, 2, ..., m}, and the set of N cities *indexed by* VC = {m+1, 2, ..., m+ N}
24. “CPLEX results are reported as the average of the upper and lower bound”. It would make more sense to report the upper bound, i.e. the value of the best feasible solution found by the solver within the time limit.
25. To be able to better generalize to the TSP instances, why not include instances with N=1 during training.
review_title: An interesting RL framework for the mTSP problem with limited mild empirical results  

Meta-review: This paper proposes a deep reinforcement learning approach for solving minimax multiple TSP problem. Their main algorithmic contribution is to propose a specialized graph neural network to parameterize the policy and used a clipped idea to stabilize the training. Unfortunately, the reviewers remain to be unconvinced by the experiments after the rebuttal and the writing need to be significantly improved. Also, it would be worthwhile to study how the proposed method can generalize to other problems. 

Decision: Reject