GOAL: A Generalist Combinatorial Optimization Agent Learner
Authors: Darko Drakulic
Sofia Michel
Jean-Marc Andreoli
Venue: ICLR 2025 Poster (2025)
Keywords: neural combinatorial optimization
generalist models
transfer learning
fine tuning
Primary area: foundation or frontier models, including LLMs
TL;DR: We propose a generalist model capable of efficiently solving multiple COPs and which can be fine-tuned to solve new COPs.

Abstract: Machine Learning-based heuristics have recently shown impressive performance in solving a variety of hard combinatorial optimization problems (COPs). However they generally rely on a separate neural model, specialized and trained for each single problem. Any variation of a problem requires adjustment of its model and re-training from scratch. In this paper, we propose GOAL (for Generalist combinatorial Optimization Agent Learner), a generalist model capable of efficiently solving multiple COPs and which can be fine-tuned to solve new COPs. GOAL consists of a single backbone plus light-weight problem-specific adapters for input and output processing. The backbone is based on a new form of mixed-attention blocks which allows to handle problems defined on graphs with arbitrary combinations of node, edge and instance-level features. Additionally, problems which involve heterogeneous types of nodes or edges are handled through a novel multi-type transformer architecture, where the attention blocks are duplicated to attend the meaningful combinations of types while relying on the same shared parameters. We train GOAL on a set of routing, scheduling and classic graph problems and show that it is only slightly inferior to the specialized baselines while being the first multi-task model that solves a wide range of COPs. Finally we showcase the strong transfer learning capacity of GOAL by fine-tuning it on several new problems. Our code is available at https://github.com/naver/goal-co .

Published as a conference paper at ICLR 2025
GOAL: A GENERALIST COMBINATORIAL OPTIMIZA- TION AGENT LEARNER
Darko Drakulić, Sofia Michel & Jean-Mare Andreoli NAVER LABS Europe, France fi Firstname. 1 nattname@aaee 1 abs. .com
ABSTRACT
Machine Learning-based heuristics have recently shown impressive performance in solving variety of hard combinatorial optimization problems (COPs). How- ever they generally rely on a separate neural model, specialized and trained for each single problem. Any variation of problem requires adjustment of its model and re-training from scratch. In this paper, we propose GOAL (for Generalist com- binatorial Optimization Agent Learner), generalist model capable of efficiently solving multiple COPs and which can be fine-tuned to solve new COPs, GOAL consists of a single backbone plus light- problem-specifie adapters for input and output processing. The backbone is based on a new form of mixed-attentinn blocks which allows handle problems defined on graphs with arbitrary combi- nations of node. edge and instance-level features. Additionally, problems which involve heterogeneous types of nodes or edges are handled through novel multi- type transformer architecture, where the attention blocks are duplicated to attend the meaningful combinations of types while relying on the same shared parame- ters. We train GOAL on set of routing, scheduling and classic graph problems and show that it is only slightly inferior to the specialized baselines while being the first multi-task model that solves wide range of COPs. Finally we showcase the strong transfer learning capacity of GOAL by fine-tuning it on several new problems. Our code is available at this url
INTRODUCTION
Combinatorial Optimization (CO) problems are extensively studied in the Operations Research com- munity, because they are both challenging in terms of theoretical complexity and central in many applications such transportation, logistics and finance. Traditional CO methods include exact solvers, typically based on integer programming (Korte & Vygen] 2018), and approximation algo- rithms [Vazirani] 2003) which provide optimality or approximation guarantees, respectively, but do not scale; and heuristic algorithms (Boussaid et al.) (203)) which produce good-quality solutions faster but without guarantees. Effective heuristics heavily rely on expert knowledge and are gener- ally problem-specific. A more recent and promising family of methods for CO is based on Machine Learning, either to learn the in an end-to-end fashion (Bengio et al. [021]] Cappart al. 2021). In partieular constructive neural heuristics have been successful at sol solving variety of CO problems, including routing (Bello et al. 2017 Nazari et al. 2018: Kool al. 20188] Kwon et al. 2020), scheduling (Zhang al., 2020 Kwon et al. 2021) and graph problems (Khalil et al. 2017 Qiu et al. 2022). However, in most cases, a separate model is specialized and trained for each problem. and sometimes even for each distribution of instances within a problem, especially for varying instance sizes. While much ef- fort has been devoted improving the generalization different instance distributions (Manchanda et al. 2022. Zhou et al.] 2023) [Son et al.) 2023) Drakulic et al.) 2023), generalization to different problems is less studied. Indeed, although there are strong neural heuristics for many CO problems, any variation of these problems requires adjustment of their model and re-training from scratch. While it is true that some cobblem-specifii model tailoring may be required, since the structure of problem instances and solutions are very diverse, many problems are related and it would be in- teresting to exploit their commonalities. In this paper, we seek to answer the following question: Can we design and train single generalist model that it can be efficiently adapted to solve
of classic CO solvers, or to directly learn heuristics
Qiu

---

Published as a conference paper at ICLR 2025
variety of CO problems? The idea of pretraining unified model some pretext task that it can be efficiently fine-tuned to several downstream tasks has been extremely successful in the language and vision domains (Devlin et al.) 2019 Brown et al. 2020: Radford et al. 2021). In these domains, a self-supervised pretraining task exploits the intrinsic structure and regularities of images and text to learn generie representations. In contrast, in CO, while most problem instances can be modeled as graphs, there is no generic regularity to leverage by a pretext task. Graphs, unlike images or text contain little redundancy or intrinsic semantics.
In this paper, we propose a new model, named GOAL (for Generalist combinatorial Optimization Agent Learner), which consists of a single backbone and weigt- cooblem-specinne adapters for input and output processing. To handle the large discrepancy between CO problems, we propose three complementary strategies. First, to ensure learning related representations for different CO problems, we propose to use problem-specific projection of the input instance features to a small fixed-size representation, which then projected into the main embedding space using a shared codebook. Second, to handle problems defined on graphs with arbitrary combinations of node, edge and instance-level features, we design a new form of mixed-attention blocks for the backbone, injecting edge information at the core of each attention block. Finally, introduce novel multi- type transformer architecture to deal with problems which involve heterogeneous types of nodes or edges (typically represented as multipartite graphs). The idea is to duplicate the backbone's mixed-attention blocks in order to attend each meaningful combination of types while relying on the same fixed set of shared parameters. In principle. GOAL able to handle any CO problem whose instances can be represented as graph and where feasible solutions can be constructed iteratively, as a sequence of node selections. We find that this pattern is generic enough cover wide range of problems. We train GOAL in a multi-task setting, by imitation of expert trajectories of eight classic CO problems, spanning multiple domains: Routing problems: the Asymmetric Traveling Salesman Problem, the Capacitated Vehicle Routing Problem with or without Time Windows, the Orienteering Problem: ; Scheduling problems: the Job Shop Scheduling Problem and the Unrelated Machine Scheduling Problem; Packing problems: the Knapsack Problem; and Graph problems: the Minimum Vertex Covering Problem. The expert trajectories are based on good-qualla solutions, easily generated by traditional problem-specific solvers for instances of medium size (generally 100 nodes).
Experimentally we first show that GOAL performs very well on all the training tasks, making it the first model that solves such a variety of CO problems. Second, we consider eight new problems and demonstrate that GOAL can be fine-tuned reach a good performance, either in few minutes using few-shot imitation learning or in a couple of hours without supervision. In both cases, the fine-tuning takes a fraction of the time and data needed to train a model from scratch. We further provide an ablation study to evaluate the effectiveness of a shared codebook, multi-type transformer architecture and mixed-attention blocks. Notably the GOAL architecture gives state-of-the-arr results on out of our 8 training tasks when used as single-task model. In summary, our contributions are the following:
We introduce GOAL: a generic and flexible model for end-to-end combinatorial optimiza- tion. Two key ingredients of GOAL are the simple yet effective form of mixed-attention blocks which enables handling problems represented by graphs with any combination of node-, edge- and instance-level features and its multi-type transformer architecture which allows to seamlessly tackle problems with multipartite graph structures.
We demonstrate that it is possible to learn a single backbone model to effectively solve a variety of CO tasks, spanning routing, scheduling, packing and graph problems.
We showcase the potential of such multi-task pretrained model to be efficiently adapted to handle varied new CO tasks, with or without supervision. We believe this is a key step toward foundation model for CO.
2 RELATED WORKS
End-to-end heuristic learning for CO Our work falls into the category of end-to-end constructive
heuristics for combinatorial optimization. Constructive neural heuristics have been successfully
applicd to a wide range of COPs, including many variants of routing problems (Kool et al.) 2018
Xin et al. 2021 Kim et al. 2022 Kool et al. 2022 Fu et al. 2021 Sun & Yang 2023), scheduling
2

---

