Efficient Training of Multi-task Combinarotial Neural Solver with Multi-armed Bandits

We conduct a comparison under the same number of training epochs by training our method on 12 tasks mentioned before for 1000 epochs in total, and comparing them with corresponding Single Task Learning (STL) neural solvers that are trained for 1000 epochs on each of their respective tasks. This is, by no means, a fair comparison, as our method dynamically chooses a task to train for 1000 epochs, resulting in a much smaller sample size than each task when using STL. Despite this, we choose this comparison as an intuitive way to demonstrate the superior generalization ability of our method under such extreme conditions. We present the results in Figure 2. Compared to individual tasks, our method's comparative performance is to be expected due to the vast differences in sample size. In most cases, our method's performance is equivalent to that of using 100 to 200 epochs of STL. However, STL can only obtain one model in this context and lacks the ability to handle different types of COPs or to generalize well when presented with the same type of COP but with varying problem scales. As a result, our method demonstrates unparalleled superiority in three ways: (1) when considering the average performance on all problem scales for each type of COP, our method obtains the best results in CVRP, OP, and KP, and is equivalent to the results achieved by training TSP for about 500 epochs. This showcases our method's excellent generalization ability for problem scales; (2) Our method can handle various types of COPs under the same number of training epochs, which is impossible for STL due to the existence of task-specific modules; (3) Our method's training time is strictly shorter than the longest time-consuming task.