GOAL: A Generalist Combinatorial Optimization Agent Learner

Rebuttal to original review

We appreciate the reviewer for their time and feedback on our work. We address your concerns as follows: > Contributions can be over claimed. Authors claim that it is ``the first model that solves such a variety of CO problems.'' ... [1] and [2] already propose a multi-task solver ... We agree that the idea of multi-task training is not new, what we claim as new is the ability of our model to solve a wide variety of CO problems. Indeed the mentioned references tackle a limited set of problems (3 euclidian routing problems and the KP for [1] (now discussed in Sec 2) and several variants of euclidian routing problems for [2] as well as other references cited in Sec 2). In contrast, our model solves 16 problems spanning (euclidian and non-euclidian) routing, scheduling, packing and graph problems. These problems have diverse structures, compared to the euclidian routing problems, which led previous works to consider different architectures (like [3, 4]). It is in this sense that we claim that, to our knowledge, our approach is the first to tackle such a variety of tasks and structures with a single (backbone) model. [3] Kwon et al. Matrix Encoding Networks for Neural Combinatorial Optimization, NeurIPS 2021 [4] Pirnay et al. Self-Improvement for Neural Combinatorial Optimization: Sample Without Replacement, but Improvement, Transactions on Machine Learning Research (06/2024) > The running efficiency is not competent compared with other methods, as shown by Table 1 and 2. Our method, like all heuristics, provides a trade-off between solution quality and running time. It outperforms most specialized NCO baselines in terms of quality, at the cost of longer running time. In effect, our model is more costly because it is more general, e.g. for CVRP our model takes as input any distance matrix while all the baselines can only take as input the node coordinates. Still in Table 1, we can see that our running times are often only a few seconds and at most 15 seconds, and therefore remain comparable with the baselines. > Significant gap between GOAL and the optimal solutions as shown in Table 1 and 2. In Table 1, the gaps between the multi-task-GOAL solutions and the specialized oracle solvers are less than 1% for half the problems and at most of 4.13\%, while GOAL is much faster than the oracles in 7 out of 8 cases (knowing that the oracles run on CPUs and GOAL runs on GPUs). Again, this is about the trade-off between solution quality and running time. While other NCO baselines have similar or larger gaps, we believe it is unrealistic to expect a generalist model to perform on-par with specialized solvers. Similarly in Table 2, we can observe a good quality/time trade-off compared to the baselines as well as the oracle solvers. > About usefulness for solving real-world problems In addition to the speed and the ability to leverage GPUs, we believe the main advantage of GOAL in real-world settings is that it can be efficiently fine-tuned to new problems, for which obtaining effective specialized solvers, working at the desired scale, may be too costly. > Lack of explanations of why the method generalizes to instances of a larger scale better than the baselines The main difference between our model and the baselines reported in Table 2 (except BQ-NCO) is the use of the BQ-MDPs. And it was shown in the BQ-NCO paper that BQ-MDPs lead to a better generalization. The provided intuition is that the states along a BQ-MDP trajectory are instances which strictly decrease in size at each step, so the model sees a diversity of sizes during pre-training and adapts more easily to new sizes. While in the baselines other than BQ-NCO, the instance component of the state remains constant along a trajectory, hence the model sees less diverse sizes during training. > Why MatNet cannot be run on ATSP500 or larger, but GOAL can? MatNet code is publicly available and we observe that it crashes on ATSP500 and larger. Analyzing their implementation, we found that MatNet cannot solve problems larger than its embedding size (256) due to the addition of random identifiers directly into the embedding space. The precise reasons for this design choice would be best clarified by MatNet developers. > Why GOAL outperforms MatNet, which parts of GOAL contribute to the improvement? Essentially, MatNet mixes the edge information directly with the vanilla attention score which is the result of the scalar product of two node embeddings. Thus, there is no direct interaction between the edge embeddings and the factors of that product (the node embeddings). Our mixed attention, on the other hand, precisely allows that interaction, since it operates on the factors of the scalar product, as captured by Eq (1b) vs (1a). This may explain the better performance of our mixed attention, as it allows more direct information flow between edges and nodes.

Thanks for your response

Authors' rebuttal well addressed part of my concerns on the experiments as well as my previous misunderstandings on the techniques. So I decide to raise the score to 5. However, some of my core concerns have not been adequately addressed, and it seems unlikely that these issues will be resolved satisfactorily in the near term. Consequently, I continue to hold a negative view of this article. Undoubtedly, this paper presents promising experimental results. My primary concerns, however, revolve around two key issues: - Theoretical Supports. For instance, there is a lack of compelling theory or analysis to motivate the random assignment of values between 0 and 1 as node features. Furthermore, the capabilities and limitations of such methods is still unknown, including the theoretical boundaries of how well the current framework can generalize to problems of different scales and which types of problems it may not work for. - Practical Applicapability. Although this work holds the potential to be used as a pre-trained model to tackle various problems in the future, its current version is still quite preliminary.

