ATTENTION, LEARN TO SOLVE ROUTING PROBLEMS!
The recently presented idea to learn heuristics for combinatorial optimization problems is promising as it can save costly development. However, to push this idea towards practical implementation, we need better models and better ways of training. We contribute in both directions: we propose a model based on attention layers with benefits over the Pointer Network and we show how to train this model using REINFORCE with a simple baseline based on a deterministic greedy rollout, which we find is more efficient than using a value function. We significantly improve over recent learned heuristics for the Travelling Salesman Problem (TSP), getting close to optimal results for problems up to 100 nodes. With the same hyperparameters, we learn strong heuristics for two variants of the Vehicle Routing Problem (VRP), the Orienteering Problem (OP) and (a stochastic variant of) the Prize Collecting TSP (PCTSP), outperforming a wide range of baselines and getting results close to highly optimized and specialized algorithms.
This paper proposes an alternative deep learning model for use in combinatorial optimization. The attention model is inspired by the Transformer architecture of Vaswani et al. (2017). Given a distribution over problem instances (e.g. TSP), the REINFORCE update is used to train the attention model. Interestingly, the baseline used in the REINFORCE update is based on greedy rollout using the current model. Experimentally, four different routing problems are considered. The authors show that the proposed method often outperforms some other learning-based methods and is competitive with existing (non-learned) heuristics.
Overall, this is a good piece of work. Next, I will touch on some strengths and weaknesses which I hope the authors can address/take into account. My main concern is the lack of comparison with Deudon et al. (2018).
Strengths:
- Writing: beautifully written and precise even with respect to tiny technical details; great job!
- Versatility: the experimental evaluation on four different routing problems with different kinds of objectives and constraints, different baseline heuristics, etc., is quite impressive (irrespective of the results). The fact that the proposed model can be easily adapted to different problems is encouraging, since many real-world operational problems may be different from textbook TSP/VRP, and hard to design algorithms for; a learned algorithm can greatly expedite the process. This versatility is shared with the model in Dai et al. (2017) which applied to different graph optimization problems.
- Choice of baseline: the use of the greedy policy is definitely the right thing to do here, as one wants to beat "simpler" baselines.
- Results: the proposed method performs very well and does not seem hard to tune, in that the same model hyperparameters work well across different problems.
Weaknesses:
- Comparison to Deudon et al. (2018): I believe the authors should do more work to compare against Deudon et al. (2018). This includes expanding the sentence in related work, describing the differences in more detail; perhaps a side-by-side graphical comparison of the two models in the appendix would help; reporting results from or running the code of that paper for the relevant problems (TSP?). This is crucial, since that paper also builds on the Transformer architecture, attention, etc. Its code is also online and seems to have been up for a while (https://github.com/MichelDeudon/encode-attend-navigate). There is quite some overlap, and the reader should be able to understand how the two models/papers differ.
- Intuition: One thing that is lacking here is some intuitive explanation of *why* this particular attention model is a reasonable choice for guiding a combinatorial algorithm. For instance, earlier work such as Pointer networks or S2V-DQN each addressed certain issues with other models of the time (e.g. capturing graph structure in S2V-DQN). If the choice of the model is purely performance-driven, that is completely fine, but then it makes sense to walk the reader through the process that got you to the final model. You do some of that in the ablation study in 5.2, for the baseline. Additionally, I am wondering about why this attention model is good for a combinatorial problem.
Questions/suggestions:
- Performance metric: if I understand correctly, Table 1 reports objective values. Could you additionally report optimality gaps compared to the best solution found *across* methods (including Gurobi, especially when it solves to optimality for the smaller problems/all of TSP)? Otherwise, it is very hard to interpret the differences in absolute objective values across methods.
- Baseline: could you use a non-learned baseline (e.g. 2-opt for the case of TSP) at the beginning of the training (then go to your learned but greedy baseline)? Might this give a stronger baseline at the beginning and accelerate training?