Published as a conference paper at ICLR 2025
problems Zhang et al. 2020 K wwon et al. 2021), as well as classic COPs such as the Knapsack Problem (won et al. 2020) and the Maximum Independent Set (Khalil et al. 2017: Sun & Yang.
2023). Another successful category of neural CO methods are improvement heuristics, which focus on iteratively enhancing a given complete solution, typically by using a neural network to guide the
selection of local search operators (Chen & Tian 2019 [Hottung& & Tiemey 2020; Ma et al. [
Wu et al. 2022). The seminal work Khalil et al. (2017) introduces graph embeddings which do work for a variety of CO problems but with limited performance. Current state-of-the-ar models are tailored for certain problem structures (e.g. euclidian routing problems, where nodes are represented by their coordinates plus some extra node or graph features such as demand or vehicle capacity), ,, and successfully handled by transformer-base
architectures (Kool et al., 2018). For non-euclidian routing problems, Kwon et al. (202T) and Drakulic et al. (2023) propose adapted architectures to deal with the distance matrix, but they are specialized for such problems and do not apply to those with node-only features. In GOAL, we propose a novel sixee-attention modules which can ficxibly deal with both node and edge features, incurring no overhead when one or the other is missing.
Generalization of neural heuristics While the first seminal models for neural CO had dramatic drop performance when tested on out-of-training distribution instances (Joshi et al. 2022 Man-
chanda et al.] 2022), several recent approaches show greatly improved generalization performance,
especially to larger instances (Fu et al.) 2021 Li et al.,
2021
I Son et al. 2023 Pan et al. 2023). to
distribution shifts of other instance parameters (Bi et al. 20022, , or both (Manchanda et al. 2022 Bi
et 2022 Zhou et al. 2023 Drakulic et al. 2023). Concurrently with our work, some papers have started explore cross-problem generalization for the family of routing problems. Specifically, (Lin et al. 2024) propose to pretrain the AM model (Kool et al. 2018) on the TSP and to fine-tune either the entire model some light-weigh modules on the Price Collecting TSP and OP. Addi- tionally, Zhou et al. (2024); Liu et al. (2024); Berto et al. (2024) explore generalization to different variants of the CVRP. They build on the idea of zero-shot compositionality (Ruis al., 2021) by training a model on CVRPs with some combinations of constraints from predefined set (e.g. time windows and duration limit constraints) and show that the model generalizes to some unseen com- binations of the same constraints. [Wang& & Yu (023) propose bandit based approach to alternate between problems during training. so as to focus on those which have the best return. Although these approaches tackle multiple problems, it is important to note that the considered Euclidian routing problems remain very similar in structure and indeed many of those problems were solved by the seminal Attention Model of (Kool et al. 2018) with little adaptations of its base model. Our paper goes further and considers multi-task training and transfer learning of a new model on a variety of COPs with different structures.
Multi-task training for sequential decision making Multi-task (pre-)training has recently shown promising results in related fields. For processor capable of learning to execute variety of algorithms, such sorting and searching. The paper focuses only on polynomial problems and learns to imitate the execution of classical algorithms. In contrast, we address NP-hard problems and learn by imitation of the solution provided by (potentially exponential) specialized solvers. Recent approaches in control rely on sequence modeling of expert trajectories from multiple tasks (Stooke al., 2021] Sun et al., 2023). Although they treat various tasks, with potentially diverse state and action spaces. these works still consider image observations and exploit this common structure. [Reed et al. (022) propose GATO, general- purpose agent obtained by training a large transformer- based model on hundreds of tasks spanning vision, language and control. It demonstrates the potential of a single network (albeit with 1.2B parameters) to effectively tackle wide variety of tasks.
et al. (2022) proposed graph neural network
MULTI-TASK LEARNING FOR COMBINATORIAL OPTIMIZATION
3.1 CONSTRUCTIVE CO PROBLEM SOLVING
We assume that a CO problem instance is given by pair of a finite, non-empty set X of feasi- ble solutions, and a real-valued objective function of whose domain contains X. Solving the in- stance consists in finding an optimal solution, i.e. an element of arg mingex fz). Constructive approaches assume that ff is defined not only over X but over a set of partial solutions. which in- cludes X and is amenable to step-wise construction procedure where each partial solution can be
3

---

Published as a conference paper at ICLR 2025
construction step
macked Softmax
construcion seep
Ourput adapter
Qutput adaptor
NxD
toyers
X.L. Layers
norm
Incm
backbone
Feed Forward
Tam
soltmax
MMA
MMA
MIKA
MMA
NxNxI
edges
nodes
71
edges
codebook
NoN
No!
codebook
Input adopter
Inpur adlaporr
NXN
instance
instancee
Left: Architecture of GOAL for single-type problems; the green components are task- specific, while the others belong to the backbone. The codebook is a shared fx D (resp. εx D) matrix (with &<Dİ<< applied to the node (resp. edge) representations produced by the input adapters. Right: Architecture of GOAL for multi-type problems (with here node types T1,T2); it uses multiple mixed attention blocks ("MMA"), some in self- and some in cross-attention mode, but they all share the same parameters (per layer); so do the two Feed Forward blocks ("FF"). For the edges, all the type combinations are shown (here T11,T12,T21,T22 meaning task are simply onitted. The same set of parameters is used for the two architectures.
Figure 1:
but those which have no
obtained by a sequence of construction steps. Thus, solving the problem instance be formulated as sequential decision procedure which iteratively selects the construction steps as to reach not only feasible but an optimal solution. That turn can be modeled as a Markov Decision Problem (MDP) associated with the problem. In this paper, we use the BQ-MDPs introduced by DDakulic al. (023) which are defined for "tail-recursive" problems, i.e. the widespread class of problems that are solvable by dynamic programming (Bertsekas) 2019). In BQ-MDPs, the actions are the con- struction steps, typically the selection
node, while the states are simply instances. This differs from many peer NCO models where each state is pair of instance and partial solution. The tail recursion property precisely ensures that the two alternatives lead to "bisimilar" MDPs, which have the same optimal policies. shown in Drakulic et al. (2023), but the BQ-MDPs' states more efficiently capture the relevant information to determine these policies.
3.2 MULTI-TASA CO PROBLEMS
Now, given class T of tail-recursive CO problems called tasks, let Ω2 for each task fET denote the parametric space used to represent its instances. Consider the new (multi-task) CO problem whose instances are represented in the disjoint union U.ET Ω2 consisting of pairs (t, w/ of a task identifier tET and point wES, 2 in its corresponding parameter space. It is easy to show that the multi-task problem is tail-recursive whenever each of its components is. And its BQ-MDP is then simply the disjoint union of the BQ-MDPs of its components.
In this paper. we study alternatives for the multi-task policy space, beyond the (trivial) Cartesian product of the policy spaces of the individual tasks, where no parameter shared between the different tasks. The underlying assumption is that if the tasks are sufficiently similar, learning one task may elicit implicit skills useful to other tasks, which are then leveraged by parameter sharing. In the extreme, some tasks may require little training data and/or just few shot fine-tuning to obtain acceptable performance, leveraging their similarity to more thoroughly trained tasks. Since each task has its own parametric space used to represent its instances, some part of any multi-task policy has to be task specific, and trained by processing at least few instances of each task: pure zero-shot generalization not possible. The situation is close multi-lingual Natural Language Processing.
4

---

Published as a conference paper at ICLR 2025
where the vocabulary of each language needs to be seen at least once at training or fine-tuning And we borrow the solution used in that context, namely adapters (Bapna & Firat 2019).
3.3 TASK REPRESENTATION
To leverage operational similarity between tasks, need them to have least representational similarity. Thus, we assume that each instance of size of a task (CO problem) is represented by a of N abstract "nodes", together with features which be attached at node, edge (node pair) or instance level. Instance features can be replicated and appended to the features of each node, hence can be ignored without loss of generality. Since the construction steps (actions) are returned by the task-specific output adapters (Sec (Sec there are no restrictions on their format. For simplicity and to cover the problems used in our experiments, we assume in the sequel that each construction step consists of the selection of a node, possibly with an option among fixed number K of options (dependent on the task: in most eases, K=1 and the action simply selects node).
Hence, the GOAL model takes three inputs 1, I. where is a task identifier, and (x, &)E is parameter representing instance of task t, where NxF- (resp. NER-xXxx. represents the feature vectors of dimension Fę of the N nodes (resp. Fg of the Nx edges). While some tasks may have edge feature (F)=0), we always assume that at least which distinguishes the nodes by randomly assigned value between 0 and 1, similar to the random features used in Graph Neural Networks (Sato al., 2021), so we always have F,21. Both F. and Fe, as well as the meaning of the corresponding features, depend on task 1. The output of the model is a matrix y-R ge representing the score of each candidate action, i.c. the pair of node and an option for selection. As usual, it is passed to a softmax (over the whole matrix) to obtain probability distribution. Wherever appropriate, task desk-dependent masking can be used to ensure that probabilities are null for the actions disallowed by task.
node feature exists,
3.4 ARCHITECTURE OF THE MODEL
The architecture of our model generalizes that of BQ-NCO (Drakulic et al. 2023), and is described in Fig. left. It essentially consists of a sequence of layers whose parameters are shared by all the tasks (backbone) together with task-specific adapter modules at the input and output of the mode[" []] The input-output adapter modules for task are specific to the dimensions Ft, Ft, K, and the meaning of the corresponding features. No positional encoding is used: all relational information is assumed to be captured by E. The layers themselves, shared embedding dimensions D, D. They are self-attention transformer layers (Vaswani er al., 2017) where vanilla attention is replaced by multi-head mixed attention, similar in intent (Kwon) et al. 2021 Henderson et al. 2023) but with different design.
the other hand, only aware of the
Our mixed attention block, the general case where M nodes attend on N nodes (M=N only in self-attention), is an instance of generalized attention (Andreoli] 2019). A generalized attention mechanism takes the following inputs: node representations as vectors for N queries, . keys, and M values, with an optional M x log-bing aig-binary mask M. In each head h, each query, key, value vector is first projected into a common space of dimension d, yielding for each n=1:NN and m=1:M, vectors (of dimension d):
Q!a² Qn (h))) Q
k((h) m
= K w(() (h)
( m
V W
Then the key and query vectors are used to compute an M x score matrix S, which is transformed into an attention matrix (by adding the mask and applying softmax) multiplied by the reprojected value vectors to produce the output representation r of the N input query nodes as a matrix with N rows:
softmaxcu +M) w (N)T
attention matrix
Attention mechanisms then differ the way they compute the score matrix:
(vanilla attention) S(h) = { k<(h) Q(h) )
(1a)
(our mixed attention) S(h)) (((h) + +((h)) Q(1)+Q+
(Ib)
Addatters can also he introduced within layers, but this paper considers only input-output adapters.
5

---

Published as a conference paper at ICLR 2025
In vanilla attention, the scores are obtained by simple scalar product of the key and query vectors (equation Iap. Our mixed attention mechanism takes as additional input MxN "edge" vectors, projected twice into the common space of dimension d, once key and once as query, resulting in vectors (of dimension d):
2nhh Emn W (()
K = Emn W (b)
The score matrix is still obtained as scalar product of a key and query vector, but now, each of them is the sum of a node component and an edge component (equation Ib). Our mixed attention allows to incorporate arbitrary relational information (edge features) into the core of the attention mechanism. It differs from positional encoding, which attempts to instill a priori the edge informa- tion (limited sequential ordering) into the node representations.
In the GOAL backbone, all the node (resp. edge) inputs to the attention blocks are of dimension D (resp. D). and they are all projected into a common space of dimension d equal D divided by the number of heads. No masking is used in the backbone. One well-known limitation of this model its quadratic complexity, the attention matrices being of size N², In practice though, for many tasks, a simple, task-specific heuristic can deal with that problem by pre- pre-fittriing the set of nodes to present to the model (usually much fewer than N). Whenever available, we use such heuristics.
Input and output adapters are linear projections, from the task-specific instance features to the back- bone's input embeddings and from the backbone's output embeddings to the task tasc-specific action space. However, when the embedding dimension is large and the number of training tasks is small, there is a risk that the embeddings produced by each task end up occupying complementary sub- spaces of the embedding space throughout the layers, which would defeat the purpose of effectively sharing parameters across tasks. To prevent this, we simply force the input linear projection to be low rank. Thus, node (resp. edge) features are first mapped into a low dimension &< (resp- (<D), through a task-specific linear projection (the input adapter proper), forcing the representa- tions to share dimensions across tasks. Then this "small" representation is plunged into a "large" D- (resp. didminnnio embedding, through a common linear projection, called a codebook, shared by all the tasks (see Fig. [lett)
3.5 MULTI-TYPE TRANSFORMER ARCHITECTURE
Many tasks (CO problems) involve different types of nodes. For example, scheduling problems often involve "operation" and "machine" nodes. For GOAL, one solution is to simply treat them all indiscriminately in the backbone. The adapters, being problem specific, are of course free to treat them differently according to their types. This is sometimes unsatisfactory though, since forces the adapter to provide uniform embeddings for all the nodes and edges, though they are often heterogeneous by nature: in the scheduling example, edge features may carry precedence constraints when between operations, or processing times when between machines and operations, and no information at all when between machines. Instead of packing all these different types of relations into single vector, with padding values wherever a feature is undefined for given edge, we propose a multi-type architecture where the adapters output separate embeddings per type (for nodes) compatible pairs of types (for edges). Each layer of the model, instead of being a monolithic self-attention block operating on all the nodes, becomes a task-specific combination of both cross- and self-attention blocks, as described by equation [b] operating on different type- compatible subsets of nodes and edges. This is illustrated in Fig. right in the case of two types. For n types, the architecture would be similar but involves n² mixed-attention blocks, where each type attends to itself and every other type, or a selection of relevant types defined by the task. Therefore, in our scheduling example, the model will contain separate self-attention blocks, for operation nodes and machine nodes respectively, and cross-attention blocks, for mnechie edges and vice- versa. Observe that while the architecture configuration now task-specific. the model parameters remain the same for all the configurations: all the attention blocks of a layer, be them self- cross- attentions, and whatever the types they involve, share the same, layer-specific parameters. This is precisely what allows to train unique model to solve arbitrary single- and multi-type problems.
3.6 TRAINING PROCEDURE
We train GOAL on a set of eight various CO problems (described in Sec 4. For each training problem, we define the corresponding BQ-MDP, the linear input and output adapters match the

---

Published as a conference paper at ICLR 2025
dimensions of the input features and the construction actions. We train the model by imitation of high-quality solutions, provided by specialized solvers. At each step. we sample a problem and create batch of instances by sampling suffix subproblems from the training instances, similarly to (Drakulic et al. 2023). 'he forward and backward processes involve the input and output adapters, as well the backbone parameters, where the mixed-attention and feed-forward blocks are duplicated within each layer if the sampled task is multi-typed.
4 EXPERIMENTS
Our experiments aim to address the following questions: (i) does the GOAL approach enable learn- ing a single backbone to effectively solve variety of CO problems (Sec 4.1 (ii) can it be used as pretrained model and efficiently fine-tuned to solve new CO problems, unseen at training (Sec 4.2 (iii) to what extent do mixed-attention blocks and multi-type architecture contribute to the results We begin by describing the multi-task training of GOAL.
(Sec 4.3) ?
Training tasks. We train GOAL eight classic and varied CO problems. For each problem, generate a training dataset of 1 million random instances and solve them using traditional solvers. Specifically, we consider the following problems and oracle solvers: the Asymmetric Traveling Salesman Problem (ATSP) with LKH (Helsgaun 2017). the Capacitated Vehicle Routing Problem (CVRP) with LKH (Helsgaun 2.17), the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) with HGS (Vidal 2022) the Orienteering Problem (OP) with A4OP (Kobeaga et al.)
2018), the Knapsack Problem (KP) with ORTools (Perron Furnon| 2022), the Minimum Vertex Covering Problem (MVC) with VC (Cail 2023), the Unrelated Machine Scheduling Problem (UMSP) with HiGHS (Huangfu & Hall 2018) and the Job Shop Scheduling Problem (JSSP) with ORTools (Perron & Furnon 2022). The training instances are of size 100 nodes, 10x 10 for JSSP and x00x20 for UMSP (resulting in both cases in 100 operation nodes). The description of the problems and the associated data generation processes is provided in Appendix F
Training details. GOAL is trained by alternating batches in random order from each of the training tasks, using a single-class cross-entropy loss for ATSP, CVRP, CVRPTW, OP, JSSP and UMSP and a multi-class cross-entropy loss for KP and MVC. We use AdamW optimizer (Loshchilov & Hutter, 2018), with an initial learning rate of 0.0005 and a decay rate of 0.97 every 10th epoch. We trained the model on 8 Nvidia V100 GPU servers, with batch size of 256 for 7 days, completing ca. 400 epochs. The best model was selected based on the average performance on a validation set of 128 instances per problem. The model hyperparameters are described in Appendix A
Baselines. We consider the following constructive neural models as baselines: AM Kool et al.
2018), MDAM (Xin et al., (02T). POMO (K wwon et al.; (2020). Sym-NCO (Kim et al. 2022).
BQ-NCO (Drakulic et al., 2023). MVMOE (Zhou et al. (2024). MatNet (Kwon et al. 202 1). S2V-
DQN (Khalil et al. 2017). RouteFinder (Berto et al. 2024). COMPASS (Chalumeau et al. 2023)
and Gumbeldore (Pirnay & Grimm 2024). All models except MVMoE and RouteFinder are special- ized and trained in single-task mode. They are often combined at test time with various enhancers, such as heam search Drakulic et al. (2023), sumulation-guides beam search (Choo et al., 2022). MCTS (Xing & Tu. (020)) instance augmentation (Kwon al., 2020), active search (Hottung ett al. (021). but for fair comparison, all the results we report are obtained by pure greedy applica- tion of the trained policy at test time.
4.1 PERFORMANCE ON THE TRAINING TASKS
In Table [ we compare the performance of GOAL to the relevant neural baselines for each problem as well as its single-task version (i.e. GOAL trained separately for each task). First, we observe that the best performance is achieved by the single-task GOAL in 7 out of the 8 tasks, with a com- putation time comparable to that of the baselines. This proves the versatility and effectiveness of our proposed architecture, even for a specialized model. Second, we see that multi-task GOAL is only slightly worse than the single-task version. These results validate the capability of the GOAL backbone, together with the task task-specific adapters, to effectively solve the variety of training tasks. More broadly, they demonstrate that multi-tase task learning can be a successful paradigm for neural combinatorial optimization.
7

---

Published as a conference paper at ICLR 2025
ATSPI00
CVRPI00
CVRPTWIO0
OP100
gap
time
gap
time
gap
time
gap
time
Oracle solver
0.00%
29s
0.00%
12m
0.00%
10m
0.00%
1.1m
AM greedy
7.11%
1s
5.35%
1s
MDAM greedy
4.84% %
1s
2.88%
16s
POMO no aug
1.21 %
Sym-NCO greedy
3.33%
1s
2.03%
2s
BQ-NCO greedy
1.27%
2s
2.79%
2s
0.22%
2s
MVMoF/4E
1.65%
1s 4.90%
1s
RouteFinder-TB:
1.50%
1s
3.19%
1s
MatNet greedy
0.93%
1s
GOAL SINGLE-TASE greedy
0.30%
I0s
2.34%
10s
2.61%
10s
-0.04%
3s
GOAL MULTI-TASH greedy
0.91%
10s
3.16%
10s
3.82%
10s
0.43%
3s
KPT00
MVC100
JSSPT0x
IO
gap
time
gap
time
gap
time
gap
time
Oracle solver
0.00%
1s
0.00%
2m
0.00%
2m
0.00%
47s
POMO aug
0.19%
BQ-NCO greedy
0.10%
S2V-DQN
0.97%
2s
COMPASS
4.70%
3h
Gumbeldore greedy
3.17%
9s
GOAL SINGLE-TASK greedy
0.10%
3s
0.23%
3s
2.82%
7s
2.73%
15s
GOAL MULTI-TASK greedy
0.12%
3s
0.37% %
3s
3.84%
7s
4.13%
15s
Table I:
Performance on 128 test instances from the training tasks. Each gap is with respect to the oracle and often corresponds to the optimality gap. Lower is better.
In addition, in Appendix F we provide experimental results demonstrating GOAL's excellent zero- shot generalization instances up to 10 times larger than the training instances. We can note in particular the strong generalization for ATSP which seems much more challenging for the state-of- the-art baselines. This confirms the effectiveness of our mixed-attention mechanism.
4.2 FINE-TUNING TO NEW TASKS
In this section, we want to evaluate the transfer capability of the trained GOAL backbone to un- seen tasks. We consider eight diverse new COPs: the Traveling Repairman Problem (TRP), the Prize Collecting TSP (PCTSP), the Open CVRP (OCVRP), the Split Delivery CVRP (SDCVRP), Sequential Ordering Problem (SOP), the Maximum Covering Location Problem (MCLP), the Maximum Independent Set (MIS) problem and the Open Shop Scheduling Problem (OSSP) (de- tailed descriptions in Appendix [F. GOAL can be fine-tuned to specific problems in two modes. In both, the adapters trained from scratch, and the backbone is also open backpropagation (no parameter freeze). The supervised mode is identical to training, except it processes only a few (labeled) instances of the problem for few steps. Details and results given in Appendix [B] The unsupervised mode is more challenging, but also more realistic, since we may not have ac- cess to good-quality solutions for the new problem. We propose fine-tune the model by iterative mmitation-improvenne
steps between an Apprentice and an Expert, as in Exit (Anthony et al. 2017). While Exit relies on a possibly complex tree-search for improvement, we use instead brute-force but fast method, where the Expert samples multiple solutions (in our case 128) per instance from the Apprentice and selects the best, if sufficiently better, and sends it back the Apprentice (current model) for imitation. This is similar to the self-labeling strategy proposed by Corsini et al. (2024) for the JSSP. One could also use more sophisticated experts such as generic local search heuristics smarter sampling (Pirnay & Grimm 2024) to accelerate the finetuning. Performance results are given Fig 2 which shows that unsupervised fine-tuning systematically outperforms unsupervised training of the whole model from scratch at comparable processing time budget. We also compare finetuning GOAL to finetuning the single-task models and report the results in Fig We observe that the multi-task model consistently performs well better than the "most-related" single-task
8

---

Published as a conference paper at ICLR 2025
model (e.g. CVRP model for OCVRP or JSSP model for OSSP), hinting to the synergistic effect of the multi-task training.
Traveling Repairman Problem
Prize Collecting TSP
Open CVRP
Spllt delivery CVRP
from scratch
From scratch Tune GOAL
From kzrtch Tine SOAL
25
Tunee GOAL
40-
50
50
40-
40
30-
30
Tune GBAL
30
20-
20
5
10
10
10
0.72
4.00
4.4
233
32
1.0
1.
2.0
3.3
22
0.0
1.1
22
Sequential Ordering Problem
Maximum Covering Location Problom
Maximum Independent Set
Open Shop Scheduling Problem
from scratch
From scraich
from scrwir Tune GOAL
40
From smarch
Ture GOAL
Tana COAL
Line GOAL
25
10
10-
2.925
3.90%
0.31%
3.2
0.5
0.7
0.5
0.0
2.0
Figure 2: Unsupervised fine-tuning of GOAL to eight diverse new tasks. We report the best results over 10 runs both for training from scratch and fine-tuning,
4.3 ABLATION STUDY
Mixed-attention blocks. We compare our mixed-attention blocks with alternative modules which also aim at mixing the edge information with the attention scores, namely MatNet (Kwon et al. 202I] and G2G (Henderson al.] 2023). More precisely we focus on the ATSP and train three versions of GOAL with the three different variants of mixed-attention. For MatNet, we keep the original syper-parameters used for solving the ATSP, Fig 3 (left) presents the models performance (optimality gap on a test set of 128 instances) at different points of the training. We see that using our mixed-attentics or on the speed of convergence (G2G). Note that these ablations are performed on smaller training dataset than in the previous experiments (100k instances), hence the larger optimality gap.
blocks leads to significant gain, on the performance at convergence (MatNet)
Multi-type transformer. Our multi-type architecture is meant to deal with tasks that are naturally represented by multipartite graphs with heterogeneous nodes or edges, typically scheduling prob- lems where job and machine nodes play different roles. To evaluate its effect on the performance, we compare it to that obtained with the more direct alternative which ignores node and edge hetero- geneity: we simply gather in a single tensor the node (edge) representations of the different types, produced by the input adapter, and use the original single-type model. Note that because of the lin- earity of the input adapters, these representations can be obtained either by defining a specific linear transform per type, or equivalently by defining a single linear transform on the direct sum of the feature spaces of the different types. We implemented the former for the Job Shop Scheduling Prob- lem and present in 3 (middle) a comparison between the training performance of the single-type and multi-type architectures. Clearly, the multi-type architecture converges faster and to a better performance: after 200 epochs of training on 100K instances, it reaches a test optimality gap of 4.6% while the single-type model achieves only 8.9%. Finally, note that the multi-type model offers more flexibility for fine-tuning: while, in order to be task agnostic at training, parameter sharing between the type specific attention blocks of a layer must be enforced, that constraint can be relaxed fine-tuning to better fit the task at hand.
Sparsification using a codebook. Fig 3 (right) experimentally confirms the importance, in the fine-tuning phase (supervised mode), of sparsifying the input adapter with a shared codebook. The results are given for the PCTSP, but similar results are available in Fig 6 (Appendix) for the other problems. The shared codebook results in a more stable finetuning (over 10 runs) and to a better optimality gap. While we do not observe significant effeet the performance on the training tasks, we believe that constraining the rank of the codebook tends to prevent its vectors from specializing for individual tasks seen at training, which would be of limited use when fine-tuning to new tasks.
9

---

Published as a conference paper at ICLR 2025
Asymmetric TSP
Shop Scheduling Problem
Prize Collecting TSP
40
Optimotty 20p 1511
GDAL with G2G attentice
GOAL with mixed attertion
Single type GOAL (stacked Inputi Multi-type GOAL
35
I) codtbook
M/o codaboox
GDAL with Matifel atleed
30
25
20
10
50
200
10
12
14
Thaninn
Epachs
&Instances!
Figure 3: (left) Performance with different variants of
(middle) Performance of
single- multi-type GOAL. (right) Fine-tuning of GOAL with and without the codebook.
Open CVRP
Prize collecting
72
72
CHUFTW aingl lasc
30
CVEP singhe
CVEPTW aiggl lask
angin tace
aingii back
(50
UPV baaa
UIVE single
JSP angle lask
J50P sirglt lush
male
S0HL mraii lasic
Problum
sangin CVEE ainglt look
CHEP smglt Last
45-
MYC diigle Caik
MVC enge carc
UPMS ding
LeNG stngle
coteu Re
malt
mubii
Stpo 1911 S00p (9Gance))
Steps S311 SCOp 100.0.0..
Figure 4: Comparison of the (supervised) fine-tuning of the single- versus multi-tast task GOAL on four new problems.
DISCUSSION AND CONCLUSION
In this paper, we propose a generalist neural CO model (GOAL) and demonstrate the feasibility of learning a shared backbone model to solve a variety CO problems, spanning routing, scheduling, packing and classic graph problems. We have shown the benefits of GOAL as (i) a single-task spe- cialized model, providing state-of-the-ee to solve different problems with the same backbone; and (iii) a pretrained model. which is efficiently fine-tuned to new problems. The proposed multi-task pre-training relies on imitation learning and therefore the availability of good-quality solutions. While this is not an intrinsic limitation of the GOAL model, we believe that imitation learning is an effective training paradigm for learning multi- task models. This is indeed demonstrated by previous works which relied on mondencc-mdeliing training tasks for control (Sun et al.) 2023 Reed et al., 2022). It is particularly advantageous for CO as we can leverage high-quality solutions to classical ha-hard problems, provided by traditional solvers, which are based on decades of OR research. In contrast, for a new potentially more original problem, we show that GOAL can be effectively finetuned without any supervision. Our approach is limited to problems where solution feasibility is easy ensure during the construction, which is a common requirement of constructive heuristics. Finally the quadratic complexity of the under- lying transformer architecture makes the approach too costly for problem sizes beyond a thousand nodes. Exploring more efficient forms of attention as basis for our titxeedttttetionn blocks would be a promising direction for better scaling.
results on seven CO problems; (ii) multi-tast model, able
10

---

Published as a conference paper at ICLR 2025
ETHICS STATEMENT
To the best of our knowledge, no aspect of our research raises ethics issues. It did not involve human subjects, and considers only generic Combinatorial Optimization problems with dubious association.
REPRODUCIBILITY STATEMENT
For full reproducibility, the implementation of the backbone, the adapters and all the experiments described in this paper are publicly available at petps://githubb com naver goal co The training data generation process, the training process, and its hyper-parameters are described in detail the Appendix.
REFERENCES
Jean-Marc Andreoli. Convolution, attention and structure embedding. In Proc. of NeurlPS Workshop on Graph Representation Learning, pp. 8, Vancouver, BC, Canada, December 2019.
Thomas Anthony. Zheng Tian, and David Barber. Thinking Fast and Slow with Deep Learning and Tree Search. Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Thomas Bachlechner, Bodhisattwa Prasad Majumder, Henry Mao, Gary Cottrell, and Julian McAuley, ReZero is you need: Fast convergence at large depth. Proceedings of the Thirty- Seventh Conference Uncertainty in Artificial Intelligence, pp. 1352-1361. PMLR, December 2021.
Ankur Bapna and Orhan Firat. Simple, Scalable Adaptation for Neural Machine Translation. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp- 1538 1548, Hong Kong, China, November 2019. Association for Computational Linguistics.
Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. Neural Combina- torial Optimization with Reinforcement Learning. In Sth International Conference on Learning Representattons, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings. OpenReview.net, 2017.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: A methodological tour d' d'horizon. European Journal of Operational Research, 290(2): 405-421, 2021.
Federico Berto, Chuanbo Hua, Nayeli Gast Zepeda, André Hottung, Niels Wouda, Leon Lan, Kevin Tiemny, and Jinkyoo Park. RouteFinder: Towards Foundation Models for Vehicle Routing Prob- lems. In ICML 2024 Workshop on Foundation Models in the Wild, July 2024.
Dimitri Bertsekas. Reinforcement Learning and Optimal Control. Athena Scientific, July 2019. ISBN 978-1-886559-39977
Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation. In Sanmi Koyejo. S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Pro- cessing Systems 2022, NewrlPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022.
Ilhem Boussaid, Julien Lepagnot, and Patrick Siarry. A survey on optimization metaheuristics. Information Sciences, 237:82-117 July 2013. ISSN 0020-0255.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neclakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M.

---

Published as a conference paper at ICLR 2025
Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever. and Dario Amodei. Language Models are Few-Shot Learners. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Pro- cessing Systems 2020, NeurlPS 2020, December 6-12, 2020, Virtual, 2020.
Shaowei Cai. VC Solver: Implementation of the algorithm proposed in Towards Faster Local Search for Minimum Weighted Vertex Cover on Massive Graphs, July 2023. Preprint.
Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial Optimization and Reasoning with Graph Neural Networks. In Twenty- Ninth International Joint Conference on Artificial Intelligence, volume 5, pp. 4348-4355, August 2021.
Felix Chalumeau, Shikha Surana, Clement Bonnet, Nathan Grinsztajn, Arnu Pretorius, Alexandre Laterre, and Thomas D. Barrett. Combinatorial Optimization with Policy Adaptation using Latent Space Search, November 2023, Preprint arXiv:231 1.33569.
Xinyun Chen and Yuandong Tian. Learning to Perform Local Rewriting for Combinatorial Opti- mization. In Advances Neural Information Processing Systems, volume 32. Curran Associates,
Inc., 2019.
Jinho Choo, Ycong-Dae Kwon, Jihoon Kim, Jeongwoo Jac, Andre Hottung, Kevin Tiemny, and Youngjune Gwon. Simulation-guided Beam Search for Neural Combinatorial Optimization. In NeurlPS 2022, 2022.
Andrea Corsini, Angelo Porrello, Simone Calderara, and Mauro Dell' Amico. Self-Labeling the Job Shop Scheduling Problem, July 2024. Preprint arXiv:2401. 11.4401.18449 11849.
Jacob Devlin, Ming-Woi Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Lan- guage Technologies, Volume I (Long and Short Papers), pp. 4171-4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.
Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Marc Andreoli. BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization. In Advances in Neu- ral Information Processing Systems, volume 36, pp. 17416-77449, December 2023.
Jonas K. Falkner and Lars Schmidt-Thieme. Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention. arXiv:2006.091 09000 [cs, stat), June 2020.
Zhang- Hua Fu, Kai- Bin Qiu, and Hongyuan Zha. Generalize a Small Pre-trained Model to Arbitrar- ily Large TSP Instances. Proceedings of the AAAI Conference on Artificial Intelligence, 35(8):
7474-7482, May 2021. ISSN 2374-3468.
Keld Helsgaun. An Extension of the Lin- Kon--eenighan-Heee ing Salesman and Vehicle Routing Problems. Technical report, Roskilde University, Roskilde, Denmark, 2017.
TSP Solver for Constrained Travel-
James Henderson, Alireza Mohammadshahi, Andrei Coman, and Lesly Miculicich. Transformers as Braph-to-Graph Models. In Yanai Elazar, Allyson Ettinger, Nora Kassner, Sebastian Ruder, and Noah A. Smith (eds.), Proceedings of the Big Picture Workshop, pp. 93-107, Singapore, December 2023. Association for Computational Linguistics.
Ellis Horowitz and Sartaj Sahni. Exact and Approximate Algorithms for Scheduling Nonidentical Processors. Journal of the ACM, 23(2):317-321 April 1976. ISSN 0004-5411.
André Hottung and Kevin Tiemey. Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem. In ECA/ 2020, pp. 443-450. IOS Press, 2020.
André Hottung, Yeong-Dat Dae Kwon, and Kevin Tiemnyy Efficient Active Search for Combinatorial Optimization Problems. In International Conference on Learning Representations, October 2021.
12

---

Published as a conference paper at ICLR 2025
Q. Huangfu and J. A. J. Hall. Parallelizing the dual revised simplex method. Mathematical Pro- gramming Computation, 10(1):119-142 March 2018. ISSN 1867-2957.
Borja Ibarz, Vitaly Kurin, George Papamakarios, Kyriacos Nikiforou, Mehdi Bennani, Róbert Csordás, Andrew Joseph Dudzik, Matko Bošnjak, Alex Vitvitskyi, Yulia Rubanova, Andreea Deac, Beatrice Bevilacqua, Yaroslav Ganin, Charles Blundell, and Petar Veličković. A Generalist Neural Algorithmic Learner. In Proceedings of the First Learning on Graphs Conference, pp.
2:1-2:23. PMLR, December 2022.
Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. Constraints, 27(1-2):70-99 April 2022. ISSN 1383-7133.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning Combinatorial Opti- mization Algorithms over Graphs. In Advances in Neural Information Processing Systems, vol- ume 30. Curran Associates, Inc., 2017.
Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization. In Advances in Neural Information Processing Systems, volume 35, pp. 1936-1949, December 2022.
Gorka Kobeaga, María Merino, and Jose A. Lozano. An efficient evolutionary algorithm for the orienteering problem. Computers Operations Research, 90:42-59, February 2018. ISSN 0305- 0548.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, Learn to Solve Routing Problems! In International Conference on Learning Representations, September 2018
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep Policy Dynamic Pro- gramming for Vehicle Routing Problems. In Pierre Schaus (ed.). Integration of Constraint Pro- gramming, Artificial Intelligence, and Operations Research, pp. 190-213, Cham, 2022. Springer International Publishing. ISBN 978-3-031-08011-
Bernhard Korte and Jens Vygen. Combinatorial Optimization: Theory and Algorithmxx volume 21 of Algorithms and Combinatorics. Springer, Berlin, Heidelberg, 2018. ISBN 978-3-662-56038-9 978-3-662-56039--6
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. In Advances in Neural Information Processing Systems, volume 33, pp. 2020.
Curran Associates, Inc.,
Yeong-Dae Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. In Advances in Neural Information Processing Systems, volume 34, pp. 5138-5149. Curran Associates, Inc., 2021.
Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. In Advances in Neural Information Processing Systems, volume 34, pp. 26198-26211 1. Curran As- sociates, Inc., 2021.
Zhuoyi Lin, Yaoxin Wu, Bangjian Zhou, Zhiguang Cao, Wen Song, Yingqian Zhang, and Senthilnath Jayavelu. Sross-Problem Learning for Solving Vehicle Routing Problems. In Thirty- Third International Joint Conference on Artificial Intelligence, volume 7, pp. 6958-6966, August 2024.
Fei Liu, Xi Lin, Zhenkun Wang, Qingfu Zhang, Tong Xialiang, and Mingxuan Yuan. Muski-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalization. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '24, pp- 1898-1908, New York, NY, USA, August 2024. Association for Computing Machinery. ISBN 979-8-4007-0490-1.
Ilya Loshchilov and Frank Hutter. Decoupled Weight Decay Regularization. In International Con- ference Learning Representations, September 2018.
13

---

Published as a conference paper at ICLR 2025
Fu Luo, Xi Lin, Zhenkun Wang, Xialiang Tong, Mingxuan Yuan, and Qingfu Zhang. Self- Improved Learning for Scalable Neural Combinatorial Optimization, May 2024. Preprint arXiv:2403.19661
Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang. Zhenghua Chen, and Jing Tang. Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer. In Advances in Neural Information Processing Systems, November 2021.
Sahil Manchanda, Sofia Michel, Darko Drakulic, and Jean-Mare Andreoli. On the Generalization of Neural Combinatorial Optimization Heuristics. In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD), Grenoble, France, September 2022.
MohammadReza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac. Reinforcement Learning for Solving the Vehicle Routing Problem. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Xuanhao Pan, Yan Jin, Yuandong Ding, Mingxiao Feng. Zhao, Lei Song, and Jiang Bian. H-TSP: Hierarchically solving the large-scale traveling salesman problem. In Proceedings of the Thirty- Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium Educational Advances in Artificial Intelligence, volume 37 of AAAI"23/AAA"23//AAA pp. 9345-9353, AAAI Press, February 2023. ISBN 978-1-57735-880-0
Laurent Perron and Vincent Furnon. OR-tools, 2022. Preprint.
Jonathan Pirmay and Dominik G. Grimm. Self- Inff---proveeetttt for Neural Combinatorial Optimization: Sample without Replacement, but Improvement, March 2024. Preprint arXiv:2403.15 151::2580.1......
Ruizhong Qiu. Zhiqing Sun, and Yiming Yang. DIMES: A Differentiable Meta Solver for Combina- torial Optimization Problems. In Advances in Neural Information Processing Systems, December 2022.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning Transferable Visual Models From Natural Language Supervision. In Pro- ceedings of the 38th International Conference on Machine Learning, pp. 8748-8763. P118--873.PMLP.. PMLR, 2021.
Scott Reed, Konrad Zolna, Emilio Parisotto, Sergio Gómez Colmenarejo, Alexander Novikov, Gabriel Barth-maron, Mai Giménez. Yury Sulsky. Jackie Kay, Jost Tobias Springenberg. Tom Eccles, Jake Bruce, Ali Razavi, Ashley Edwards, Nicolas Heess, Yutian Chen, Raia Hadsell, Oriol Vinyals, Mahyar Bordbar, and Nando de Freitas. A Generalist Agent. Transactions on Machine Learning Research, August 2022. ISSN 2835-8856.
Frank Ruis, Gertjan Burghouts, and Doina Bucur. Independent Prototype Propagation for Zero- Shot Compositionalitty In Advances in Neural Information Processing Systems, volume 34, pp. 10641-10653. Curran Associates, Inc., 2021.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random Features Strengthen Graph Neural Networks. 0rXiv:2002.03155 [cs, stat), January 2021.
Jiwoo Son, Minsu Kim, Hyeonah Kim, and Jinkyoo Park. Meta-SAGE: Scale Meta-Learning Sched- uled Adaptation with Guided Exploration for Mitigating Scale Shift Combinatorial Optimiza- tion. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of ICML 23, pp. 32194-32210, Honolulu, Hawaii, USA, July 2023. JMLR.org.
Adam Stooke, Kimin Lee, Pieter Abbeel, and Michael Laskin. Decoupling representation learning from reinforcement learning. In International Conference on Machine Learning, pp. 9870-9879. PMLR. 2021.
Yanchao Sun, Shuang Ma. Ratnesh Madaan, Rogerio Bonatti, Furong Huang, and Ashish Kapoor. SMART: Self-supervised Multi-task pretrAining with contRol Transformers. In The Eleventh International Conference Learning Representations, February 2023.
14

---

Published as a conference paper at ICLR 2025
Zhiqing Sun and Yiming Yang. DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Opti- mization. Advances in Neural Information Processing Systems, 36:3706-377 -731, December 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention All you Need. In Advances in Neural Infor- mation Processing Systems, volume 30. Curran Associates, Inc., 2017.
Vijay V. Vazirani. Approximation Algorithms. Springer, Berlin, Heidelberg, 2003. ISBN 978-3-642- 08469-0 014-3--662-0455--7
Thibaut Vidal. Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Computers & Operations Research, 140: 105643, April 2022. ISSN 0305-0548.
Chenguang Wang and Tianshu Yu. Efficient Training of Multi-task Neural Solver with Multi-armed Bandits. CoRR, abs/2305.06361, 2023.
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning Improvement Heuris- tics for Solving Routing Problems. IEEE Transactions on Neural Networks and Learning Systems, 33(9):5057-5069, September 2022. ISSN 2162-2388.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-Decoder Attention Model with Em- bedding Glimpse for Solving Vehicle Routing Problems. Proceedings of the AAAI Conference on Artificial Intelligence, (0113):2242-120000 May 2021. ISSN 2374-3468.
Zhihao Xing and Shikui Tu. Graph Neural Network Assisted Monte Carlo Tree Search Approach to Traveling Salesman Problem. IEEE Access, 8: 1:108418-108425 2020, ISSN 2169-3536..
Cong Zhang. Wen Song, Zhiguang Cao, Jie Zhang. Puay Siew Tan, and Chi Xu. Learning to dispatch for job shop scheduling via deep reinforcement learning. In Proceedings of the 34th International Conference Neural Information Processing Systems, NIPS' 20, pp. 1621-1632, Red Hook, NY, USA, December 2020. Curran Associates Inc. ISBN 978- 778-1-7138-295--6
Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Towards omni-generalizable neural methods for vehicle routing problems. In International Conference Machine Learning, pp. 42769-42789, PMLR, 2023.
Jianan Zhou, Zhiguang Cao, Yaoxin Wu, Wen Song, Yining Ma, Jie Zhang, and Chi Xu. MVMoE: Multi-task vehicle routing solver with mffture-of-eexpers. In Proceedings the 41st International Conference on Machine Learning, volume 235 of ICML 24, pp. 61804 31804-61824 61824, Vienna, Austria, July 2024. JMLR.org.
15

---

Published as a conference paper at ICLR 2025
A GOAL HYPERPARAMETERS AND SIZE
The GOAL backbone consists of L=9 layers with an embedding size of D=D=128 (the same for both nodes and edges), feed-forward dimension of 512, and ReZero normalization Bachlechner et al. (202T) The mixed-attention blocks have 8 heads. The task specific input adapters produce representations of low dimension 8=8 for nodes and 8=4 for edges, which are mapped embed- dings by a shared codebook of dimension &x for nodes and &x D for edges, respectively. GOAL backbone has 2.1M parameters and adapters are very light, with only a few thousand parameters per task. For the illustration, RouteFinder (Berto et al. 2024) with POMO has 1.3M, MVMoE (Zhou ct a 2024) has 3.7M (the same model used in RouteFinder with MVMoE), and RouteFinder with the Transformer Encoder 1.7M.
B SUPERVISED FINE-TUNING OF GOAL
In section we describe the process of fine-tuning our multitask model on eight unseen tasks in unsupervised mode. Although fine-tuning without labeled data is useful for transferring to new tasks, it comes at a cost it is quite expensive. Our experiments show that fine-tuning to the new problems with unsupervised learning takes, average, few hours.
On the other hand, we demonstrate that GOAL can be effectively fine-tuned using a very small amount of labeled data, in a short time. Figure presents the performance of fine-tuning GOAL on the same eight problems used in unsupervised tuning. Here, we use only 128 solved (but not necessarily optimal) instances and tune the model with just one training step per instance (more precisely, one training step per tail-subproblem of each instance). In contrast to unsupervised tuning, this method extremely fast; fine-tuning takes only few minutes.
kcratch
Tune GON,
GOM,
Trawiling Repairman Problem
Collecting TSP
Open
Split delivery CVRP
20
50
50
15
-0
4.
30-
10
25-
0.1
0.5
1.2
2.7
22
3.3
0.1
0.6
10
15
20
0.1
0.6
12
1.7
22
2.7
233
0.1
0.6
12
17
22
27
Sequential Ordering Problem
Maximum Covering Location Problem
Maximum Independent Set
Open Shop Scheduling Problem
12.5
op9ges
20
20
5.0
10
2715
0.0
22
2.7
0.0
0.2
0.3
9.4
3.1
2.1
30
6.0
4.9
59
Timeminal
Time
Time (mirs)
Tima (mina)
Figure 5: Supervised fine-tuning on eight new problems. We report the best results over 10 runs for both training from scratch and fine-tuning.
C IMPACT OF CODEBOOK ON FINE-TUNING
In 4.3 We discussed the importance of sparsifying the input adapter with a shared codebook. Al- though this feature does not impact training performance, phase. By adding a codebook to the model, fine-tuning becomes more stable and achieves better performance. In the main text, we presented a figure comparing fine-tuning for the PCTSP with models that have and do not have codebook. Figure illustrates the impact of the codebook on fine-tuning the multitask model across all eight problems we used for transfer. these experiments, used light-traines' models with and without codebook. The models are trained on 100K in- stances, for 200 epochs. For each experiment, we perform 10 inference runs and report the mean with confidence interval of 100.
very important in the fine-tuning
iilustaee
16

---

Published as a conference paper at ICLR 2025
Prvve tng bezalrman Protlem w'' cocebock
Colletiigg
Open CVSP
SptP Eeery
40
wit coliilec
25-
cocobook
44
22
2.00
25-
13
In eCcosBoos
30
26
25-
12
Zaps OP8 (1S18TO1
2051 (0R8 Mtg
S1804 F0T0310P (nstatos))
Stpg 17t 100 Isttrco
Figure 6: Ablation study of codebook
op selection
Output adapter
00
machine
randomly pidked
Chipput wdlpterr
porm
marhine
hackbone
FF
nom
norm
norm
MMA
MMA
MMA
MA
M&A
MMS
MMA
MA
machine
op
execution time, availability time
JC0 moshhne
machine
machine
availabiltt time
Job
op
op-machine assignment
codebook
machiie
nvaiibbiity time
Input adapter
machine
adapter
exccution time
op-op
precedence, same relation
Instance
machise
instance
(a) the Unrelated Machine Scheduling Problem (UMSP)
(b) the Job-shop Scheduling Problem (JSSP)
Figure 7: Illustration of the multi-type model on scheduling tasks in GOAL. The "MA" blocks use vanilla multi-head attention while the "MMA" use our multi-head mixed-attention.
D MULTI-TYPE MIXED ATTENTION LAYERS FOR UMSP AND JSSP
As illustration of our proposed multi-type transformer architecture, we present in Figure the inputs to the mixed-attention blocks for the Unrelated Machine Scheduling (UMSP) and the Job Shop Scheduling Problems (JSSP). Note that the case UMSP, since there is no edge information between jobs and between machines, the self-attention blocks (left-most and right-most attention blocks) degenerate to vanilla attention. The cross aross-att blocks, on the other hand, are mixed, and they fed the same edge information, holding the job execution times each machine (transposed from each other). In JSSP, the situation is similar, but ops have two kinds of relations between themselves: precedence, and sharing the same job. Hence the self-attention block ops is mixed.
17

---

Published as a conference paper at ICLR 2025
Train. distrib.
Generalization
200
500
1000
LKH
0.00%
29s
0.00%
48s
0.00%
2m
0.00%
4m
MatNet
1.57%
1s
97.21%
12s
ATSP
BQ-NCO
1.63%
Is
1.90%
98
4.29%
8.09%
Im
GOAL
0.45%
5s
1.54%
30s
1.62%
3m
1.96%
5m
LKH
0.00%
12m
0.00%
2h
0.00%
5h
0.00%
7h
AM
7.11%
1s 10.16%
1s
17.2%
1s
72.95%
2s
MDAM
4.84%
1s
7.54%
6s
12.94%
24s
32.25%
1m
CVRP
POMO
1.21%
1s
5.94%
6s
31.36%
32s
284.58%
1m
Sym-NCO
3.33%
1s
8.42%
3s
37.58%
54s
481.53%
9m
BQ-NCO
2.79%
1s 2.81%
9s
3.64%
55s
5.88%
GOAL
3.16%
5s
3.42%
30s
3.90%
2m
7.37%
5m
HGS (Is) f
108/128
2m
14/128
2m
0/128
2m
0/128
2m
CVRPTW
HGS (1m)
0.00%
10m
0.00%
26m
0.00%
2h
0.00%
2h
GOAL
3.82%
7.71%
30s
9.49%
2m
6.75%
5m
EА4ОP
0.00%
1m 0.00%
3m
0.00%
11m
0.00%
45m
AM
5.35%
1s
11.05%
1s
22.29%
1s
30.73%
1s
OP
MDAM
2.88%
16s
5.55%
1s
18.31%
4s
30.05%
15s
SymNCO
2.03%
6.60%
3s
19.81%
24s
31.79%
Im
GOAL
0.43%
38
I L60%%
10s
7.45%
17s
15.62%
30s
ORTools
0.00%
1s
0.00%
1s
0.00%
<
1s
0.00%
< 1s
POMO
0.19%
1s
0.50%
1s
6.41%
31s
5.34%
1m
KP
BQ-NCO
0.10%
0.14%
6s
0.74%
0.92%
GOAL
0.12%
3s
1.63%
6s
2.40%
10s
2.59%
16s
10x10
10x15
13x15
20x15
ORTools 0.00%
47s
0.00%
2m
0.00%
3h
0.00%
80h
JSSP
COMPASS 4.70%
8.00%
5h
10.40%
8h
GOAL 4.13%
15s
11.02%
43s
10.74%
45s
22.53%
4m
Table 2: Generalization performance larger instances. Lower is better. All NCO methods perform greedy decoding, except for methods marked with o; they not provide results for greedy decoding. Solvers marked with are unable to solve all instances within the given time budget; report the number instances successfully solved.
GENERALIZ.ATION TO NEW INSTANCE DISTRIBUTIONS
Table 2 presents the generalization to instances up to 10 times bigger than the training ones, for subset of the training tasks. Our approach takes bit more time than some baselines, but note that scaling to much larger instances is not focus of this paper. One possible way to avoid the quadratic complexity of attention is by using task-specific heuristics, such as the KNN heuristic for routing problems (proposed by Drakulic et al. (2023), to reduce the size of the input instance and the overall complexity. Another approach could be using methods that do not rely on quadratic attention blocks, such those proposed by Luo et al. (2024), though this method tends to be highly specialized for specific problems.
Our model demonstrates excellent generalization performance in terms of the optimality gap for problems with various edge features, such as ATSP (with an asymmetric distance matrix) and JSSP (with two binary matrices with precedence constraints and job-machine relations).
F DESCRIPTION OF THE CONSIDERED CO PROBLEMS
In this Section, we describe the CO problems (in alphabetical order) that are solved by GOAL as well as the instance generation process. GOAL solves problems from various categories: Routing, Scheduling, Packing, Graph, and Location Problems. For each problem, we provide all the details of how it is represented in model, including a list of instance, node and edge features, the action chosen by the model, and the objective. We also describe how we generate a solution trajectory for problems where single cross-entropy loss for behavioral cloning.
18

---

Published as a conference paper at ICLR 2025
F.1 CAPACITATED VEHICLE ROUTING PROBLEM AND DELIVEE CAPACITATED VEHICLE ROUTING PROBLEM
The Capacitated Vehicle Routing Problem (CVRP) is standard routing problem. The goal of CVRP is to op- timize the delivery routes of fleet of vehicles to a set of customers while considering each vehicle's capacity. The objective to minimize the overall distance trav- eled by the vehicles while respecting the capacity con- straints and ensuring that all the customer demands are met. Split-Delivery CVRP (SDCVRP) is variant of the CVRP that allows a single customer's demand to be ful- filled by multiple vehicles. In our experiments we use Euclidean CVRP for training GOAL and SDCVRP for fine-tuning.
Data generation. Node locations are randomly sam- pled from the unit square, while node demands are randomly generated integers from the interval [1. 10]. Following Kool et al. (2018), the vehicle capacity depends on the problem size: capacity of 50 for a problem size of I00, 80 for 200, 100 for 500, and capacity of 250 for problems with 1000 nodes.
Instance features:
Remaining vehicle capacity
Node features:
Origin/destination tokens, demand Distance between nodes
Edge features:
Oracle:
LKH
Objective:
Minimize traveled distance
Action:
Select a node, with direct edge or via-depot
Trajectory:
Nodes ordered by solution subtour. Subtours ordered by their final remaining capacity in descending order
F.2 CAPACITATED VEHICLE ROUTING PROBLEM WITH TIME WINDOWS
The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) an extension of the CVRP. In addition to demand constraints, each customer also has a specified time window during which they can be visited, along with the necessary service time required for serving that customer. The objective of the CVRPTW is to find routes for the vehicles that satisfy the capacity limits, deliver goods within the specified time windows, and minimize the total travel and waiting time or the number of vehicles used. In our experiments, we consider the standard version of the Euclidean problem where total traveling and serving time should be minimized and we use it for training GOAL.
Data generation. For the time windows and service times, we use a similar procedure to Falkner & Schmidt-Thieme (2020), where the locations are sampled sampled from the unit square. We ensure the feasibility of the resulting instances by sampling time windows using a more refined procedure. Windows start time values are sampled from the range (0.01, 0.25). It's important note that start times do not directly impact problem feasibility, as vehicles can wait at the node until the service starts. On the other hand, the choice of the visiting end time has an impact is unfeasible if the window end time of customer is less than the travel time from the depot plus the service time. To avoid this, end times are sampled from the interval (max(window start time, travel time from depot) 2 x service time, max(window) start time, travel time from depot) 4 x service time].
feasibility. An instance
Instance features: Remaining vehicle capacity, current time
Node features: Origin/destination tokens, demand, start time window, end time window,
service time
Edge features:
Distance between nodes HGS
Oracle:
Objective:
Minimize traveled time
19

---

Published as a conference paper at ICLR 2025
Action:
Select node, with direct edge via-depot Nodes ordered by a solution subtour. Subtours are ordered by their final remaining capacity in descending order
Trajectory:
F.3
JOB SHOP SCHEDULING PROBLEM
The Job Shop Scheduling Problem (JSSP) is classic scheduling problem. We are given N jobs and ma- chines. Each job consists of a sequence of operations that need to be processed in a specific order (implying prece- dence constraints). Each operation has given processing time. Each machine can only process one operation at time and when an operation started it cannot be inter- rupted (no preemption). A solution schedule, defined by the start time of each operation such that specific criterion, such makespan, total completion time, total tardiness minimized.
Data generation. We follow the standard procedure for generating JSSP benchmark datasets: ecution times are randomly sampled from (1, 100).
Instance features: None
Node features:
Operation execution time, job availability time, machine availability time Precedence constraint, operation-machine machine dependency
Edge features:
Oracle:
ORTools
Objective:
Minimize makespan
Action:
Select an operation
Trajectory:
Tasks ordered by minimal finishing time
F.4 KNAPSACK PROBLEM
The Knapsack Problem (KP) is well-known combinatorial optimization problem that involves selecting subset of items from a given set. Each item had weight and value, and the goal is to maximize the cumulated value of selected items, without exceeding given cumulated weight threshold, known as the knapsack's (weight) capacity.
Data generation. Following the same procedure as in Kwon al. (2020), node weights and values are randomly sampled from the unit interval, and knapsack capacity is set to 25.
Instance features:
Remaining knapsack capacity Value, weight
Node features:
Edge features:
None
Oracle:
ORTools
Objective:
Maximizing packed values
Action:
Select an item
Trajectory:
There is order
F.5
MAXIMUM INDEPENDENT SET PROBLEM
In the Maximum Independent Set (MIS), undirected graph G (V, E) and the goal is to find sub- of nodes S V of maximal size [S] such that each pair of nodes in S not connected by an edge. In other words, the maximum independent set is the largest pos- sible independent set in G. i.e., an independent set with the maximum number of vertices. In our experiments, fine-tune GOAL to MIS problem.
given
Data generation. For this problem, we follow a similar procedure as in Khalil al. (2017). We generate random
20

---

Published as a conference paper at ICLR 2025
graphs by using Erdös- model with the critical edge probability sampled from [0.05, 0.15].
Instance features: None
Node features:
None
Edge features:
Adjacency value (0-1)
Oracle:
VV
Objective:
Maximize number of selected nodes
Action:
Select an node
Trajectory:
There is no order
F.6
MAXIMUM COVERAGE LOCATION PROBLEM
In the Maximum Coverage Location Problem (MCLP), given
of locations with associated weights and several facilities with associated radius of coverage. The goal is to find the optimal placement of the facilities, a subset of the locations, to maximize the number of covered locations. There is also variant in which nodes have associated weights; in this case, the objective is to maximize the sum of the weights of the covered locations. In our experiments, we fine-tune our multitask model to MCLP
Data generation. Node locations randomly sam- pled from the unit square, the number of facilities is fixed to 10 and their radius of coverage to 0.1.
Instance features:
Number of facilities, radius of coverage
Node features:
None
Edge features:
Distance between nodes
Oracle:
Pu
Objective:
Maximize the number of covered locations
Action:
Select an facility node
Trajectory:
There is no order
F.7
MINIMUM VERTEX COVER PROBLEM
The goal of the Minimum Vertex Cover Problem (MVC) to find the smallest set of vertices in graph, such that each edge is incident to at least one of these vertices. In the weighted version of this problem (MWVC), each vertex has an associated weight, and the goal to select vertices with minimum cumulated sum of weights while satisfying the vertex cover condition. Data generation and problem features are the same as in MIS. We use MVC to train our model.
F.8
OPEN SHOP SCHEDULING PROBLEM
The Open Shop Scheduling Problem (OSSP) a schedul- ing problem in which set of jobs (with a given set of operations) must be processed on set of machines, but unlike job shop scheduling, there is no predefined order. Each operation must be processed, with no overlapping between operations and machines at the same time unit. The goal is typically to minimize the makespan, or the total time required to complete all jobs. Data generation and problem features are the same as in JSSP, except OSSP does not have precedence constraints.
Wedked
#00390
Wedled
102301
Naciio
700
21

---

Published as a conference paper at ICLR 2025
F.9 OPEN VEHICLE ROUTING PROBLEM
Open Vehicle Routing Problem (OCVRP) is a variant of CVRP where unbounded fleet of vehicles is available at the depot, each serving a set of customers. In con- trast with other CVRP variants, vehicles do not need to return to the depot at the end of their service. This makes OCVRP similar the classical CVRP, both problems involve set of locations with demand and vehicle ca- pacity constraints. However, the key difference lies in the route structure: in OCVRP, vehicles do not need to return to the depot after completing deliveries, which af- fects the solution space and cost minimization strategy. OCVRP has common applications in logistics, where de- livery trucks do not need return the depot after com- pleting deliveries. Data generation and problem features are the same as for the CVRP. our experiments, handle the Euclidean version of the OCVRP and fine-tune GOAL solve
F.10 ORIENTEERING PROBLEM
The Orienteering Problem (OP) is combinatorial opti- mization problem that combines aspects of the Traveling Salesman Problem (TSP) and the Knapsack Problem. It is commonly used routing and scheduling applications where the goal is to maximize collected rewards while re- specting a constraint on total travel distance or time. The OP is defined by set of locations (nodes), each associ- ated with a reward; a starting location and an ending loca- tion (usually the same node); travel cost matrix between locations; and a maximum allowable travel budget. The objective to visit subset of locations that maximizes the total collected reward while ensuring the total travel cost does not exceed the budget.
Data generation. We generated data following previous work Kool et al. (2018): node locations are uniformly sampled from the unit square and prizes are proportional the distance to the depot (in Kool et al. (2018) this variant of the problem is called O Oddistonce). The maximal distance constraint is set to 4. We use Euclidean OP for training GOAL.
Instance features: Remaining distance
Node features:
Origin/destination tokens, prize
Edge features:
Distance between nodes
Oracle:
A4OP
Objective:
Maximize collected prizes
Action:
Select node (including coming back the depot)
Trajectory: Ordered nodes by a solution tour
F.11
PRICE COLLECTION TRAVELING SALESMAN PROBLEM
The Prize-Collecting Traveling Salesman Problem (PCTSP) is a variant of the classic Traveling Salesman Problem. the PCTSP, each node has an associated prize and penalty, and the goal is to minimize the traveled distance while satisfying a minimum total prize constraint. Unlike the traditional TSP, where all cities must be visited, the PCTSP allows for skipping some nodes; however, unvisited nodes incur penalty, creating a trade-off between collecting prizes and minimizing travel distance. The final objective is minimize the
22

---

Published as a conference paper at ICLR 2025
of the traveled distance and the sum of the penalties for unvisited nodes.
Data generation. We generated data following previ- ous work Xin et al. (2021): node locations are uniformly sampled from the unit square, while prizes are randomly sampled from (0, num - nodes) and penalties are sampled from U [0 num nom--noess) Both features are normalized by multiplying by 4/num nodes and 12/ 22/num- -odes, respectively.
Instance features:
Remaining prize constraint
Node features:
Origin/destination tokens, prize, penalty
Edge features:
Distance between nodes
Oracle:
ORTools
Objective:
Minimize the sum traveled distances and penalties of univisited nodes
Action:
Select node (including coming back to the depot)
Trajectory:
Ordered nodes by a solution tour
F.12 SEQUENTIAL ORDERING PROBLEM
The Sequential Ordering Problem (SOP) combinatorial optimization problem where a set of tasks nodes must be visited in specific order while minimizing the total travel cost distance. This problem can be modeled as the Traveling Salesman Problem, with precedence constraints. The objective is to find the shortest possible route that satisfies these precedence conditions. In experiments, we fine-tune our multitask model to SOP.
Data generation. The values of the cost matrix are integers randomly generated from uniform distribution U[L, 1000] with zero costs between the same task. To fulfill feasibility constraints, randomly order the tasks, and for the i-th task, we randomly add precedent jobs, where & is sampled from U j0, [e/2]]-
Instance features: None
Node features:
Origin token
Edge features:
Distance between nodes, precedence constraint
Oracle:
LKH
Objective:
Minimize cost
Action:
Select a node
Trajectory: Ordered nodes by a solution tour
F.13
TRAVELING REPAIRMAN PROBLEM
The Traveling Repairman Problem (TRP) combina- torial optimization problem where repairman must de- termine the most efficient route to visit set of locations, performing repairs or services each site. In the Travel- ing Repairman Problem, a set of locations is given with the time needed to travel between any pair of locations. Each location has a task to be performed by the repair- man. The objective of the problem to find the route that minimizes the sum of the delays for reaching each point. In our experiments, we fine-tune GOAL to Eu- clidean TRP.
Data generation. Node locations are uniformly sam- pled from the unit square.
Instance features: None
Node features:
Origin token
Edge features:
Distance between nodes
Oracle:
LKH
23

---

Published as a conference paper at ICLR 2025
Objective:
Minimize waiting time of all nodes
Action:
Select a node
Trajectory:
Ordered nodes by solution tour
F.14
TRAVELING SALESMAN PROBLEM
The Traveling Salesman Problem (TSP) is a classic com- binatorial optimization problem. The objective of the TSP is to find the shortest possible route that a salesman can take visit a given set of cities exactly once and turn to its starting point. In the path-TSP variant, the ori- gin and destination of the salesman are distinct nodes (but may have the same coordinates, so that the TSP is spe- cial case of the path-TSP). TSP instance can be repre- sented either by node coordinates or by distance matrix. The majority of NCO models address TSP in the coordi- nate setting, yet the matrix setting holds greater signifi- cance for practical applications, as it applies beyond the Euclidean context, where the matrix energy, or cost, rather than distance, and need not satisfy the symmetry property of a distance ma- trix. In work, the Asymmetric TSP (where the distances satisfy the triangular inequality property) to train our multi-task model."
represent time,
Data generation For the Euclidean case, generate datasets described in Kool et al. (2018): points are uniformly sampled from the unit square, and the corresponding distance matrix A 18 com- puted. For non-Fuclidean problems (ATSP) we generate data described in Kwon al. (021) where distance matrices are generated randomly, but post-processed to satisfy the triangular iequal- ity.
Instance features: None
Node features:
Origin/destination tokens
Edge features:
Distance between nodes
Oracle:
Concorde (for Euclidean) and LKH (for non-Euclidean)
Objective:
Minimize tour length
Action:
Select node
Trajectory:
Ordered nodes by solution tour
F.15 UNRELATED MACIINE SCHEDULING PROBLEM
The Unrelated Machine Scheduling Problem (UMSP) is an optimization problem in operations research where set of jobs must be assigned to a set of machines, each with different processing times for each job, to minimize a specific criterion, such as makespan, total completion time, total tardiness. Unlike related machine schedul- ing. where machines have similar characteristics and pro- cessing times proportional, in UMSP, the performance and efficiency of machines vary, making a more complex and challenging problem to solve. HHrowitz & Sahni (1976) shows that this problem is NP-hard. We use UMSP for multitask training of our GOAL model.
Data generation.
For UMSP, the processing times are randomly generated from U(1, 100).
Instance features: None
Node features:
Machine availability times
Edge features:
Execution times
Oracle:
ORTools
Objective:
Minimize makespan
Action:
Select a machine to randomly selected task
Trajectory:
Ordered tasks by execution time
24


Reviews:
[{"review_id": "QoUVo9CDyc", "reviewer": "Reviewer_5MgC", "summary": "This paper introduces a generalist model designed to address various combinatorial optimization problems. Unlike traditional machine learning approaches, which require a specialized and separately trained model for each problem, this method utilizes a shared backbone network with lightweight, problem-specific adapters for input and output processing. The backbone incorporates mixed-attention blocks that accommodate different combinations of node, edge, and instance-level features, while a multi-type Transformer architecture handles heterogeneous node and edge types. Experiments show that this method performs nearly as well as specialized models in a multi-task setting across diverse problems and demonstrates strong transfer learning capabilities, adapting effectively to new problems through fine-tuning.", "questions": "（1）Please address the issues raised in the weaknesses section.\n\n（2）The paper assumes that solving strategies for various combinatorial optimization problems share common knowledge. How can it be proven that such knowledge exists, and how can the overlap of this knowledge across different combinatorial optimization problems be demonstrated?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "（1）The paper is novel , as it designs a multi-task learning approach to solve various combinatorial optimization problems through an end-to-end model. The authors developed a mixed-attention block to effectively achieve this objective.\n\n（2）The paper is well-organized, concisely written, and has good readability.\n\n（3）This paper demonstrates substantial work, conducting experiments on various combinatorial optimization problems and showcasing the effectiveness of the proposed method in terms of solution quality and speed.", "weaknesses": "（1）The description of dimension transformations and the learning process of the model is not very illustrative. It is recommended to add figure and text to enhance the explanation.\n\n（2）In Table 1, only one problem size is tested, and it is relatively small. It is recommended to include experiments with larger problem sizes.\n\n（3）The paper lacks a theoretical analysis of the method's effectiveness, and it is recommended to include this section.\n\n（4）There are few effective baselines in Table 1. For ATSP, CVRPTW, OP, KP, MVC, and JSSP, there is only one or two baselines, and UMSP lacks an NCO baseline, which weakens the convincing power. It is recommended to add more baselines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BRY9bmKV59", "reviewer": "Reviewer_QzXG", "summary": "This paper presents a new transformer-like architecture, named GOAL, for general types of combinatorial optimization training. GOAL is an auto-regressive model with a shared architecture across different problem types with specialized input and output layers for each problem. This architecture learns a generalizable rule that solves different COs and can generalize to new problems by fine-tuning. Experiment result shows that GOAL could be comparative or outperform problem-specific state-of-the-arts (greedy version).", "questions": "The following questions should not be considered as \"weaknesses\", but I believe are worth discussing:\n* What is the parameter size of GOAL and how does it compare to other peer methods?\n* How to implement the post-processing step (such as MCTS, 2-opt search) that has been proven to be prominent for neural network CO solvers?\n* For problems where there could be different ways of defining nodes and edges, how will different node and edge definitions affect the solver's performance?\n* To what extent does the current version of GOAL scale up to larger-sized problems?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "* A generalized combinatorial optimization solver is favored by the research community.\n* The proposed GOAL transformer architecture seems interesting and promising, especially given the fact that it outperforms other neural networks when trained for a specific problem.\n* The generalized training and fine-tuning result seems sound and promising. The greedy version of GOAL is comparative to other greddy peer methods.", "weaknesses": "Some important details are missing in this paper:\n* What are the implementation details of the \"codebook\"? Please specify\n* Definitions of  BQ-MDP and tail-recursive are needed in the main text to make this paper self-contained.\n\nMisc:\n* The first paragraph is too long\n* There are multiple misuses of \\citep and \\citet in this paper. For example, In L112, please use \\citet for Khalil et al., 2017. In L116, please use \\citep for Kool et al. (2019). Please proofread and fix all the misusages\n* If the oracle solver is not an optimal solver, the results should not be claimed as \"optimal gap\" in Table 1", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8WG4im9xgP", "reviewer": "Reviewer_vjMs", "summary": "The paper studies the problem of training a joint multi-task model on multiple combinatorial optimization tasks (COP). \nTo this end, the GOAL architecture is proposed. This (graph) transformer architecture learns a shared transformer backbone that is shared across COPs. It further maintains COP-specific adaptors that are applied before and after the backbone.\nThe experiments show that the model trained on multiple tasks is competitive and yields slightly worse than single-task models of the same architecture. It is further shown that fine-tuning a pretrained multi-task model to new tasks yields significantly faster convergence than training a single-task model from scratch.", "questions": "* How exactly does the proposed multi-type architecture improve performance? (see Weakness section)\n* Considering that the multi-task architecture performs slightly worse than the single-task models, have the authors considered using some multi-task learning techniques (GradNorm, etc...) to potentially close this gap? \n* For the fine-tuning experiments, how different would the performance be if one freezes the backbone and only trains the adaptors?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "* The problem of multi-task pretraining on multiple CO problems is novel and interesting.\n* The main experiments are fairly comprehensive and consider a wide range of problems.\n* The reported results are promising and suggest that pretraining can significantly improve convergence speed when fine-tuning for a new problem.", "weaknesses": "I am skeptical about the architecture design for multi-type problems, which is why I currently rate this work as a borderline reject. If I understand correctly, two changes are made when working on a multi-type problem:\n1. Multiple adaptors are learned, one for each node type (and edge type), respectively.\n2. The same backbone model is applied separately to each type and each node type now applies the attention module twice: once to self-attend to other nodes of the same type and a second time to cross-attend to nodes of other types.\n\nThe first modification seems useful to map the features of each type to different positions in the latent space. However, it is not clear to me why the second change is helpful. Is this superior to applying the single-type backbone to embeddings produced by heterogeneous adaptors? If so, why? The ablation study seems to combine both changes at once, so the individual contribution of either modification is not demonstrated.\n\nI also think the illustration of the multi-type mechanism in Figure 1 is a bit misleading as it suggests that the output of the self-attention is passed as input to the cross-attention. However, the source code applies both operations in parallel and sums the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DmgpntH9sO", "reviewer": "Reviewer_vQUg", "summary": "The paper introduces GOAL, a generalist machine learning model for solving various combinatorial optimization problems. It uses a single backbone model with lightweight problem-specific adapters and shows strong performance in solving multiple optimization tasks. The model also exhibits efficient transfer learning capabilities.", "questions": "- The mixed attention works similar to MatNet. So why MatNet cannot be run on ATSP500 or larger, but GOAL can? Another question, why GOAL outperforms MatNet, which parts of GOAL contribute to the improvement?", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Writing is easy to follow. Motivation makes sense. Experiments are sufficient. \n\nThe paper gives an interesting trial on the multi-task neural CO solver with a common encoder and task-specific adaptor.", "weaknesses": "## Contributions\n\n- Contributions can be over claimed. Authors claim that it is ``the first model that solves such a variety of CO problems.'' As I know, [1] proposes a multi-task solver where encoders for different tasks share a common part, just like GOAL. So GOAL might not be the first one. Many other works e.g. [2] also have a similar idea. So, the idea of a multi-task solver may not be that new.\n\n[1] Efficient training of multi-task combinarotial neural solver with multi-armed bandits. arXiv preprint arXiv:2305.06361, 2023.\n\n[2] Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalization\n\n- The contribution to the foundational neural model for CO appears to be somewhat limited, as it seems to utilize the same neural network architecture (mixed attention) as MatNet. \n\n## Experiments \n\n- The running efficiency is not competent compared with other methods, as shown by Table 1 and 2. In ATSP and CVPR, it may take several more times of the running time compared with other methods (AM, MatNet, MDAM, etc.)\n\n- There is still a significant gap between GOAL and the optimal solutions as shown in Table 1 and 2. Though it is understandable that some heuristics can be simultaneously fast and effective, the gap between GOAL and the best solver may make GOAL useless in solving real-world problems. Such a gap may also suggest that the time of ``general solvers'' has not yet arrived, and more efforts should be paid on task-specific models.\n\n- Since GAOL adopts a similar neural networks as MatNet, the experimental results may not be that convincing. MatNet is trained on i.i.d. ATSP data, while GOAL is trained on multi-problem data. Given the same (or close) model capacity, how and why does it happen that MatNet performs worse than GOAL? Is it because that MatNet is trained with less epochs and does not converge completely? It looks quite unusual and requires a more detailed analysis and explanation.\n\n## Theoretical analysis\n\n- The neural network of mixed attention has a fatal flaw. The dimension of the node feature $x$ is $ N \\times F_t$. When there are no explicit node features, $x$ is initialized as a one-hot vector. That is to say, in this case, the scale of the problem $N$ that the model can handle cannot exceed $F_t$, otherwise there would be a reuse of one-hot vectors. It appears that the model's generalization is severely compromised when $ N > F_t$, and the authors have not analyzed this situation. \n\n- Though the method empirically works, there is still a lack of necessary theoretical explanations that why the method has the ability to generalize to instances of a larger scale while other baselines do not have such an ability. Also, there lacks comprehensive analysis over the method's multi-problem solving ability and how the model balances the weights during the learning process for different problems simultaneously to make the model performs best on average.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)