Rebuttal

We are very grateful for the reviewer's precise and constructive feedback. We answer each concern as follows: > The ablation study seems to combine both changes at once, so the individual contribution of either modification is not demonstrated. The first modification is actually unavoidable. Let's say we have $M$ machines with $m$ features and $J$ jobs with $j$ features. Consider the two options: (i) we concatenate the features of the different types, using zero padding when necessary, then go through the input adapter of size $(m{+}j){\times}\ell$, then the codebook ($\ell{\times}D$) and ending up with an embedding vector of size $(M{+}J) {\times} D$, that we can split into the machines embedding $M{\times}D$ and the jobs embedding $J{\times}D$. (ii) use type-specific adapters of size $m{\times}\ell$ and $j{\times}\ell$, then apply the codebook and end up again with the machines embedding $M {\times} D$ and the jobs embedding $J{\times}D$. Because of the linearity of the adapters and the codebook, options (i) and (ii) are strictly equivalent. That is why our ablation only evaluates the advantage of the multi-type versus single-type architecture (the second change below). We added this clarification in the ablation section. > Why the second change is helpful. Is this superior to applying the single-type backbone to embeddings produced by heterogeneous adaptors? The ablation study focuses on testing the impact of the second change; i.e. comparing using the single-type model on the $(M{+}J){\times}D$ embeddings versus the multi-type model on the $M{\times}D$ and $J{\times}D$ embeddings. It shows that the later leads to a superior performance. One reason may be that in the multi-type attention blocks, the softmax operation which defines the attention coefficient scopes only over nodes of the same type. This means that the transformation can spread attention weight independently on jobs and on machines, instead of having to spread it on both jointly as in the single-type model, leading to a rather counter-intuitive competition between types for attention. Furthermore, the multi-type model allows to define smaller blocks, that can be adapted to the "structure" of the type: for example for the UMSP, as shown in Figure 7 (a), the type-specific self-attention blocks are vanilla attention modules, leveraging the fact that there are no edges between the jobs (resp. machines). Finally, the multi-type model offers more flexibility for fine-tuning: indeed, although it is crucial that the different blocks share the same parameters at training (to remain task agnostic), this constraint can be relaxed at fine-tuning time to better fit the specific task at hand. > How exactly does the proposed multi-type architecture improve performance? See above. > Illustration of the multi-type mechanism in Figure 1 a bit misleading... Thank you very much for pointing this out, the figure actually corresponds to a previous implementation, which we found to be slightly slower. We have updated it in the manuscript and provide additional illustrations in Figure 7 (Appendix D). In any case, because we stack several layers, we observed that what is important is not so much how the attention blocks are connected in each layer, but the fact that they all share the same parameters (within a layer), so that the model remains generic. > Multi-task learning techniques (GradNorm, etc...) We experimented with advanced multitask training approaches, including meta-learning (a Reptile-inspired) methods and gradient aggregation techniques similar to GradNorm. However, these approaches did not outperform our standard multitask training. The primary challenge lies in the computational expense of training the GOAL model, which makes parameter tuning for these pipelines particularly costly. We plan to investigate these methods further, as this represents an important direction for future research. > Backbone freeze when finetuning We have updated Fig. 5 with the performance when the backbone is frozen. It concerns the supervised fine-tuning mode, but the results are essentially the same in the unsupervised case (Fig. 2). As one may expect, freezing the backbone yields a degraded performance. Freezing the backbone (or limiting its finetuning to internal adapters as in LoRa) is common practice and makes sense when dealing with very large models such as LLMs. But it is to be noted that our GOAL backbone is relatively small, so the computational impact of fine-tuning it in full is almost negligible. That is also why we are not using adapters (e.g. LoRa) inside the backbone.

Rebuttal

We thank the reviewer for their insightful and constructive feedback. We address your concerns as follows: > Implementation details of the "codebook" The codebook is a (low-rank) matrix of size $\ell{\times}D$), shared by all tasks, and mapping the output of the input adapter (of dimension $N{\times}\ell$) to the input of the backbone ($N{\times}D$). We added more details at the end of Sec 3.4. The term codebook is usually reserved for a discrete set of representations (here $\ell$ embedding vectors of size $D$), and we abuse it slightly by allowing each input adapter to represent its task features by linear combinations of the codebook vectors rather than single ones. > Definitions of BQ-MDP and tail-recursive are needed in the main text We added a couple of sentences at the end of Sec 3.1 to highlight the main difference between the BQ-MDPs and those more commonly used in other NCO frameworks, as well as more information on tail recursivity. > Parameter size of GOAL and how does it compare to other peer methods We added the following precision in Appendix A. The size of our model is in the same range as peer models. The GOAL backbone has 2.1M parameters and adapters are very light, with only a few thousand parameters per task. For comparison, RouteFinder+POMO has 1.3M, MVMoE has 3.7M (the same model is used in RouteFinder+MVMoE), and RouteFinder+Transformer_Encoder 1.7M. > How to implement the post-processing step (such as MCTS, 2-opt search) Post-hoc improvements can be applied exactly as in similar constructive NCO works (e.g. beam search in AM [2] and BQ-NCO [3], MCTS in [4]). Alternatively, after constructing the greedy solution, one can apply 2-opt or any other improvement heuristic. [2] Kool et al, Attention, Learn to Solve Routing Problems! ICLR 2019 [3] Drakulic et al, BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization, Neurips 2023 [4] Xing et al, A Graph Neural Network Assisted Monte Carlo Tree Search Approach to Traveling Salesman Problem, IEEE Access 2020 > How will different node and edge definitions affect the solver's performance? Some problems can indeed be represented equivalently with various node and/or edge features. For example, in the Euclidean routing problems, location information can be represented either as node features (using node coordinates) or as edge features (using a distance matrix). We chose the latter approach for all routing problems because it is more general. When GOAL is used for a single routing task like TSP, performance is slightly superior when using distance (injected with GOAL's mixed attention) rather than coordinates (using vanilla attention). Table 1 reports a .3% opt gap on TSP100 for the former while the BQ-NCO paper reports .35% for the latter (single-task GOAL boils down to BQ-NCO when coordinates are used since edge information is void in that case). > Scaling to larger problems Generalization results on larger instances, with up to 1000 nodes, are available in Table 2 in the Appendix. Originally we provided the generalization results for 3 problems, we added 3 more in the updated manuscript. Note that the attention bottleneck can be mitigated by considering task-specific heuristics to prefilter the input graph (see Sec 3.4), allowing generalization to even larger sizes on some tasks.

Rebuttal

We thank the reviewer for the insightful feedback and address their concerns and questions as follows: > Description of dimension transformations and the learning process To complement the dimensions that are explicit in Fig 1, we added the following at the end of Sec 3.4: "... node (resp. edge) features are first mapped into a low dimension $\ell{\ll}D$ (resp. $\bar{\ell}{\ll}\bar{D}$), through a task-specific linear projection (the input adapter proper), forcing the representations to share dimensions across tasks. Then this "small" representation is plunged into a "large" $D$- (resp. $\bar{D}$)-dimensional embedding, through a common linear projection ..." Besides, we added a new section "3.6 Training Procedure" to detail the learning process. > Experiments with larger problem sizes In Table 1, we provide the results on instances with 100 nodes, coming from the same distribution as the training instances. Generalization results on larger instances, with up to 1000 nodes, are available in Table 2, presented in the Appendix for space reasons. Originally we provided the generalization results for 3 problems, we added 3 more in the updated manuscript. > Lack of theoretical analysis We indeed do not provide a theoretical analysis but demonstrate the effectiveness of our approach through extensive experiments. In addition to the performance on the training tasks (Tables 1 and 2) and fine-tuning on new tasks (Fig 2), we empirically demonstrate the synergistic effect of our proposed multi-task pre-training for effective fine-tuning on new tasks in Fig 4. We want to point out that similar works that aimed at foundation models in other domains, such as GATO [1], do not provide a theoretical analysis either. [1] Reed et al., A Generalist Agent, Transactions on Machine Learning Research (11/2022) > Lack of (NCO) baselines for certain problems in Table 1 We included extra baselines for CVRPTW and JSSP in Table 1. Regarding other problems, we are not aware of more NCO baselines, and in particular we do not know any for the USMP. > Existence of common knowledge between different CO problems We implicitly conjecture but do not prove the existence of such a common knowledge. Intuitively, some CO problems share common underlying concepts/skills like shortest paths for routing problems, and therefore we may think pre-training on a set of problems may enable the model to learn such skills which will then be helpful to effectively adapt to a new problem. The experimental results tend to confirm this intuition. Indeed, if there was no common knowledge acquired during the training, finetuning the pre-trained model on a new task would be equivalent to learning it from scratch, which is not what we observe (Fig 2).