UniCO: On Unified Combinatorial Optimization via Problem Reduction to Matrix-Encoded General TSP
Authors: Wenzheng Pan
Hao Xiong
Jiale Ma
Wentao Zhao
Yang Li
Junchi Yan
Venue: ICLR 2025 Poster (2025)
Keywords: Travelling Salesman Problem
Neural Combinatorial Optimization
Primary area: learning on graphs and other geometries & topologies

Abstract: Various neural solvers have been devised for combinatorial optimization (CO), which are often tailored for specific problem types, e.g., TSP, CVRP and SAT, etc. Yet, it remains an open question how to achieve universality regarding problem representing and learning with a general framework. This paper first proposes **UniCO**, to unify a set of CO problems by reducing them into the *general* TSP form featured by distance matrices. The applicability of this strategy depends on the efficiency of the problem reduction and solution transition procedures, which we show that at least ATSP, HCP, and SAT are readily feasible. The hope is to allow for the effective and even simultaneous use of as many types of CO instances as possible to train a neural TSP solver, and optionally finetune it for specific problem types. In particular, unlike the prevalent TSP benchmarks based on Euclidean instances with 2-D coordinates, our studied domain of TSP could involve non-metric, asymmetric or discrete distances without explicit node coordinates, which is much less explored in TSP literature while poses new intellectual challenges. Along this direction, we devise two neural TSP solvers with and without supervision to conquer such matrix-formulated input, respectively: 1) **MatPOENet** and 2) **MatDIFFNet**. The former is a reinforcement learning-based sequential model with pseudo one-hot embedding (POE) scheme; and the latter is a Diffusion-based generative model with the mix-noised reference mapping scheme. Experiments on ATSP, 2DTSP, HCP- and SAT-distributed general TSPs show the strong ability towards arbitrary matrix-encoded TSP with structure and size variation.

Published as a conference paper at ICLR 2025
UNICO: ON UNIFIED COMBINATORIAL OPTIMIZATION VIA PROBLEM REDUCTION TO MATRIX-ENCODED GEN-
ERAL TSP
Wenzheng Pan', Hao Xiong', Jiale Ma, Wentao Zhao, Yang Li, Junchi Yan" Sch. of Computer Science & Sch. of Artificial Intelligence, Shanghai Jiao Tong University {pwz1121, taxuexh, heatingman permanent, yang- Lly, yaniuncniuui (ss ftu.ttueeee edu, en Code: https: htt///gtttuuuu www.coo.//ii.cctet.. abb www.sst//nnicc
ABSTRACT
Various neural solvers have been devised for combinatorial optimization (CO), which are often tailored for specific problem types, e.g. TSP, CVRP and SAT, etc. Yet, it remains open question how achieve universality regarding problem representing and learning with general framework. This paper first proposes UniCO, unify set of CO problems by reducing them into the general TSP form featured by distance matrices. The applicability of this strategy depends on the efficiency of the problem reduction and solution transition procedures, which we show that at least ATSP, HCP, and SAT are readily feasible. The hope is to allow for the effective and even simultaneous use of as many types of CO instances as possible train neural TSP solver, and optionally finetune it for specific problem types. In particular, unlike the prevalent TSP benchmarks based on Euclidean instances with 2-D coordinates, metric, asymmetric or discrete distances without explicit node coordinates, which is much less explored in TSP literature while poses intellectual challenges. Along this direction, we devise two neural TSP solvers with and without supervision conquer such foruul-f input, respectively: MatDIFFNet. The former is a reinforcement learning- based sequential model with pseudo one-hot embedding (POE) scheme; and the latter is a Diffusion-bass based generative model with the mix mix-noised reference mapping scheme. Experiments on ATSP, 2DTSP, HCP- and SAT-distributed general TSPs show the strong ability towards arbitrary matrix-encoded TSP with structure and size variation.
studied domain of TSP could involve non-
MatPOENet and 2)
INTRODUCTION
Beyond heuristics, learning-buie based neural solvers have shown suc- cess in solving combinatorial optimization (CO) problems. While designing neural solvers for a specific type, e.g., TSP, has been a popular pursuit (Khalil et al., 2017; Vinyals et al., 2015), yet such a problem type-specific paradigm can be restrictive in real-world with immense problem diversity, which prompts the following question:
NP-Complete
NP-Hard
General TSP
RCP
Eucliden
Asymmetric
Non-metric
Birary
Can we develop general framework capable of learning a range of CO problems on graph in a unified manner?
Reskay
Selee
In this paper, we resort to utilizing problem reduction, namely transformation between different problem types which is in fact largely neglected by previous research. By the theory of computa- tional complexity, any NP problem can be transformed (or in a more professional terminology, reduced) into an NP-Complete (NPC) problem in polynomial time, and every NP problem can be reduced to an NP-hard problem in polynomial time (Lewis, 1983; Van Leeuwen, 1991). The famous Karp's 21 NPC problems (Karp, 1972) exemplify the polynomial-tin
Figure 1: CO problems and the polynomial- reduction. HCP, 3SAT and SAT are used as case studies in this paper.
reduction between 21 NPC CO problems.
* *Corresponding author, who is also affiliated with Shanghai Innovation Institute. *Fqual contribution, in alphabetical order of the last name. This work was partly supported by NSFC (92370201, 62222607).

---

Published as a conference paper at ICLR 2025
Table 1: Comparison of different current works with the key word "multi-task solver". Refer to Table 6 in Appendix B.4 for a more thorough comparison of recent related works.
ASP
MAB MIL (Wong Yo, 2013)
MVMot: (Zhon 20210)
2021y
(Wang 2004)
(Chrs)
Applicablle Proflems
Exolusted Problens
PFSP
2DTSR CVRP
CVRR OP KP
VRT
(poblem
2D7SP, DECP, SSAT TSP)
Mulli-
NIA [no volver proposed)
Lamised to VRP corianis
Multi Scale
Single
Seiver Type
Quodratc Programming
Exaltated ML.-hased ones
Mi--bored
ML hased
ML based
Echance PISP solving via
A model rproblem agaostic training tramewori to improve peneralizahilny
A maln cask zeurai solver specific problemss via multi armedd bondirs
A multi vasiam VRP solver with hierarciical goring mechanism
neural CD tramework with two solvers for problens reducible geteral TTP
Bridf Deseription
knowleegge trandtrring beeween sinilar instances
Specifically, by introducing the general Traveling Salesman Problem (general TSP, see Def. 1) as the reduction endpoint, one can construct problem reduction tree as shown in Fig. 1, suggesting the potential of training a general TSP solver to tackle problems within the reduction tree. While theoretically, other NP-hard problems, e.g., mixed integer linear programming (MILP), could also serve as the reduction endpoint (Zhang et al., 2023), TSP has already fostered extensive research attention in neural solvers in recent literature (U et al., 2021). In fact, existing machine learning research on (end-to-end) MILP neural networks are sill limited (Zhang et al., 2023), compared with the emerging progress in neural TSP (Li al., 2023b; Ye et al., 2024b; Drakulic al., 2023) solvers.
In the context of developing general neural TSP solver for various CO problems as discussed above, the reduced TSP instances fact can be represented by an arbitrary distance matrix in both its size as well as its elementary value, far beyond the popular 2D points form (Kwon et al., 2020) in the well-studied Euclidean space. In another word, it can be no longer a metric space and the distance may break the triangular inequality. Currently, Transformer (Vaswani et al., 2017) and graph neural network (GNN) have become popular backbones for neural TSP solvers (Joshi et al., 2019; Kool et al., 2018) where the 2D coordinates of the points are often used as node features, which constraints the research scope of the TSP world. For the general TSP with arbitrary matrix as input, it is technically nontrivial to achieve effective featuring of the problem instances with only pair-wise relationships and have non-deterministic node numbers (Joshi et al., 2020). To address such challenges, this paper proposes novel framework called UniCO and two corresponding neural solvers (MatPOENet and MatDIFFNet) that innovatively improves prevalent Transformer and Diffusion models as matrix encoder for general TSP learning and solving. Our contributions can be summarised as follows:
We conceptualize UniCO, namely Unified Combinatorial Optimization learning framework, lever- aging the rich expressivity of general TSP with arbitrary positive-valued matrix for unified rep- resentation of multiple CO problems (where reducible). We also construct standard datasets benchmarking the under-explored capacity of the general TSP world accordingly. This practice, to our best knowledge, has not been performed, especially in the context of machine learning for CO. We propose MatPOENet, namely Matrix encoding Network with Pseudo One-hot Embedding, reinforced Transformer- based model which utilizes a novel size-agnostic node embedding to aid instance input, thereby significantly improving model scalability and performance of general TSP. We propose MatDIF namely Matrix encoding Diffusson Network, a supervised diffusion- based model which leverages novel mix-noised reference map module, thus extending the promising ability of generative model for Euclidean TSP solving to matrix-formulate general TSP. We instantiate UniCO with the above two proposed neural backbones and one more existing method, DIMES, and conduct experiments on general TSP with four types of CO problem distributions, i.e., ATSP, 2DTSP, DHCP, and ASA Experiments show that measuring either the average TSP tour length or the average rate that solvers find optimal solutions for decisive tasks, our best best-performing methods beat compared neural approaches, and outperform the strong heuristic LKH in some cases.
RELATED WORKS
Multi-Task CO Solvers. To the best of our knowledge, this the first work that combines neurally matrix-encoded general TSP solver and unified multi-task CO learning. While similar concepts, e.g.. "multi-task solver", "universal solver", etc., have also appeared in recent literature, they often denote quite different approaches and functionalities. For example, MTCO (Li & Liu, 2023) devises "multi-task" CO framework which measures the similarity between CO problems, and then transfers knowledge between similar instances within the same problem type gain search speed-ups in its quadratic programming solver. However, it solely focuses on the permutation flowshop scheduling problem (PFSP) and is not specifically designed for seaming-basedd neural solvers, making the
2

---

Published as a conference paper at ICLR 2025
Problems
Differest problems Different scales
General TSP Neural Solver
Cost Matrices
Output Tours
Solutions
TSP: the shortost your custence
Nam-xcii, apunnctic
Euciakos
Humilonnian the Hamilaatin eycle SAT snisfishlity & voluos varables
HCP
SAT (ty 1oy
a) Problem reduction to general TSP
b) Problem solving
c) Resull mansformmtionn
Figure 2: The 3-step workflow of the UniCO learning framework.
term "multi-task" in its title misleading from a learning perspective and irrelevant to the theme of this paper. ASP (Wang al., 2024) proposes "universal" framework to address generalization issues of neural CO solvers with moodel-/problem--anooiicc training policy. However, no specific new solver is proposed, which we believe is technically nontrivial to deal with different problems. MAB-MTL (Wang & Yu. 2023) proposes a multi-armed bandit framework to train a neural solver with a shared encoder but different header and decoder. Yet, as the header and decoder necessitate customized designs for specific problems, the solver cannot be readily applied to unseen problems beyond its four training tasks. GCNCO (Li et al., 2025a) builds upon the similar header-encoder- decoder structure yet additionally enforces the consistency of the optimization trajectories across different problems to promote learning generalizable strategies corresponding to the shared structure among different CO problems. MVMoE (Zhou et al., 2024) proposes a "multi-task" vehicle routing solver with mixture-ot offiree---xppptrtt and a hierarchical gating mechanism to enhance the model capacity with good computational complexity. However, its applicable problems also limited to variants of VRPs. Table outlines the disparities between representative existing works and ours, highlighting the uniqueness and novelty of our work. More recent works like MTNCO (Liu et al., 2024), UNCO (Jiang et al., 2024), and GOAL (Drakulic et al., 2024), etc., are discussed in Appendix B.4.
General TSP Solvers. Besides traditional solvers and heuristics, neural methods for TSP with 2D coordinates have been well studied in literature (Kool et al., 2018; Kwon et al., 2020; Qiu et al., 2022; Sun & Yang. 2023; Li al., 2023b; 2024; Xin et al., 2021), systematically discussed in Li et al. (2025b). However, neural solvers for general TSP are much more challenging due to a lack of effective and scalable neural networks to handle the pairwise distance information. To our best knowledge, few works have demonstrated comparable capability of general TSP solving. MatNet (Kwon et al., 2021) proposes a Transformer-batt solver for asymmetric TSP (ATSP), which takes distance matrices as in- put. However, the adopted one-hot embedding has limitations in dealing with arbitrarily large matrices, and its implementation typically includes preset value of maximum size, restricting its generalization ability. BQ-NCO (Drakulic et al., 2023) proposes leveraging bisimulation quotienting to enhance out- of-distribution robustness on CO problems, which is capable of solving ATSP via Markov Decision Process (MDP) formulation. The following research lines show the potential of adaptation to general TSP solving without major revisions to the model architecture or learning paradigm. Divide-and- conquer methods (Ye et al., 2024b; Zheng al., 2024b; Luo et al., 2023) generally learn to break down a problem into sub-problems to facilitate solving, which accommodate matrix encoding models like MatNet as sub-problem solvers for general TSP solving. Non-autoregressive methods, including pre- dictive solvers (Joshi et al., 2019; Qiu et al., 2022; Min et al., 2024) and recent generative solvers (Sun & Yang, 2023; Li al., 2023b; 2024), typically utilize GNNs encode both node features (coor- dinates) and edge features (distances) for directly preidicting solutions, which can be adapted for general TSP solving with minor modifications to the node features at the cost of subpar results.
In Appendix B, we further discuss exact solvers, heuristic solvers for general TSP; auto- and non- auto-regressive neural solvers and neural-heuristic solvers for 2DTSP, divide-and-conquere methods for large routing problems, and specific solvers for other covered CO problems (HCP, SAT, etc.).
PRELIMINARIES
3.1 COVERED CO PROBLEMS
Definition (Traveling Salesman Problem (TSP)). Given a complete, directed or undirected graph without self-loops denoted by G = (V,E) (V 21, ... .N: the node set, E: the edge set) along with a cost matrix C of the shape N x N where the entry Cij is the cost for edge (i.j) E E, the
problem is to find the tour (f1, (ix) to minimize the total cost _k=1 Civin
Cigir-
3

---

Published as a conference paper at ICLR 2025
Algorithm 1 The training pipeline of UniCO.
Input: Problems (P) reduced general TSP. batch size B, a general TSP solver handling instances different scales. repeat
Select a problem from (P) and generate batch of B instances of the problem at the same scale;
Reduce the instances to general TSP instances with cost matrices (C:() 1b=1i
Train with the input instances [C(bi] 16=15
until the training of S converges;
Definition 2 (Hamiltonian Cycle Problem (HCP)). Given directed undirected graph G (V,8), the problem is to determine whether there exists a Hamiltonian cycle in G.
Definition 3 (Boolean Satisfiability Problem (SAT) conjunctive normal form (CNF)). SAT aims to determine the existence of an interpretation that satisfies a given Boolean formula. A Boolean formula in CNF is represented by a conjunction (denoted by A) of clauses that are disjunctions (denoted by V) of variables. For example, (œ1 V -w2) A (~xz) V x2 V -x3) is SAT instunce of two clauses (I1 V -I2) and (-z1 V I2 V -xxs). and three variables ø1, T2 and 23.
Special cases of TSP are defined according to the properties of the cost matrix C:
Metric. A TSP is metric if the triangle inequality, i.e., Ci + C₁K 2 Cik. holds for any different three nodes j. and k. Specially, when C is derived from coordinates in Euclidean space, the TSP is Euclidean.
Symmetric. A TSP is symmetric if Cij Cjz for all i and j: otherwise, it is asymmetric.
We use the term "general TSP" refer to TSPs either metric or non-metric, symmetric or asymmetric. For HCP, without losing generality, we mainly discuss directed HCP (DHCP) in this paper. For SAT, a special case of SAT in CNF with at most 3 variables is named as 3-Satisfiability Problem (3SAT). Note any SAT problem can be reduced to 3SAT in polynomial time (Fouh et al., 2014). Throughout this paper, for consistent representation and unified evaluation, when we mention any problem type X, we prescribe limit to its reduced general TSP formulation, i.e., differently distributed distance matrices only. Furthermore, note that a wider range of problems (e.g., VC, Clique, certain VRPs, FFSP, MIS, etc., detailed in Appendix E.2), can be dealt with by our proposed methods.
3.2 POLYNOMIAL- TIME REDUCTION OF CO TO GENERAL TSP
The reduction relations of the covered CO problems in this paper can be summarized as 3SAT Sp HCP Sp TSP (A Sp B means that the problem A can be reduced to B polynomial time). The solutions can also be transformed from TSP tour to the solution of the raw problem. The detailed illustration of instance reduction and proofs are provided in Appendix A.
METHODOLOGY
4.1 UNICO: UNIFIED CO LEARNING FRAMEWORK
As illustrated in Fig. 2. given CO instance. UniCO works in a 3-step pipeline: a) reduce the instance to a general TSP instance with a distance matrix obtained by techniques in Sec. 3.2, b) feed the distance matrix to trained general tsp solver and output a tour, and c) transform the output tour into the solution the origin problem (efficiently). To prepare the training data, we build a problem pool with CO problems of different scales that can be reduced to general TSP (see Sec. 5.1 for details). During training, we randomly fetch problems from the pool, transform them to general TSP, and treat the general CO solver training
equivalent task to train the general TSP solver. A concise pipeline is given Algorithm 1. In the main context, we propose increments to two promising architectures in solving general TSP across scales: the Transformer- MatDIFFNet, trained in the reinforcement (Williams, 1992) and supervised manner, respectively. We describe the two architectures Sec. 4.2 and Sec. 4.3. To demonstrate the general applicability of UniCO to different backbone solvers, we additionally incorporate DIMES (Qiu et al., 2022), neural model based on GNN and meta-reinforcement learning, into our UniCO framework. Details of model, training, and results of UniCO-DIMES are presented in Appendix E.
MatPOENet, and the Diffusion-basse
4.2 TRANSFORMER BASED SOLVER: MATPOENET
Overview. As is known, MatNet (Kwon et al., 2021) is the first neural solver designed for matrix encoding and asymmetric TSP. To overcome the inherent drawback that vanilla MatNet cannot scale
4

---

Published as a conference paper at ICLR 2025
Rough Sulver
Calculate POE Value
Initial Distunce Matrix
Re-permetation
POE Matrix
POE
POE: POET
POE
POE POE!
OE
OE OE
d.1) POE with N-30, d-16
d.2) POE with d-16
d.3) Vanilla OE with M(-4)-10
Figure 3: a-c) The three steps to generate the pseudo one-hot embedding (POE). d) The visualization of POE when N > d (d.1) and N < d (d.2) and one-hot embeddings (OE) (d.3), lighter blocks represent higher values. As the approximation of OE, POES in Fig. d.1) and d.2) both achieve concentrating POE pairs of high dot products near the diagonal of the dot product matrix.
to arbitrary size of input due to its fixed initial node embeddings, we propose MatPOENet, namely Matrix encoding Network with Pseudo One-hot Embedding for general TSP, which greatly improves model scalability as well as performance. MatPOENet utilizes an encoder-decoder Transformer architecture learn features of each city the TSP, and trained with deep reinforcement learning scheme (DRL). Generally, the model takes two sets of initial node embeddings ag, by and distance matrix C as input, and sequentially calculates the probability of nodes selected for the next position in the TSP tour via standard attention operations and mask indicating whether node has been visited. The model is trained using POMO (Kwon et al., 2020) by DRL. For each instance with distance C, N tours {T1,... 7. with different starting nodes are sampled to calculate the policy gradient:
N (L(T") - b(C)) Vo logpo(""|C),
VoJ(O)
= N
1=1
where L(T) is the length of tour ((C) = 1/N L(r") is a baseline method, set as the mean tour length of the N tours. Mathematical details of the model and training process is deferred to Appendix C.1 and the general network structure is correspondingly illustrated in Fig. 4. The POE technique introduced in Sec 4.2.1 is the highlight of our design, taking its effect by assigning by non-trivial position embedding to largely elevate the performance and scalability of the model.
4.2.1 PSEUDO ONE-HOT EMBEDDING
In vanilla MatNet, zero embedding and one-hot embedding is adopted for initial node embedding. However, the one-hot component is of fixed size and cannot accommodate arbitrary input matrix sizes. Thus, seek input size-agnostic encoder with dimension d, thereby dismissing the need for the one-hot embedding. As solution, we propose the Pseudo One-hot Embedding (POE) in the continuous vector space replicate the functionality of the vanilla one-hot embedding. We denote the input embedding as x; E IR where is the node index. When we are applying the model on large instances, i.e., N > means, there will unavoidably be some bias on the similarities between embeddings. So naturally, we incorporate this bias into the POE design by assigning similar embeddings nodes that are likely to be connected in the solution.
can never ensure X; X; 0, Vi / j as with the one-hot embedding. That
Specifically, the POE works by the following steps: 1) (Fig. 3 a) We transform the input cost matrix into tour, forming closed loop by rough solver. To ensure efficiency, we adopt the nearest neighbor (NN) heuristic as the rough solver, which can also be replaced by other possible choices. Subsequently, each node on the tour is assigned a position index denoted by pos ranging from 0 to N 1. 2) (Fig. 3 b): We define an even function f [- 1 - (0, 1) with an "impulse-like -ikee" shape, depicted in Fig. 3 b). The POE is then generated based on f. with empirical success found using f()) = 1/ cosh 100x). 3) (Fig. 3 c). We rotationally shift f along the tour for different positions, and generate POEs by sampling values from f. Mathematically, the i-th entry of the POE for position
2.
5

---

Published as a conference paper at ICLR 2025
pos can be given by:
f( poss
+
1
if
pos
2
N
d
2
N
d
P pos,a
(2)
pos
3
pos
if
N
d
2
N
d
The POE matrix then becomes the substitution of B in the vanilla MatNet. To visualize the similarity between POE and the original one-hot embeddings, Fig. 3 d.1-3) shows different cases of the POE and one-hot embeddings.
4.3 DIFFUSION BARESD SOLVER: MATDIFFNET
Overview. Generative methods gain considerable attention and show promising performance in TSP solving. Prominent models for the generative objective encompass variational autoencoders (VAE) (Hottung al., 2021a), diffusion models (e.g.. DIFUSCO (Sun & Yang, 2023) and T2T (Li et al., 2023b)), and consistency models (Li et al., 2024). These representative works demonstrate good feasibility and competitive results of diffusion model solving TSP in the Euclidean space. However, a robust generative backbone for general matrix-formmlated (A)TSP which finely adapts our UniCO framework has yet to be proposed. To fill this gap, we devise MatDIFFNet, namely Matrix encoding Diffusion Network for general TSP, which can also be seamlessly incorporated in our UniCO pipeline for multi-task and multi-scale unified training and solving. MatDIFFNet is inspired by and developed upon Sun & Yang (2023) and Li et al. (2023b), endeavoring to characterize a distribution of high-quality solutions for given instance, i.e., estimating p(S[C), where the solution distribution and C the distribution of distance matrix. the general framework of diffusion includes a forward noising and a reverse denoising Markov process. The noising process takes the initial solution So and progressively introduces noise generate a sequence of latent variables S.. The denoising process is learned by the model, which starts from the final latent variable ST and denoises S, each time step to generate the preceding variables S based on the instance C, eventually recovering the target data distribution. The formulation of the denoising process is expressed as pe (So:r C) ((r) I Pp C). The training optimization aims to align po(Sp) C) with the data distribution (Sa))C) using ELBO:
C - (SS Pg
C)] - log (Sp c3| +
We defer the mathematical elaboration of discrete diffusion process (derivation through Bayesian theorem, transition probability matrix, etc.) to Appendix C.2 and the general network strueture is correspondingly illustrated in Fig. 5. The adaptive scheme proposed to enable matrix-input for our generative general TSP solver is detailed in the following Sec. 4.3.1.
4.3.1 MIX-NOISED REFERENCE MAP AND DUAL FEATURE CONVOLUTION
In previous works, graph-based diffusion networks for TSP takes core inputs for the GNN encoder. One is the Euclidean 2D coordinates as initial node features, and the other is the noised reference map which forms the initial edge embedding. However, in general TSP formulation, no coordinates is available while and arbitrary distance matrix is instead provided. We endeavor to maintain the best compatibility with previous design principles, thus proposing to combine the distance matrix and the noised label matrix to obtain mix-noised reference map to replace the original x, to leverage edge information from pair-wise distances and enrich the initial edge embedding. Additionally considering the asymmetry of the distance matrix for general TSP and inspired by the scheme adopted in Kwon et al. (2021) 1), we introduce two random vectors as pseudo coordinates for both "from" " points and "to" points node inputs, which will be updated respectively in subsequent GNN aggregations.
Mix-Noised Reference Map. The fusion of distance matrix C E NNN and original noised reference map X, E IR XN is learned by multilayer perceptron (MLP) with two input nodes and a single output node and biases, conforming to that of vanilla MatNet. Mathematically, the mix-noised reference map x e IR N for the diffusion encoder can be calculated as follows. First, stack C and x, along the last dimension to gain a mixture tensor M E Nx Nx2 where N denotes the number of nodes and the batch size is omitted. Then, linear and activating operations are performed on M:
Wmixa (ReL.U (W mix1 (M)))

---

Published as a conference paper at ICLR 2025
Subsequently, x is used to compute the initial edge embedding for the GNN via sinusoidal featuring of each input element respectively:
C sin
G2 T
C
é concat
COS T
sin
COS T
sin
COS
(5)
T
T
T
where E; denotes the i-th value of the 2 entries in x d is the embedding dimension, T is large number (usually selected as 10000), concat(-) denotes concatenation.
Dual Feature Convolution. Let t Rd where de is the time feature embedding dimension. is the mix-noised reference map calculated above. As for node features, deviating from the widely used GCN model (Joshi et al., 2019) that learns single node representation, we introduce a,, E R two random generated pseudo coordinates as initial node embeddings for the asymetric nodes in general TSP, and maintain two distinct node features with two sets of learnable parameters throughout the cross-layer convolution operations:
A a'A. + ReLU(BN(WW) A. +
Σ
Ed o (
(WA2
W WB.
(6)
BB r/n + ReLUUBN(WW B. BB Σ
G (W 2
W 2 T))
(7)
j.i
11 dy + Ree.U(BN(WWL W/ Wh WB, W
(8)
a(el)) GAM o(ey) G'B.s
o(ee)))
ESn, ((e
where WA,1, WB.1... W; E Raxh denote the model weights, G denotes the dense attention map for element-wise gating. The convolution operation integrates the edge feature to accommodate the significance of edges in routing problems. The final prediction of the edge heatmap in TSP is (RR.eaeL (W)) for subsequent decoding and searching process.
H.j Softmax(norm (ReL.U(W.e,,
5 EXPERIMENTS
5.1 EXPERIMENTAL SETUP
Hardware. MatPOENet trained on an NVIDIA RTX3090 24GB GPU with AMD 3970X 32-Core CPU for N < 50, and on an RTX8000 48GB GPU with Intel Xeon W-3175X CPU for N Rs 100. MatDIFFNet is trained on 8 NVIDIA H800 80GB GPUs with Intel Xeon (Skylake, IBRS) 16-core CPU, All evaluations are conducted on a single RTX3090 GPU with AMD 3970X 32-Core CPU.
Training data generation. The train data cover four CO problems: non-metric Asymmetric TSP (ATSP), 2D Euclidean TSP (abbr. 2DTSP, metric and symmetric), Directed HCP (DHCP), and 3SAТ, all in their general TSP matrix formulation. Then we generate the training data for different problems by the following protocols: i) For ATSP, 2DTSP, and HCP, we first randomly choose the number of nodes N from [min_scale, max_scale]. Then ii) For ATSP, we generate the distance matrix C from the distribution in Uniform (0. 1) with the diagonal entries being O: iii) For 2DTSP, we assign each node a random 2D coordinate by distribution Uniform (0, 1) X Uniform( (0, 1) and then compute the Euclidean distance matrix C; iv) For DHCP, generate node sequence
,ix) by randomly permuting all the nodes and assigning C,,, = O for nodes in 7 and C.y.i = 0. thus ensuring Hamiltonian cycle in C. Then
(f1,
pick random amount of node pairs (i.j) and set C₁ = as the noise edge. Finally we set all Cūj = for the rest node pairs (i.)). v) For 3SAT, the TSP instance scale N is tied to the number of variables and clauses (Appendix A.2), so we cannot set N to an arbitrary value. We first pick a set of variable number N. and clause number No as specified in Appendix D.2 ensure that the scale of the reduced TSP instance fits different experimental scales. Finally, the instances are transformed to the general TSP form, as described in Sec. 3.2.
Testing data preparation. Due to the absence of previous work to standardize the evaluation of matrix-formatted general TSP across various problem distributions, we prepare 10K test instances for 3 scales (conforming to mainstream works of the "multi-task" concentration, see Table 6 in Appendix B.4), comprising 2,500 instances featuring each problem (ATSP, 2DTSP, HCP and 3SAT) in the matrix formulation, in pursuit of comprehensive examination across general TSP tasks.
7

---

Published as a conference paper at ICLR 2025
Table 2:
Main experimental results. Reported data for ATSP and 2DTSP are tour length. "Single"; models trained and tested on each problem respectively. "Mixed": unified models trained with a mixture of 4 tasks each scale. Asterisked (+): unified model trained with mixture of 4 tasks and 3 scales. Bold: the best result of neural solvers. Underlined: the reference results for computing
the optimality gap. Red blue boxes: ours that outperform LKH with 10K/500 trials respectively.
Time: the average time (seconds) per instance solving over each line, with batch size set to 1.
Methools
Train Data
ATSPL
2DTSPL
DHCP (LL. FR1)
3SAT (L., FRR))
Avg. L1
Avg. Gapl
Arg. FRT
Time
Gurobi
1,5399
3.847
100.00%
0.0000
100.00%
1.3424
100.00%
LKH (10000)
1.339
3,847
0.008
99.92%
0.0000
100
13426
0.01%
99.968
0.327
I.H (500)
1.349
18347
D.0066
99 445
0.3000
100.005
1 1.348
0.11%
99.72%
0.038
Nearest Neighhor
2,009
4.5021
388566
0.48%
3.0504
0.32%
3.3428
149.0254
0.40%
0.000
Scale x 20
Furthest Insertion
1,7000
3,9695
3.3136
1.76%
4,8816
0.00%
3.4679
158.34%
0.88%
0.000
MatNet
1.5871
4.2612
2,9608
1.12%
3,4722
0.56%
3,0716
128.
0.005
MatNet
Mixed
16339
3.114
0.9740
60%
3,4656
11.04%
2.4967
0919
19.528
DI00
MarNet-8x
Mixed
1,5648
3.8478
0.1936
80.92%
1.6272
1.36%
1 1,8033
34,77 14.7155 56
41. 41.14%
0.637
DIMES
Mixed
2,2335
4.1096
2.9448
2.67%
2,6660
2.12%
3,0035
123. 74%
2,39%
0.038
DIMES-AS((00)
Mixed
1,690
3,9092
0.4596
60.125%
0.2828
77.12%
1 1.5826
17.90%
68.62%
0.522
MarPOENet
Mixed
16445
3,8643
32.60%
0,4541
61
7076
27.21%
47.24%
0.006
Mixed
1.5695
3,3389
0.1760
82. 68%
0.0122
98.88%
1 39899
4.21%
90.78%
D:043
MuPOENNr--Be
Mixed
1.5506
3.3322
0.0556
94.44%
0.0008
99.92%
1.3610
1.39%
97.18%
0.043
Gurrbi
1.5545
5.6952
0,0000
100.009
0,0000
100.00%
1.8124
100.00%
0.296
LKH (10000)
1.5548
5.6053
100.00%
0,2764
1821
87.40%
0.513
I.KH (500)
1.557
5,604
0.000
100000
0.77%
1 19329
6,65%
80.90%
0:059
Nearest Neighhor
2,0455
6.9977
5.1120
0.00%
5.9872
0.00%
5,0448
178. 90%
0.00%
0.000
Farthest Insertion
18387
6.0998
4.0224
5.28%
10.3964
0.00%
5.5893
208. 39%
2.64%
0
MatNet
ATSP
1.5753
7,3618
1,4856
11 80%
8:4020
0.00%
4.7062
159 67%
5.90%
0.007
MatNet
Mixed
1,0098
0.9288
80.84%
1,1901
30.52%
2,4821
36.95%
50.68%
D.007
MatNet-Sx
1.7340
5.8664
71.52%
0.2992
73.08%
2.0513
18%
72.50%
0.064
GLOP
Single
18885
6.6499
3.7244
0.845
4,9816
0.76%
4.3111
137,87%
0.80%
0.115
Scale: N
DIMES
Mixed
2.3341
6.6271
3.1788
1.56%
5,3656
0.12%
4,3764
141.47%
0.84%
0.055
DIMES-AS(100)
Mixed
1,6920
5.9117
0.5908
16.01%
1,5830
20.14%
2:4528
35.33%
33.24%
2,016
MarPOENat-s
Single
15643
5,7042
93.52%
0.1888
81.72%
3.76%
87.62%
MaPOENd
Mixed
1688]
5.7694
0.1444
86. 202
1,3644
27.08%
2.2416
23.68%
$6.64 56.64%
0.009
MaPOENa--8s
Mixed
16417
5.7283
0.9172
98.28%
0.2456
77 60%%
1 1.90822
5.29%
87 345
0.067
MarPOFNer-B8 -8
Mixed
16285
5,7575
0.0230
97.20%
0.1172
88.44%
1 18288
3,88%
92.82%
0.067
MaDDIFFNet
Single
2,0713
5.7954
2.0992
15.32%
0.3664
98.16%
2.5031
38.11%
56.74%
0.157
MaDDIFFNa-2OrP
Single
5.7279
41.08%
0
98.64%
2,0744
14.16%
71.36%
MaDDIFFNet
Mixel
1,8385
6,2332
2,0648
15.7665
0.1112
94 68%
2.5619
41.35%
55.22%
0.155
MuIDIFNNes-2OPT
Mixed
14991
5.8619
0,8192
44.525
0.3496
05.6
2,0075
15.75%
70.08%
0.164
Gurobi
1.5661
7,7619
0,0000
100.00%
0.0000
100.00%
2 2,3320
100.00%
0.689
LKH (10000)
7.7709
100.00%
1,0008
44.50%
2.5818
10.81%
72.40%
LKH (500)
1.5704
7,8015
0.0000
100.00%
1,6656
28.08%
2.7594
18.33%
64.04%
0.095
Nearest Neighhor
2,1321
9 9.6606
5 5,4016
0.209
8.3236
0.00%
6. 3859
17%. 84%
0.10%
0.002
Farthest Insertion
19333
8.4847
3,1256
26.64%
23,5160
0.00%%
9 9.2649
297. 20%
13.32%
0.063
MatNet
ATSP
L6217
19.0514
17,8620
0.00%
40.1188
0.00%
19. 19.6667
743.34%
0.00%
0.015
Scale N' 100
MatNet
Mixed
8.2551
31 31.68%
2,040K
13.84%
3.3146
14%
22.76%
0.018
MatNet-8x
Mixed
19210
8. 8.0078
0.3640
69 607S
0,7740
50.76%
2. 2.7004
66.666
60.188
D.0MS
GLOPP
Single
1.849
8.8349
2.7850
2.00%
6.4280
0.08%
4 4.9468
113, 84%
1.04%%
0.176
DIMES
Mixed
2,5186
9.5777
3,9064
1.16%
3.8064
0.00%%
6.4018
174.52%
0.58%
0.124
DIEMS-AS(100)
Mixed
16968
8.3390
0,8480
24.00%
2,8040
7.16%
3.4220
46.74%
15.58%
8.437
MalPOENe
Mixed
1.9183
8.2967
90.78%
1,0704
2,8465
22.06%
61.30%
0:017
MaPOFENet-8
Mixed
1,8655
1.799
0.0052
99. 48%
0.24401
2:5717
10.28%
N8.30%
D.994
MuPOENer-88
Mixed
1.7607
8.0817
0.0012
99.88
0.3244
70.92%%
2.5420
9.01
$5.40%
0.095
MarDIFFNer
Single
1.9432
7.9684
4.4536
2.96%
0.3404
98 45%
3. 3.6014
$4.455 43.%
50.70%
0.103
MaDDIFFNe-2OPP
Single
1.1K6
7,8482
1.1404
37.72%
0,0240
98.60%
2,6823
15.02%
68.16%
0.112
MaDDIFFNee
1.763
8.9030
3,2524
5.68%
0.1980
90.52%
3,5564
52.501
48.10%
MaDIFFNNe-2OPF
Mixed
1.6965
S.1501
0.9148
13.04%
0.0952
91.14%
2.7217
16.711
67.24%
0.114
Metrics. Found Rate (FR): the percentage of optimal solutions found in the test instances for the decisive problems HCP and SAT. A higher found rate indicates better performance. We also report the the average FR (Avg. FR) of DHCP and 3SAT. Tour Length (L): This is the conventional metric for any TSP. The lower length indicate the better performance of the general TSP solver. We report the average tour length (Avg. L) over all the instances of different problem distributions. The average gap (Avg. Gap) is the performance drop from Gurobi w.r.t the mean tour length across the four tasks.
Compared methods. Exact solver: Gurobi. Note that the current Concorde only fits Euclidean TSP. Heuristics: LKH (500 and 10,000 trials), Nearest Neighbor, and Farthest Insertion. Neu- ral sovlers: Vanilla MatNet (Kwon et al., 2021), DIMES (Qiu et al., 2022) (Trained under UniCO. DIMES-AS(T) means tuned heatmap by T steps of active search, detailed in Appendix 1)), GLOP (Ye et al., 2024b) (using vanilla MatNet as local reviser under GLOP framework). ATSP results of BQ-NCO (Drakulic et al., 2023) and GOAL (Drakulic et al., 2024) are put in Appendix F.7 for reference only (estimated by their reported optimality gap no pre-trained checkpoints are available). MatPOENet (ours) and MatDIFFNel (ours) w/ and w/o post-inference improvements (8x parallel running for MatPOENet and 20PT for MatDIFFNet). All evaluated neural methods are re- re-trrined and tested on our unified dataset for fair comparison. Parameter settings are listed in Appendix D. I. Note that for HCP and SAT problems, previous specific models performed on totally
8

---

Published as a conference paper at ICLR 2025
Table 3: Results of both solving time and solving quality comparing Mat-X-Net (ours) and different
settings of LKH. LKH-N: LKH with runs and N max_trials. Batch size = 1.
Method
Timel
ATSPL
2DTSP]
DHCP (L.). FR1)
3SAT (L., FR1)
Avg. L.
MatPOENet
7m31s
16647
5.7283
0.0172
98.28%
0,2456
77.60%
19082
MatDIFFNet
21m48s
1.7186
5.7279
0.8324
44.08%
0.0188
98.64%
2.0744
LKH-500
9m9s
1.5557
5.6964
0.0000
100.00%
0.4796
61.80%
1,9329
N
LKH-1000
13m53s
1.5554
5.6957
0.0000
100. 100.00%
0,4160
65.68%
1.9168
L.K--10000
1h22m
1,5548
5.6953
0.0000
100.00%
0.2784
74.80%
1.8821
MatPOENet
15m35s
1.8655
8.1719
0.0052
99.48%
0,2440
77.12%
2.5717
Re 100
MaDIFFNNt
28m21s
1.7165
7.8482
1.1404
37.72%
0.0240
98.60%
2.6823
LKH-500
15m49s
1.5704
7.8015
0.0000
100.00%
1.6656
28.08%
2.7594
LKH-1000
24m39s
1.5692
7.7909
0,0000
100.00%
1.4400
32.52%
2.7000
LKH-10000
2h15m
1.5674
7.7709
0,0000
100.00%
1.0008
44.80%
2.5848
Table 4: Case study of N > d: d
= 512, d2 32 on the scale N 50.
Method
ATSPL
2DTSPJ
DHCP (LL, FR1)
3SAT(LL, FR1) || Avg. LL
MarPOENet (N <<d,)) d.)
1.6417
5.7283
0.0172
98. 28%
0.2456
77.60%
1.9082
MaPOENet (N de)
1,8799
5,9742
0.4548
60.24%
0.3292
75.56%
2.1595
different problem formulation, thus orthogonal to target of general matrix encoding TSP solving pipeline and are reasonably excluded from evaluation in this paper. Detailed clarification of this issue sincerely explained in Appendix B.6 for possible concerns.
5.2 RESULTS AND DISCUSSIONS
Main results are shown in Table 2. In the following part, RQI-RQ3 discuss the eternal topics of performance, efficiency, and scalability; RQ4 analyzes the ablations upon the POE embedding; RQ5-RQ7 introduce different applications and additional experiments based on UniCO.
Performance. MatPOENet outperforms LKH when N x 50 and 100 the average length of the full dataset. Outperforming LKH on TSP has been a pursuit by neural CO solver for long, while scarcely are there methods achieving it, let alone on the problem of general TSP. As highlighted in Table 2, on the scale N x 50, MatPOENet* achieves to outperform LKH with max_ trialls000 on the Avg. Li.., the overall performance, and on the scale N Rs 100, MatPOENer* outperforms LKH with as many trials as max ttw..aaaiaao000000 on the Avg. L metric. The competent results compared with LKH indicates that our method MatPOENet* can not only serve as a strong baseline for future research. but also becomes a current SOTA over the problem of general TSP. Diving deeper into the results, we observe that LKH performs stably well on general TSP instances in continuous data space (ATSP and 2DTSP) but is not always that good in discrete data space: It may be because of the crash of the inherent so-called meehaa-e" of LKH, which relies on the computing of minimum I-tree that is not unique in the discrete cases. We detail the observation and analyses for LKH in Appendix G.I. The discovery of LKH's crash also suggests the significance of developing neural solvers for general TSP that can work simultaneously on the instances in both continuous and discrete spaces.
RQ1:
RQ2: Efficiency. We extract the total solving time in Table for a clearer comparison. On N Rs 50 data, MatPOENet achieves better tour length (1.91 v.s. 1.93) within shorter time (7m31s v.s. 9m9s)
compared to LKH--500. More impressively, on N R 100 data, MatPOENet not only beats LKH-5000
on both run- run-time efficiency and average quality, but also show superiority in solving performance (2.57
v.s. 2.58) compared to LKH-10000 which consumes 8.7x time (15m35s v.s. 2h15 MatDIFFNet consumes more solving time for its complex inference denoising steps of diffusion, yet also reaches competitive results against LKH within similar sovling time.
RQ3: Scalability. Experiments are conducted from three aspects to show the multi-scall scale general- izability: i) MatPOENet trained on all the scales. We train an MatPOENet with training data of all the scales, denoted by MatPOENet* in Table 2. Competitive results are obtained compared to single training. demonstrating the feasibility of, and even benefits brought by multi-scale training. ii) Scale-free initializer POE on the scale N > d. In response to the motivation of designing POE in Sec. 1. we show that MatPOENet can be trained on instances at the scale N larger than the pre-set one-hot embedding dimension d, which is the case where vanilla MatNet fails. Results in the case N > d are given in Table 4. Compared with the model trained with higher d, we observe that a reduced would cause a reasonable degeneracy of model performance. iii) On larger-scaled data. In terms of solving large scaled CO problems, resorting divide-and-conquee paradigm is popular

---

Published as a conference paper at ICLR 2025
Table 5: Results on large-scaled ATSP instances.
Scale
Method
ATSP (L.))
Time
BiTSP (L.)
Time
HCP (L.)
FRT
Time
Greedy
2.146
21s
5.609
21s
5.734
0.005:
21s
IK
MatNet
2.130
1m24s
4.352
3.063
0.78%
45s
Ours
2,092
57s
0,517
40s
0,563
64.84%
41s
Greedy
9,516
4m32s
5,938
4m32s
5,438
0.00%
4m32s
10K
MatNet
9.184
23m17s
3.313
6m10s
2.750
0.005
23m22s
Ours
8,355
5m27s
0.688
5m10s
0.625
62.50%
5m40s
and proved feasible and performant (Ye et al., 2024b; Luo et al., 2024; Fu et al., 2021), where a strong solver at small-to-medium instances is still of irreplaceable importance. We readily incorporated the state-of-the-as GLOP (Ye et al., 2024b) which greatly improves MatNet's scalability. Results of the -epoweeep MatPOENet (Ours) are presented below, which can be regarded as an initial indication for the efficiency of our proposed POE at large scaled problems (128 instances for N = 1K and 16 instances for N = 10K). Note BiTSP is a direct simulation of decisive CO problems in general TSP formulation, referring to randomly generated instances that has binary distances but doese not necessarily possess a zero-length loop. A more thorough discussion of scalability and applicability issues from the view of current research status of unified NCO is deferred to Appendix G.2.
RQ4: Ablations of POE (Appendix F.1). i) MatNet v.s. MatPOENet. Main results in Table 2 validate the effectiveness of introducing POE to enhance MatNet. ii) Comparison of different initial rough solver. Results of nearest neighbor (NN), farthest insertion (FI), and an ablation without rough solvers (Non) in Table 10 show superiority of NN as the initial solver for POE. We speculate that it is because NN pays more attention to the local structure, complementing subsequent attention layers where global information are learned. iii) POE v.s. alternatives. Fixed random vectors and trainable embeddings are tested as the substitution of the proposed POE. Results in Table 11 show that our POE outperforms the other two options suggested in the paper of MatNet (Kwon et al., 2021).
RQ5: UniCO for Setraaninnn-iieetniin (Appendix F2). With MatPOENet, UniCO executes both i) cross-task and ii) cross-scale experiments for cerraining-finetunii applications. With MatDIFFNet, UniCO also trains the model in the curriculum learning manner, i.e., models larger scales are trained upon existing weights gained during training of small scaled data. Results in Appendix F.2 demonstrate applicability of UniCO as a pretraining-finetuii framework.
RQ6: UniCO for other learning paradigms and problems. (Appendix F.3 & F.4). Besides afore- mentioned methods (DRL., Generative, etc.), UniCO is also available for the mainstream supervised learning (SL) of neural heatmap for general TSP solving. We perform minimum modification to the backbone model in MaPOENee obtain a heatmap predictor via pure supervised learning. Results are provided in Appendix F.3 Also, supplementary experiments on the vertex cover problem (VC) have been conducted using UniCO. Results and discussions are in F.4. To conclude, UniCO along with our Mat-X-Nets possess good adaptability to embrace new learning paradigms and tasks.
RQ7: UniCO for standard TSP and real-world generalization (Appendix F.5 & F.6). In order to reach better alignment to previous works that focused on 2DTSP only, we have conducted experiments on the standard test set shared by a series typical works (Kool et al., 2018: Joshi et al., 2019; Min et al., 2024; Qiu et al., 2022; Li et al., 2023b; Hudson et al., 202 1), with 1280 instances each for TSP-50 and TSP-100. Also, we test MaPPOENet and MatDIFFNet on 45 selected real-world instances (N [14, 195) from the well-kown TSPLIB. Results (in Table 18, 19, 21, respectively) demonstrate that our designed networks manage to solve the conventional Euclidean TSPs without coordination as input, yielding comparable performance and capability of generalization towards distribution shifts.
6 CONCLUSION AND FUTURE WORK
Conclusion. In this paper, we first propose the UniCO framework to embed different CO problems in consistent general TSP matrix format via problem reduction. Further, we delve into the under- TSP and devise MatPOENet and MatDIFFNet as plugs-in of
explored realm of UniCO, in aid of current lack of neural capability targeting general TSP.
Limitations and Future Work. We have made an initial step towards the general neural CO solver. Future works include: i) More problems. More CO problems reducible to general TSP (Appendix E.2) shall be included for evaluation. iii Stronger capability. Gaps still exist comparing to exact solvers at specific problem solving. iii) Better scalability. MatDIFFNet has the potential to scale larger and work as a consistency model in the future (Appendix G.4).
10

---

Published as a conference paper at ICLR 2025
ETHICS STATEMENT
The methods proposed in this paper aim to improve the field of neural combinatorial optimization (NCO), especially neural solvers with better generality. A dataset comprising synthetic instances of general TSPs with different problem distributions is released to facilitate the under-studied branch of formul-- TSPs, thereby standardizing the evaluation of unified NCO solvers. To our best knowledge, no ethical issues or harmful insights of this work need to be otherwise stated.
REPRODUCIBILITY STATEMENT
The hardware and the preparation of the used data are described in Sec. 5.1. The detailed parameteri- zation and implementation of the models for training and testing are provided Appendix D. Source code and datasets can be accessed at https: //g githt......... http://iiiiaaa--T////mmam
REFERENCES
Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. Learning to solve circuit-SAT: An unsupervised differentiable approach. In International Conference on Learning Representations, 2019a.
Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. Pdp: A general neural framework for learning constraint satisfaction solvers. arXiv preprint arXiv: 1903.01900 2019b.
Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34, 2021.
Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. Neural combi- natorial optimization with reinforcement learning. In International Conference on Learning Representations, 2017.
Federico Berto, Chuanbo Hua, Junyoung Park, Minsu Kim, Hyeonah Kim, Jiwoo Son, Haeyeon Kim, Joungho Kim, and Jinkyoo Park. RL4CO: a unified reinforcement learning for combinatorial optimization library. In NeurlPS 2023 Workshop: New Frontiers in Graph Learning, 2023.
Léo Boisvert, Hélène Verhaeghe, and Quentin Cappart. Towards a generic representation of com- binatorial problems for learning-based approaches, 2024. URL https:ttttttti....a//// http://axvvvv///// 2403. 06026.
Xavier Bresson and Thomas Laurent. An experimental study of neural networks for variable graphs. ICLR workshop, 2018.
Chris Cameron, Rex Chen, Jason Hartford, and Kevin Lcyton-Brown. Predicting propositional satis- fiability via end-to-end learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3324 3331, 2020.
Xinyan Chen, Yang Li, Runzhong Wang, and Junchi Yan. Mixsatgen: Learning graph mixing for sat instance generation. In The Twelfth International Conference Learning Representations, 2024.
Paulo R O da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Sinno Jialin Pan and Masashi Sugiyama (eds.), Proceedings of The 12th Asian Conference Machine Learning, volume 129 of Proceedings of Machine Learning Research, pp. 465-480. PMLR, 18-20 Nov 2020. URL https: http:p::///pccceeee httpp/ppoccccg..eee///ee/o
www.nngssmmrr....mmmmmmm......ww mlr prwss wwwppppwssss.eeeepppppppppa a0 html.
Darko Drakulic, Soñaa Michel, Florian Mai, Araudd Sors, and Jean-Marc Andreoli. Bq-nco:
Bisimulation quotienting for efficient neural combinatorial optimization, 2023. URL https:
//aaaxivvorg//aaaaeeeeaaaa.eaaee altp///l.//////a.///// 03313.
Darko Drakulic, Sofia Michel, and Jean-Mare Andreoli. Goal: A generalist combinatorial optimiza- tion agent learner, 2024. URL https://aaree www./oor/bss..................ss 0 15079.
11

---

Published as a conference paper at ICLR 2025
Stefan Elfwing, Eiji Uchibe, and Kenji Doya. Sigmoid-weighted linear units for neural network function approximation in reinforcement learning. Neural networks, 107:3-11, 2018.
Eric Fouh, Ville Karavirta, Daniel A Breakiron, Sally Hamouda, Simin Hall, Thomas L Naps, and Clifford Shaffer. Design and architecture of an interactive etextbook-the opendsa system.
Science of computer programming, 88:22-40, 2014.
Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 7474-7482, 2021.
Wenxuan Guo, Hui-Ling Zhen, Xijun Li, Wanqian Luo, Mingxuan Yuan, Yaohui Jin, and Junchi Yan. Machine learning methods in solving the boolean satisfiability problem. Machine Intelligence Research, 2065):440-655, June 2023. ISSN 2731-5398. doi: 10. 11000//11663--22-1399222 URL
http:/ /txp/xxx////// doi. wwg/10..o/..o 1007 /0000///1111 633- 001-1116-33222236---23 022-1396-2.
LLC Gurobi Optimization. Gurobi optimizer reference manual. Gurobi, pp. 2-12, 2021.
Michael Hahsler and Kurt Hornik. Tsp-infrastructure for the traveling salesperson problem. Journal of Statistical Software, (3(2):1-21,000) 2007.
Keld Helsgaun. An extension of the lin-kernighan-helggam tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12, 2017.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models, 2020. URL
https: / arxiv..viivv org/ abs/ /206 2001/110..........
André Hottung. Bhanu Bhandari, and Kevin Tiemnyy Learning latent search space for routing problems using variational autoencoders. In International Conference on Learning Representations, 2021a.
André Hottung, Yeong-Dae Kwon, and Kevin Tiemey. Efficient active search for combinatorial optimization problems. arXiv preprint XXXv:2006.051266, 2021b.
Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. arXiv preprint arXiv:2110.05291, 2021.
Sebastian Jaszezur, Michat Euszezyk, and Henryk Michalewski. Neural heuristics for sat solving. arXiv preprint arXiv:2005. htt.::0005/33000 13406, 2020.
Xia Jiang, Yaoxin Wu, Yuan Wang, and Yingqian Zhang. Unco: Towards unifying neural combina- torial optimization through large language model, 2024. URL hwtpthttss///aiiiiaa org/ /bs/ 2408. 12214.
Chaitanya Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint 1txx:v:19060122200 2019.
Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. arXiv preprint 047554 2020.
Richard M. Karp. Reducibility among combinatorial problems. Complexity of Computer Computations: Proceedings of symposium on the Complexity of Computer Computa- tions, 1972 doi: 178-1-4660 118-1-4684-2001-2
1-117788---484-200122 9, URL httt::://doi.oggg///
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimization. Advances in Neural Information Processing Systems, 35:1936-1999, 2022.
12

---

Published as a conference paper at ICLR 2025
Minsu Kim, Sanghyeok Choi, Jiwoo Son, Hyeonah Kim, Jinkyoo Park, and Yoshua Bengio. Ant colony sampling with gflownets for combinatorial optimization. arXiv preprint arXiv:2403.07041, 2024.
DP Kingma. Adam: method for stochastic optimization. In Int Conf Learn Represent, 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 1609. 02900, 2016.
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08477 2018.
Wouter Kool, Herke van Hoof, and Max Welling. Buy 4 REINFORCE samples, get baseline for free! In Deep Reinforcement Learning Meets Structured Prediction, ICLR 2019 Workshop, New Orleans, Louisiana, United States, May 6, 2019, 2019. URL https: forum? d= 1
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic pro- gramming for vehicle routing problems. In International conference on integration of constraint programming, artificial intelligence, and operations reseurch, pp. 190-213. Springer, 2022.
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 88 21198, 2020.
Yeong-Dae Kwon, Jinho Choo, Iijoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Ma- trix encoding networks for neural combinatorial optimization. Advances in Neural Information Processing Systems, 34:5138-5149, 2021.
Harry R Lewis. Michael Tgarey and david s. johnson. computers and intractability. guide the theory of np-completeness. wh freeman and company, san tranciscol979. x+ 338 pp. The Journal of Symbolic Logic, 48(2):498-500 1983.
Peng Li and Bo Liu. Multi-task combinatorial optimization: Adaptive multi-modalit knowledge transfer by an explicit inter-task distance. arXiv preprint arXiv:2305. 2023.
Yang Li, Xinyan Chen, Wenxuan Guo, Xijun Li, Wanqian Luo, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, and Junchi Yan. Hardsatgen: Understanding the difficulty of hard sat formula generation and strong stucture-hardnesssooe SIGKDD Conference on Knowledge Discovery and Data Mining, 2023a.
baseline. In Proceedings of the 29th ACM
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. T2t: From distribution learning in training to gradient search in testing for combinatorial optimization. In Thirry-sevntth seventh Conference on Neural Information Processing Systems, 2023b. URL https://///..c.......tt /wwp//ppweeew..e/////p//. net forum? ? iid= JtFOugNMv2.
Yang Li, Jinpei Guo, Runzhong Wang, Hongyuan Zha, and Junchi Yan. Fast 12t: Optimization consistency speeds diffusion-based training-to--esting solving for combinatorial optimization. Advances in Neural Information Processing Systems, 2024.
Yang Li, Jiaxi Liu, Qitian Wu, Xiaohan Qin, and Junchi Yan. Toward learning generalized cross-problem solving strategies for combinatorial optimization, 2025a. URL https:// openreview hwt.:eet//roooe (onrummiidiii pid=//aaa/nnappaa.aaaa
Yang Li, Jiale Ma, Wenzheng Pan, Runzhong Wang, Haoyu Geng, Nianzu Yang, and Junchi Yan.
Unify ml4tsp: Drawing methodological principles for tsp and beyond from streamlined design space of learning and search. International Conference on Learning Representations, 2025b.
Zhaoyu Li and Xujie Si. Nsnet: A general neural probabilistic framework for satisfiability problems. Advances in Neural Information Processing Systems, 35:25573-25588 2022.
Fei Liu, Xi Lin, Zhenkun Wang, Qingfu Zhang, Xialiang Tong, and Mingxuan Yuan. Multi- task learning for routing problem with cross-problem zero-shot generalization, 2024. URL
https: //ttxv//.vvvv.// org/abs......oooo......ooaa abtp//2/s22222... 2402 6891.
13

---

Published as a conference paper at ICLR 2025
Iyy Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Confer- ence on Learning Representations, 2018.
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. Advances in Neural Information Processing Systems, 36:8845-8864, 2023.
Fu Luo, Xi Lin, Zhenkun Wang, Xialiang Tong, Mingxuan Yuan, and Qingfu Zhang. Self-improved learning for scalable neural combinatorial optimization, 2024. URL https: //tpxx/xxvvooro///// abs/ 22///2433..2 19561.
Yining Ma. Zhiguang Cao, and Yeow Meng Chee. Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https: // openreview hwtp:/wwwwwweeeeeeeeeeeeeeeeeeee forum? Lo Juxgguu
Yimeng Min, Frederik Wenkel, and Guy Wolf. Geometric scattering attention networks. In ICASSP 202/ 202/ IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, June 2021. doi: 10. 1..1000iasss339728.22000 1111199944555 URL http: //tp:///xxxx/ /xx http//xxoioooooo//oooooo///oodot doi. org./1 1109/ Ct///ICAASPP9999
2021. 100...9111000 9414557.
Yimeng Min, Yiwei Bai, and Carla P. Gomes. Unsupervised learning for solving the travelling salesman problem, 2024. URL https:/// /atp:////avvvv..//. wwwg hargg/ab///30// 2tw0////3.... 10538.
Emils Ozolins, Karlis Freivalds, Andis Draguns, Eliza Gaile, Ronalds Zakovskis, and Sergejs Kozlovics. Goal-aware neural sat solver. In 2022 International Joint Conference Neural
Networks (IJCNN), pp. 1-8. IEEE, 2022.
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combinatorial optimization problems. In Advances Neural Information Processing Systems 35, 2022.
Sebastian Sanokowski, Wilhelm Berghammer, Sepp Hochreiter, and Sebastian Lehner. Variational annealing on graphs for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 36, pp. 63907, 2023.
Sebastian Sanokowski, Sepp Hochreiter, and Sebastian Lehner. diffusion model framework for unsupervised neural combinatorial optimization. In Forty-first International Conference Machine Learning, 2024.
Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4):367-377, 2022.
Daniel Selsam and Nikolaj Bjømerr Guiding perfoomrf sat solvers with unsat-core predictions. In Theory and Applications of Satisfiability Testing-sAl 2019: 22nd International Conference, SAT 2019, Lisbon, Portugal, July 9-12, 2019, Proceedings 22, pp. 336-353, Springer, 2019.
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David Dill. Learning sat solver from single-bit supervision. arXiv preprint arXiv:1802.00 1802.03685, 2018.
Mohamed A Wahby Shalaby, Ayman R Mohammed, and Sally S Kassem. Supervised fuzzy c-means techniques to solve the capacitated vehicle routing problem. Int. Arab J. Inf. Technol., 18(3A): 452-463, 2021.
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. CoRR, abs/2010.02502, 2020. URL
wwwp://////aaaaaa//a/.ooaa 2010.. 02502.
Yang Song and Prafulla Dhariwal. Improved techniques for training consistency models. In The Twelfth International Conference on Learning Representations, 2023.
IBM ILOG CPLEX Optimization Studio. V20.1: User's manual for eplex. IBM Corp, pp. 1-20, 2020.
Jingyan Sui, Shizhe Ding, Rui Tao Liu, Liming Xu, and Dongbo Bu. Learning 3-opt heuristics for trav- cling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learn- ing, 2021. URL https: : /api. semant eschol a www.chhlar..or/ooorsssisoe. : 249033331.
14

---

Published as a conference paper at ICLR 2025
Jingyan Sui, Shizhe Ding, Boyang Xia, Ruizhi Liu, and Dongbo Bu. Neuralgls: learning to guide local search with graph convolutional network for the traveling salesman problem. Neural Comput. Appl., (611)))666)) URL htwps::/p/.......... /doi orrg
October 2023. ISSN 0941-0643. doi: 10. 10.1000//00051-023-0990900
Zhiqing Sun and Yiming Yang. DIFUSCO: Graph- based diffusion solvers for combinatorial opti- mization. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Junior Mele U, Maria Gambardella L, and Montemanni R. Machine. Machine learning approaches for the traveling salesman problem: A survey. In Proceedings of the 2021 8th International Conference Industrial Engineering and Applications (Europe), 2021.
Pashootan Vaezipoor, Gil Lederman, Yuhuai Wu, Chris Maddison, Roger B Grosse, Sanjit A Se- shia, and Fahiem Bacchus. Learning branching heuristics for propositional model counting. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 12427-12435, 2021.
Jan Van Leeuwen. Handbook of theoretical computer science (vol. A) algorithms and complexity. Mit Press, 1991.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural In- formation Processing Systems, volume 28. Curran Associates, Inc., 2015. URL https: https:// http://pprceeenn..eeeepeep. neurips wttppppppppppppeeeecceceece.. files/ /tccppppee_LLeeeppp//////////// ptpppp////1///ilee// Papeee..
Chenguang Wang and Tianshu Yu. Efficient training of multi-task combinarotial neural solver with multi-armed bandits. arXiv preprint wwXiv:2305.06366 2023.
Chenguang Wang. Zhouliang Yu, Stephen McAleer, Tianshu Yu, and Yaodong Yang. Asp: Learn universal neural solver! IEEE TPAMI, 2024.
Runzhong Wang, Zhigang Hua, Gan Liu, Jiay Zhang. Junchi Yan, Feng Qi. Shuang Yang. Jun Zhou, and Xiaokang Yang. A bi-level framework for learning to solve combinatorial optimization on graphs. Advances in Neural Information Processing Systems, 34:21453-211 -1466, 2021.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8:229 256,, 1992.
Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song, and Jiang Bian. Position: Rethinking post-hoc baaed neural approaches for solving large-scale traveling salesman problems, 2024. URL https:tp////... / /rxiiv org/ abs/ 03503.
Yubin Xiao, Di Wang, Boyang Li, Mingzhao Wang. Xuan Wu, Changliang Zhou, and You Zhou. Distilling autoregressive models to obtain high-performant non-autoregressive solvers for vehicle routing problems with faster inference speed, 2024. URL https:::: //tp:i//////iee/aaeeaaeeeeeaae org abs /bsg//bbb/212. /2312. 12469.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Neurolkh: Combining deep learning model with lin-kernighan ma-keeigghan-hlsgaamm helsgaun heuristic for solving the traveling salesman problem. In Advances in Neural Information Processing Systems, volume 34, 2021.
Hao Xiong, Yehui Tang, Yunlin He, Wei Tan, and Junchi Yan. Node2ket: Efficient high nigh-dimessional network embedding quantum hilbert space. In The Twelfth International Conference Learning Representations, 2024. URL https: :tttttss://peeeee //opppreeeeeeeeeeeeeeee ew net/ forum d= R0h 8eK6n.
Haoran Ye, Jiarui Wang, Zhiguang Cao, Helan Liang, and Yong Li. Deepaco: neural-enhanced ant systems for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024a.
15

---

Published as a conference paper at ICLR 2025
Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, and Fanzhang Li. Glop: Learning global partition and local construction for solving large-scale routing problems real-time. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024b.
J Zhang, C Liu, X Li, HL Zhen, M Yuan, Y Li, and J. Yan. A survey for solving mixed integer programming via machine learning. Neurocomputing, 2023.
Jiongzhi Zheng, Kun He, Jianrong Zhou, Yan Jin, and Chu-Min Li. Combining reinforcement learning with linkernighan seeiighan-helgauun algorithm for the traveling salesman problem. Proceedings of the AAAI
Conference Artificial Intelligence, 35(14):12445-12455 May 2021. doi: 10.1609/aaai v35114. 17476. URL https: / /ojs aaai. org/ htrrgiinder wnneinixxi... wwwpiindwxppppppppepeepppppppppe
Xinhao Zheng, Yang Li, Cunxin Fan, Huaijin Wu, Xinhao Song, and Junchi Yan. Learning plaintext- ciphertext cryptographic problems via anf-based sat instance representation. Advances in Neural Information Processing Systems, 2024a.
Zhi Zheng, Changliang Zhou, Tong Xialiang, Mingxuan Yuan, and Zhenkun Wang. Udc: A unified neural divide-and-cod and-conquer framework for large-scale combinatorial optimization problems. The ehirty-eighth Annual Conference on Neural Information Processing Systems, 2024b.
Jianan Zhou, Zhiguang Cao, Yaoxin Wu, Wen Song, Yining Ma, Jie Zhang, and Chi Xu. Mvmoe: Multi-task vehicle routing solver with mixture-of-cxperr 2024. URL hwwphhtt///eeee //tpxvx.wx..///////.../// abs/2405. 01029.
16

---

Published as a conference paper at ICLR 2025
Appendix
CONTENTS
Details of Problem Reduction and Solution Transformation
19
A.1 HCP v.s. TSP
19
A.2
3SAT v.s. HCP
19
A.2.1
Reduction from 3SAT to HCP
19
A.2.2
Transform HCP Solution to 3SAT Solution
20
B Additional Related Work
20
B.1
Conventional Solvers
20
B.2 Learning Methods for TSP
20
B.3 Combination of Neural and OR Methods
B.4 Multi-Task CO Models
21
B.5 Specific Solvers for SAT and HCP
23
B.6 Note on Evaluation of Specific Solvers
23
Network Details
24
C.1 Vanilla MatNet and MatPOENet
24
C.2 Graph-based Diffusion and MatDIFFNet
D Experimental Details
27
D.1 Hyperparameters
27
D.2 Scale Setting of 3SAT Instances
27
D.3 Training Curves
27
More Applications of UniCO
28
E.1
More Adaptable Backbone: GNN-based DIMES
29
E.1.1
Network Architecture
................................
29
E.1.2
Training Process
29
E.1.3
Results and Discussion
................................
30
E,2
More Applicable Problems
31
E.2.1
Vertex Cover
................................
31
E.2.2
Clique Problem
................................
E.2.3
Independent Set Problem
32
E,2.4
Vehicle Routing Problems
32
E.2.5
MatPOENet & MaDDIFFNet as Problem-Specinee Solver
33
Supplementary Experiments
34
F1
Further Experiments of POE
34
17

---

Published as a conference paper at ICLR 2025
F2
Phetraining-Finetuiingg Applications
34
F3
Comparison Learning Paradigms
35
F.4
Results Vertex Cover Problem
36
E55
Results on Standard Symmetric TSP
36
F.6 Results on Real-world Instances
36
F.7 Full Experimental Results
38
G Further Discussions
38
G.1 Note on LKH
38
G.2 Note the Scalability and Applicability
................................
38
G.3 Discussion of MatPOENet v.s. MatDIFFNet
40
G.4 Discussion of Generative Combinatorial Optimization
40
18

---

Published as a conference paper at ICLR 2025
A DETAILS OF PROBLEM REDUCTION AND SOLUTION TRANSFORMATION
For easy reading, here we give a review of the mathematical definitions covered problems. Then we give the proof to problem reduction relations in the following sections. Note that methods discussed or proposed in this paper, are anchored to CO problems on graphs, especially those technically reducible structurally similar to general TSP, i.c., feasibly characterizable via matrix formulation.
Definition (Traveling Salesman Problem (TSP)), Given a complete, directed or undirected graph without self-loops denoted by G (V, E) (V (1,2..... ::: the node set, E: the edge set) along with a cost matrix C of the shape N x N where the entry Cij is the cost cost for edge (i.j) E &, the
problem is to find the tour (11, ix) ) to minimize the cost E Ciele+s + Ciyti
Definition (Hamiltonian Cycle Problem (HCP)), Given a directed or undirected graph = (V,E). the problem is to determine whether there exists Hamiltonian cycle in G.
Definition 3 (Boolean Satisfiability Problem (SAT) in conjunctive normal form (CNF)), SAT aims to determine the existence of an interpretation that satisfies given Boolean formula. A Boolean formula in CNF is represented by a conjunction (denoted by A) of clauses that are disjunctions (denoted by V) of variables. For example, (#1 V -x22 A (~o1 V 12 V -r3) is SAT instance of two clauses (I) V -I2) and (-z1 V x2 V -I3). and three variables 21, 22 and 23.
A special case of SAT in CNF where the number of variables is no more than 3 is named as 3- Satisfiability (3SAT). Note any SAT problem can be reduced to 3SAT in polynomial time (Fouh et al., 2014). So without losing generality, we pick 3SAT for evaluation.
A.1 HCP V.s. TSP
To transform the graph = EV.E) of an HCP instance to the cost matrix C of TSP instance, we simply set Cij 0 if (i,j) E & and C.j otherwise. Then the problem of finding a Hamiltonian cycle becomes finding a tour of length 0 (also the minimum length) for the TSP instance with cost matrix C. is obvious that the procedure is polynomial-time.
A.2
3SAT V.S. HCP
A.2.1 REDUCTION FROM 3SAT TO HCP
Suppose we have 3SAT instance of N₂ variables (1. ,NN, to an HCP instance follows the below two steps. More details of illustrations and proofs for claims in this subsection can be found in references, Section 28.12 12 of OpenDSA (Fouh al., 2014) (slightly different).
and N₂ clauses, reducing it
Step 1. Construct variable-clause nodes and edges. We first construct 2N, nodes for each variable, 2NN.No nodes in all. We call these nodes "variable-clauss nodes". We assign the indices to N,
to these nodes. For a variable 24, the indices of corresponding nodes are from 2N,i to 2N.(i + 1) - 1. Then we construct edges (m, + 1) and (m + 1, m) for ranges from 2N. to 2i + 1) 2. If i < N. -1, we further construct four edges (2N244 2 (i + 1)). (2N,i, 2i + 2) - -1), (2N.(i + 1) 1, 2, + 1)), and (2N.(i + 1) 1, + 2) - 1): else if i N, 1, construct four edges (2Nai, 0), (2N.i,2N. 1). (2N.(1 + - 1,,0) and
(2No + 11 1.,2
1). -)).
Step 2. Construct clause nodes and edges. We then construct N_ nodes for the clauses. We call these nodes 'clause nodes'. We denote the clauses as (C1, Cz..... Cx.-13 We assign indices from 2N. NN N. -1. If clause Cj contains variable I;. then we construct edges (2N.i+2jj, N.)) and N2 + j, 2N,i + 2j + 1). If clause C, contains variable -w,, then we construct edges the opposite directions, i.., (2N,NN + j. 2N + 2j) and (2NN² + 2j + 1, 2N,N + +))
So far, have reduced the 3SAT instance to the graph of HCP instance G containing 2N, + No nodes in polynomial time. can be easily proved that the 3SAT is satisfiable if and only if G has a Hamiltonian path.
19

---

Published as a conference paper at ICLR 2025
A.2.2 TRANSFORM HCP SOLUTION TO 3SAT SOLUTION
If the tour T traverse two variable-clause nodes whose index are 2N + 2j and 2N,i + 2j + in the order 2N + 2j + a clause node + 2N + 2j + 1. then the variable z; is set to True; else if the order is 2Na 2j + a clause node > 2 + 2j, then zj is set False.
B ADDITIONAL RELATED WORK
Apart from the literature mentioned in the main context, hereby present a detailed summary of related works including conventional methods for TSP solving, machine learning methods for TSP solving, recent pursuit for a unified framework towards general combinatorial optimization, and specific solvers for HCP and SAT problem.
B.1 CONVENTIONAL SOLVERS
Exact Solvers. Solvers for linear programming and mixed integer linear programming, including Gurobi (Gurobi Optimization, 2021) and CPLEX (Studio, 2020), can be used to solve general TSP with optimal solutions as output. Concorde is a famous TSP solver but is only applicable to 2D symmetric TSP (Hahsler & Hornik, 2007), and according to our preliminary trials, few open-source implementations produce stable and efficient solutions to ATSP. These methods can be time-consuming, especially in real-world applications where the scale of instances may be large.
Heuristic Solvers. Heuristic algorithms include nearest neighbor (NN), furthest insertion (FI), etc. Among the heuristics, LKH (currently LKH-3.0.9 (Helsgaun, 2017)) is the most famous one for its high efficiency and near-optimal solutions. Technical details of LKH has been elaborated in the main context.
B.2 LEARNING METHODS FOR TSP
The learning models for TSP solving generally receive input features from the instance graph, where typically the node features indicates the 2D coordinates of the nodes, and edge features indicating the weight of the edges. These neural methods can be generally categorized into two classes, i.e., autoregressive (AR) and non-autoregressive (NAR) methods, according to their learning and inference paradigm.
NAR Methods. Non-autoregresssive models usually output neural heatmaps in a one-shot manner, indicative of the predicted likelihood of each eadge being included in the optimal solution. These networks are mostly developed on the basis of GNN or its variants. GCN (Joshi et al., 2019), Att-GCN (Fu et al., 2021) are representative works that adopts graph convolutional network (Kipf & Welling, 2016) and graph representaion learning (Xiong et al., 2024) for edge prediction using supervised solution proximity. UTSP (Min et al., 2024) proposes unsupervised framework based on Scattering Attention GNN (SAG) (Min et al., 2021). DIMES (Qiu et al., 2022) devises novel meta-reinforce learning framework to work cooperatively with the active search technique for scaled 2D-TSP instances. The Mhoysics-isspree GNN (Schuetz et al., 2022) presents to leverage the Quadratic Unconstrained Binary Optimization (QUBO) and Ising models from statistical physics to encode optimization problems differentiable loss functions support scalable unsupervised learning, but the design of Hamiltonian formulation of specific problem can be difficult. Authors of Xia et al. (2024) also demonstrate the limitations of heatmap generation for TSP. Deviating from the prediction of single solution with supervised learning, generative modeling methods (Sun & Yang, 2023; Li al., 2023b; Hottung al., 2021a) la) endeavor characterize a distribution of high-quality solutions for given instance. Solutions can be established by sampling from the distribution. GNARKD (Xiao al., 2024) obtains NAR VRP solvers through knowledge distillation, but limited evaluation to symmetric TSP and CVRP.
AR Methods. Instead of global prediction one shot, sequence models decompose the TSP task into n-step node prediction, where each step offers the prediction map of the next node selection based on the current state. The sequence models generally follow an attention based encoder-decoder model where the encoder produces embeddings of all input nodes and the decoder produces the
20

---

Published as a conference paper at ICLR 2025
per-step node predictions accordingly. RL4CO community develops comprehensive repository for this category of methods (Berto et al., 2023). Representatively, AM (Kool et al., 2018) first proposes using transformer- based attention model for routing problems. POMO (Kwon et al., 2020) proposes the policy optimization with multiple optima for reinforcement learning; Sym-NCO (Kim et al., 2022) leverages symmetricity for neural combinatorial optimization, which is widely adopted in subsequent literature. Recent work BQ-NCO (Drakulic et al., 2023) introduces a novel Markov Decision Process (MDP) formulation for COPs, leveraging bisimulation quotienting to enhance out-of-distribution robustness.
Divide-and-Conque Frameworks In the context of neural solvers for combinatorial optimization, scalability has been a longstanding concern and challenge for the community. For NAR methods, we notice that acquiring supervision for edge regret is extremely time-consuming. making impractical for solving larger-scale problems than TSP-500. Meanwhile, RL-based sequence models also face challenges on larger-scale problems due to issues like sparse rewards and training instability, which also struggle to support training on larger-scale instances (even impractical for N 2 100). To address this issue, apart from effort to tailor specific architectures or training techniques, resorting to divide-and-conquer is proven feasible and performant. Authors of Fu et al. (2021) train small-scale model, which could be repetitively used to build heat maps for TSP instances of arbitrarily large size. Luo et al. (2024) proposes novel self-improved learning method for better scalability of neural combinatorial optimization, powered by an innovative local reconstruction approach that iteratively generates better solutions by itself as pseudo-labels to guide efficient model training. Most recently, GLOP (Ye et al., 2024b) learns to partition large routing problems into TSPs and TSPs into Shortest Hamiltonian Path Problems (SHPPs), which subsequently get conquered by local revisers. These methods improve the scales of TSPs applicable to neural solvers up to 10000 nodes. UDC (Zheng et al., 2024b) develops unified neural divide-and-conguee framework with Leade-Conqqe--Reuniie
(DCR) training method for solving general large-scale CO problems, which tries to address the sub-optimal dividing policy via high-efficiency GNNs for global instance dividing and fixed-lengti sub-path solver for conquering divided sub-problems.
Remarks. should be highlighted that the effective divide-and divide-and-conque and-conquer frameworks are indeed orthogonal to our proposed generic solver, where significant synergy can be reached to enhance both model scalability and solving quality.
B.3 COMBINATION OF NEURAL AND OR METHODS
In addition to end-to-end approaches for CO problems on graphs (COPG), resorting to the com- bination of neural networks and operations research (OR) methods is studied in several works. VSRLKH (Zheng et al., 2021) and NeuroLKH (Xin et al., 2021) combines the strong traditional heuristic Lin- -ee--Keennn-Heeeee Helsgaun (LKH) for TSP with reinforcement learning and supervised learn- ing respectively. GNNGLS (Hudson et al., 2021) and NeuralGLS (Sui et al., 2023) present hybrid approaches for solving the TSP based on GNNs and Guided I Local Search (GLSS, which searches for solutions from neurally predicted regret of including each edge. da Costa et al. (2020), Sui et al. (2021) and Ma et al. (2023) are similar works that solve TSP through automatically learning data-driven manner. DPDP (Kool et al., 2022) proposes
effective 2-, 3- and k-opt heuristics Deep Policy Dynamic Programming (DPDP) scheme, which aims to combine the strengths of learned neural heuristies with those of DP algorithms. However, it only scales up to 100 nodes in terms of solving TSPs and VRPs. DeepACO (Ye et al., 2024a) is a meta heutr-steitticc algorithm which leverages deep reinforcement learning to automate heuristic designs. GFACS (Kim et al., 2024) develops a neural-guided probabilistic search algorithm for solving COPs.
Remarks. A common limitation of these methods is the over dependence of their performance on the effectiveness of the local search, rendering the necessity of the neural parts questionable.
B.4 MULTI-TASK CO MODELS
Recent literature show growing interest of general neural CO solver for multiple problems. While similar concepts, e.g.. "multi-task solver", "universal solver", etc., have frequently appeared in some latest works, they often denote quite different approaches and functionalities. For example, MTCO (Li & Liu, 2023) devises "multi-task" CO framework which first measures the similarity between
21

---

Published as a conference paper at ICLR 2025
Table 6: Comparison of different recent works that involve "multi-task" "general TSP" solving. "Multi-Taskk" Whether the method aims for multi-task CO solving. "Multi-Scale": Whether the model adapts differently scaled instances on the fly without pre-setting parameters. "Single Solver": Whether unified solver learns multiple problems simultaneously. "General TSP": Whether the method supports general TSP input, i.e., (probably asymmetric or discrete) distance matrix only. "QP": Quadratic Programming. "RL": Reinforcement Learning. "SL"; Supervised Learning. "Evaluated Scale": the first line means the maximal (TSP/VRP) scale in the main experiments, and second line (if exists) means the maximal scale evaluated in additional experiments (supplementary results, divide-and-conquer application, generalizability, etc.). " ""); limited to variants of VRPs.
Method
Evaluated
Applicable Prublems
Evaluated Scale
Multi- Task
Multi- Scale
Single Sulver
General
Solver Type
Problems
MICO (L. Liu, 2023)
PFSP
N/A
X
X
X
QP
ASP (Wang et al., 2024)
TSP. CVRP
N/A
(~:00)
100
N/A
N/A
N/A
X
Mi--based
MAB.MTI. (Wang & Yu, 2023)
TSP, CVRP, OP, KP
100
X
X
RI.
GCNCO (Li ct 2025a)
TSP, CVRE, OP, KP
100
RL
MVMoE (7hou 2024)
100
16 VRPs
VRP variants
(1000)
RL
MTNCO (Liu 2024)
II VRPs
VRP variants
(0-0000)
100
X
RI.
UNCO (Jiang et al. 2024)
CVRE MVCP, SMIWTP
X
LLM
GOAL
100
(Drakulic et al., 2024)
ATSP. CVRP. OP, JSSP
(1000)
SL
MatNet (Kwon et al., 2021)
AISP, FESP
in matrix format
100
X
x
RL
(Qiu et al., 2022)
DIMES
TSP, MIS
10K
x
X
Meta-RL
T2T & Fast T2T
TSP, MIS
10K
X
X
Generative
(Li al., 2023b; 2024)
BQ-NCO (Drakulic et al., 2023)
TSP. ATSP, CVRP. OP
(1000)
100
x
x
RL
GLOP (Ye et al., 2024b)
TSP, ATSP PCTSP
(Large) VRPs
(100K)
10K
x
x
RL
Sp general TSP
RL., Meta SI, Generative, etc.
UniCO (Ours)
ATSP, TSP. HCP, SAT
or P matrix format
100
(VC, Clique, VRPs, FFSP, MIS, etc.)
(10K)
CO problems, and then transfers knowledge between similar instances within the same problem type gain search speed-ups in its quadratic programming solver. However, it primarily focuses on the permutation flowshop scheduling problem (PFSP) and does not explore the application of its method in handling different types of problems. Moreover, MTCO not specifically designed for learning-based neural solvers, making the term "multi-task" in its title misleading from a learning perspective and irrelevant to the theme of this paper. ASP (Wang et al., 2024) proposes a "universal" framework to address generalization issues of neural CO solvers, which iteratively improves the generalizability to different distributions (including scales). ASP proposes a model-/problem--agie training policy to improve generalizability. However, it is also focused on PFSP, and does not provide a specific neural solver which we believe is technically nontrivial that can deal with different types of problems. In the work (Wang& & Yu, 2023), authors propose multi-armed bandit framework to train a neural solver for different CO problems, whereby problems share a common encoder but differ in the header and the decoder. Yet, as the header and decoder necessitate customized designs for specific problems, the solver cannot be readily applied to unseen problems, restricting its applicability to the training dataset comprising TSP, CVRP, OP and KP. MVMoE (Zhou al., 2024) develops a multi-task VRP solver with mixture-of-experts utilizing a hierarchical gating mechanism, which achieves good zero-shot generalization performance on multiple VRP variants. Boisvert al. (2024) proposes a new generic representation that encodes problem constraints into a graph structure by breaking down each constraint into an abstract syntax tree and connecting related variables and constraints through edges. However, the authors also identify limitations in terms of training time and
22

---

Published as a conference paper at ICLR 2025
the size of the generated graphs. Resembling MVMoE, MTNCO (Liu et al., 2024) tackles the cross- problem generalization among variants of VRPs using shared underlying attributes and solve them simultaneously via a single model through attribute composition. More recently, UNCO (Jiang et al., 2024) resorts to large language models (LL. that take natural language to formulate text-attributed instances for different COPs and encode them in the same embedding space, thereby facilitating unified process of solution construction. But the solving quality and scalability has considerable room for improvement. GOAL (Drakulic al., 2024) proposes single backbone plus light-weight problem specific adapters that solves a variety of COPs include ATSP but with inferior performance.
B.5 SPECIFIC SOLVERS FOR SAT AND HCP
SAT. Neural methods for solving the SAT problem can be broadly classified into two categories: standalone neural solvers and neural-guided solvers. Direct neural solvers, such as NeuroSAT (Selsam et al., 2018) and subsequent works (Cameron et al., 2020; Jaszezur et al., 2020), classify CNF formulas as satisfiable or unsatisfiable while simultaneously constructing possible assignments by decoding literal embeddings. Several alternative approaches (Amizadeh et al., 201 9a;;; Ozolins et al., 2022) focus on directly generating satisfying assignments, leveraging different GNN architectures and employing unsupervised loss for training. These methods generally aim to predict a single satisfying solution for each instance, failing to account for other possible solutions. In the category of neural- guided methods, NeuroCore (Selsam & Björner, 2019) and #Neuro (Vaezipoor et al., 2021) utilize neural networks to guide the branching decisions of SAT and #SAT solvers. NSNet (Li & Si, 2022) models satisfiability problems probabilistic inference, using graph neural network (GNN) to parameterize belief propagation (BP) in the latent space, thereby guiding a local search for a satisfying assignment. ANFNte (Zheng et al., 2024a) proposes graph structure based on Arithmetic Normal Form (ANF) to more effectively encode cryptographic problems and uses GNN to solve the corresponding SAT instances. Methods have also been proposed using neural models to generate pseudo-industrral SAT instances to resolve data bottlenck (I.i et al., 2023a; Chen et al., 2024). Readers can refer to Guo et al. (2023) for thorough survey of solving SAT problem with neural approaches.
HCP. It is noteworthy that HCP have not yet been extensively discussed within the ML4CO community. One recent work incorporating HCP as a case study is Wang et al. (2021), which proposes a bi-level framework with an upper-level learning method to optimize the graph (e.g.. adding, deleting, or modifying edges), combined with a lower-level heuristic algorithm solving the optimized graph. This framework utilizes actor-critic-based RL method to train a graph convolutional network (GCN) and tests it on 1001 large HCP instances, achieving results comparable to LKH.
B.6 NOTE ON EVALUATION OF SPECIFIC SOLVERS
can be controversial that we have not yet incorporated the so-called "specialized solvers" for the individual type of CO problems covered in this paper. We hereby provide our detailed consideration and clarification upon this issue in hope to eliminate possible ambiguity and misunderstanding.
Conforming to Our Motivation. As our primary motivation goes, proposing competitive yet com- pact workflow capable of effectively tackling (A)TSP instances with different problem distributions comes foremost.
Lack of Companion Methods. To our best knowledge, few existing specialized solvers match our formulation of CO problems, nor are there prevalent evaluation protocols. Notably, there is limited exploration of the potential to unify various combinatorial optimization problems on graphs and exploit matrix representations for developing neural solvers with cross-task universality or cross-distribution robustness.
Existing Research Convention. There is precedent in top literature for evaluating different problems within a primarily targeted problem type. E.g., in NeuroSAT (Selsam et al., 2018), the authors, despite focusing on SAT solver, gained recognition for its cross-tase applicability by modeling and solving graph coloring, dominating-sed and node cover problems within the SAT formulation.
Remarks. Therefore, it is supposed to be reasonable to compare within the scope of general TSP solvers on our unified matrix datasets where various CO tasks are implicitly embedded, also in hope to facilitate standardized comparison of the general neural combinatorial optimization community.
23

---

Published as a conference paper at ICLR 2025
C NETWORK DETAILS
C.I VANILLA MATNET AND MATPOENET
Encoder. Each node i in the graph form of the input matrix is assigned with two embedding vectors' a,, b; E Rd We denote the embedding matrix of all nodes at the /-th layer as A' lai, ab.... ... avy E Rdx and B' of the same shape. The input A and B are initialized as zero embeddings and one-hot embeddings respectively. Note that B may not be square matrix, so MatNet forces d 2 N and set B as an one-hot square matrix OE E R x padded with zero values R. N xx(x N3, i.c., mathematically B [OE, 0]". Notably, B POE in MatNetPOE and need not paddings.
Taking embedding as example:
Q = W K. = W v.= =W'B', Q K Vdgku
(10)
MixedScoreAtt' softmax MMLP ((C;
(11)
A 4+1 MLP2 MixedScoreAAt
(12)
where W W W E Rd xd are learnable parameters for attention modeling, [::]] denotes the concatenation operation, MLP(()) denotes multilayer perceptron layer with activation functions and batch normalization operations inside. The input and output dimensions of MLP; are and respectively, so MLP; achieves mix the attention values and the cost matrix, yielding the mixed score MixedScoreAtt E R.N The input and output dimensions of MLP2 is both d.
a; a a
Computing B is completely symmetrical with A i+1 as shown in Eq. 10 to Eq. 12, by exchanging the positions of A' and B' and introducing new parameters W W 6b W.V.
MatNet extends the mixed-score attention to multi-head one, just as the original Transformer (Vaswani et al., 2017).
Decoder. Given the output embedding A and B of the last layer of the encoder, the decoder aims to conduct the so-called 'rollout' to obtain tour r = {ún, 22, ... J. The first step is to compute the key and value matrices by Kede W dr.. B and V dec = W de. B, where W WV Rd are trainable parameters. When node in is selected as n-th node in the tour T, the query vector n+1 R containing information of previously selected nodes fi,,..., in computed by:
We' dec aij:
n+1 = W dec
Fase
+ qdecr
(13)
where WQ' W dec: dec E Xd are trainable parameters for the query vectors. Then, the output ++1 can be obtained by: embedding of nith iteration of the rollout dec
Diie K dec
a+1 dec
Linear softmax
Infiarga
Vdzee) dec
(14)
V dykk
where Infi,.. a vector length N whose i, element is set negative infinity for all n' S n and other elements are set to 0, Linear(-) is linear layer whose input dimension is dykr and output dimension is d. In practice, Eq. 14 is further enhanced by multi-head attention. By Eq. 14, #+1 becomes linear combination of the embeddings bs of unselected nodes, while the weights determined by the selected nodes whose information is contain in g
The probability vector to select the next node in+1 is:
Pe (e 1 softmax Infi /.. +tanh o at
dec dd
(15)
After N rollout iterations, complete tour can be obtained.
By default, all mentioned vectors column vectors.
24

---

Published as a conference paper at ICLR 2025
Model training. It is trained in the same way as POMO (Kwon et al., 2020) based on DRL. For each instance with C, samples N tours {T ,T, , , with different nodes as start. Then the policy gradient is:
VoJ(0) N (L(r") - b(C) V pogge(r""())
(16)
where L(T) is the length of tour т, (CC) is baseline method which is instantialized as the mean tour length of the N tours, mathematically b(C) 1/N E L(r").
Tour
Input Node
Decoder
Decoder Layer
Next Node
XN -1
Inf Mask
B
Instance
Mix-Score Attention
xL
Encoder
C
Trainable
Zero Embedding
POE Matrix B
Untrainable
Tempt Variable
Scale-free initializer: POE
Figure 4: General structure of MatPOENet.
Fig. 4 illustrates the general neural structure of MatPOENet, highlighting with dashed square the adaptive design for initial node embedding, i.e., the scale-free initializer, pseudo one-hot embedding scheme.
C.2 GRAPII-BASED DIFFUSION AND MATDIFFNET
Overview. Given the distribution of problem instance with distance matrix C, solutions (S) can be established by sampling from the distribution and maximizing the conditional likelihood estimation Ellog (S( C)]. where 0 is the model parameters. The model is optimized through the evidence lower bound (ELBO) in Eq. 17, where is the posterior and the latent variable.
C --EEyyS. log (S, C (Z C)
LE[ log pappppSS (S|C))
(17)
Details. MaDIIFFNet generates general TSP solutions Sg E (0, nx by T T'step denoising process from random noises Sr, and the latent variables include noised solution Sı:r, outputting binary heatmap guiding the search of a valid TSP tour. The discrete diffusion models generate solutions So E {0, 1 by Tssepp denoising process from random noises ST, and the latent variables include noised solution Si.T- For each entry, the model estimates a Bernoulli distribution indicating whether this entry should be selected. In implementation, each entry of solution is represented by one-hot vector² such that So E {0, 1] | Following the notations of Ho et al. (2020); Austin et al. (2021), the general framework of diffusion includes forward noising and reverse denoising Markov process.
Fach entry with [0, indicates that is included in S and [1, 0] indicates the opposite.
25

---

Published as a conference paper at ICLR 2025
Trainable
Tour T
Denoised Heatmap H
Untrainable
Tempt Vali
Model Prediction X
Instance
MLP: Matrix Mixer
Mix-Noised Map Xf
GCN: Encoder Layers
x
Noised Label
Matrix- input adaptor: Mix-noised map & Dual feature convolution
Pseudo Coordinates A
Pseudo Coordinates
Figure General structure of MaDDIFFNet.
The noising process takes the initial solution Sg and progressively introduces noise generate sequence of latent variables SI.T. The denoising process is learned by the model, which starts from the final latent variable Sr and denoises S, at each time step generate the preceding variables S,-1 based on the instance C, eventually recovering the target data distribution. The formulation of the denoising process is expressed (So.T C) p(S)) II (o Sr, C). The training optimization aims to align pe (So C) with the data distribution (Spo(C) C) using ELBO:
L Fgg Σ DEL
So) Po(SS-1(Ss, C)] - log po C)) +
(18)
Specifically, the forward noising process is achieved by multiplying S, E 1 at step t with a forward transition probability matrix Q: [0, 1]2x2 where [Qri. indicates the probability
B
3, (Austin et al., 2021),
of transforming E; in each entry to Ey- We set Q =
1-3
B,
where Bg [0, 1] such that the transition matrix is doubly stochastic with strictly positive entries, ensuring that the stationary distribution uniform which is an unbiased prior for sampling. The noising process for each step and the (-step marginal are formulated
(S.[S:.11) Cat(S.; S Q+) and (S.](So) Cat(S.; S. S,),),
(19)
where Cat(S; p) is categorical distribution over N one-hot variables with probabilities given by vector p and Q Q Q ... Q,- Through Bayes' theorem, the posterior can be achieved as:
(S. = (S SS) S.). = Cat S.-iip= S.Q. O SOQ-11 5.0550..1
(20)
(S,(SSn)
S.Q.ST
The neural network is trained to predict the logits of the distribution (So C), such that the denoising process can be parameterized through q(S, SS)
pe pe(S:11SS) x Σ (S..i1 So),. S0 C).
(21)
8
Fig. 5 illustrates the general neural structure of MatDIFFNet, highlighting with dashed square the adaptive design for matrix input, i.c., the mix- noised reference map and dual feature convolution scheme.
26

---

Published as a conference paper at ICLR 2025
D EXPERIMENTAL DETAILS
D.1 HYPERPARAMETERS
MatPOENet. We 512 as the positional embedding dimension well as all hidden dimensions in the network. For N = 20 and 50, 8 layers of mix-score attention block is adopted to better capture problem features, whereas 5 layers are set for N ~ 100 for space saving. We train our model using Adam optimizer (Kingma, 2014) with a learning rate of 4 x 10-4 with decay of 1 x 10 10-6. The batch size set to 200 for N 20, 50 and 150 for N 100. Defining training epoch as 10,000 randomly generated problem instances, we find the performance sufficiently noteworthy within 2,000 epochs for all scales, despite the fact that more training steps might produce better convergence and outcomes.
MatDIFFNet. The parameter setting of MatDIFFNet basically follows Li et al. (2023b). We set the dimension of the input features for implemented graph neural networks equals 2 indicating the pseudo 2D coordinates of the nodes, and set the feature dimension of the intermediate layers to 2 for the classification modelling.
256. The output channel dimensions of the networks Default number of GNN layers is set to 12. Models at all scales are trained with a cosine learning rate schedule starting from 4 10-4 and ending at For each type of problem distribution, we generally use 1.28M random instances for each epoch of training and train the models for 100 epochs. We apply curriculum learning and initialize the models from Rs 50 checkpoints. For mixed data training. 400 epochs are conducted to gain an equivalent period to those trained individually. Training batch-size set to 128 for N 50 and 32 for & 100. For the diffusion part, We implement the model with 50 inference steps for denoising, and the models are trained with 1000 denoising steps, ie., Titenosee = 1000. We additionally apply the technique denoising diffusion implicit models (DDIMs (Song et al., 2020)) for accelerating inference and solution reconstruction.
UniCO-DIMES. We set layers for the backbone GNN with 64 hidden units for each. For both outer updates and inner stea-,teps, use AdamW (Loshchilov & Hutter, 2018) as optimizer, with a learning rate of x 10-3 and 1 x 10-1 respectively. For all scales of problems, we train the model for 1000 outer epochs, each containing Tmeta 15 inner meta-updates with K 1000 samples. In the testing phase, we set the (inner) learning rate of active search to 0.5 for faster optimization and with typical 100 steps.
D.2 SCALE SETTING OF 3SAT INSTANCES
To align with our experimental setup (N s 20, 50, 100), we manually tailor the number of variables N₂ and clauses N₂ as outlined Table 7. During training at a specific scale, each batch of AS instances are generated with randomly determined parameter line within the corresponding scale group.
D.3 TRAINING CURVES
ATSP
21/7EP
2.6
6.5
2.5
1.55
2.5
1.0
1,50
1.5
23
1.25
35-
2.5
1.70
Ppech
Figure 6: Tour length of different problem categories during UniCO-empowered mixed-data training
of MatPOENet with N 50.
Fig. 6, Fig. 7, and Fig. 8 depict the solved tour length during the training process MatPOENet. MatDIFFNet, and DIMES under our UniCO framework. Note that the ATSP curve for MatDIFFNet is smoothed by exponential moving average with a = 0.01 for better clarity, as reaches the fluctuation stage sharply within the initial epochs. The RI--based training curves (MatPOENet and DIMES)
27

---

Published as a conference paper at ICLR 2025
Table 7: Detailed scale parameters of 3SAT instances contained in different experimental groups.
Scale group
# Variables (N₂)
Clauses (N₂)
Exact N
Average N
4
2
18
N 20
20.3
5
22
39
3
49
Ri 50
52
49.8
4
54
55
95
5
99
N ~ 100
8
102
101.0
104
7
105
1.000
1.064
1,53
Spock
Figure 7: Tour length of different problem categories during UniCO-empowered mix-data training of MatDIFFNet with N 50.
Pall sut
ALSP
20735
35/11
2.5
2.5
3.5
Much
1M
750
3000
750
5:00
750
3000
500
750
1000
530
730
1000
Speck
Figure 8: Tour length of different problem categories during UniCO-empowered mix-data training of DIMES-AS with N = 50.
sampled with a time step 10. It can be observed that Transformer- Diffusion- and GNN-base backbones all well optimized under UniCO with problem instance reduction. Furthermore, detailed training objective curves for each individual problem type demonstrate consistency and stability of convergence across all involved problem categories, addressing claim of multi-task robustness.
E MORE APPLICATIONS OF UNICO
In this section, we provide the details of possible applications of our proposed UniCO. For backbone model, we adapt DIMES (Qiu et al., 2022) for multi-task training under UniCO by simply replacing its input of nodes coordinates by random vectors. Sec. E. we carefully introduce architecture and training policy. For more applicable problems, Sec. E.2 presents a list of feasible CO problems that can i) be reduced to general TSP form, ii) formulated via matrix representation, or iii) resolved by proposed models specific solvers. In the conclusion, provide further clarification upon the orthogonality of UniCO and the proposed backbone solvers, reiterating the motivation and position of paper.
model
28

---

Published as a conference paper at ICLR 2025
E.1 MORE ADAPTABLE BACKBONE: GNN-BASED BASED DIMES
DIMES (Qiu et al., 2022) proposes scalable neural solver for 2DTSP based on meta-learning and deep RL.
For TSP, parallel to attention models that sequentially decode node selections, GNN-based techniques have gained prominence for predicting healmaps in support of online scarching. To this end, we endeavor to pinpoint a GNN-based architecture that aligns seamlessly with the implementation of our instance reduction-bee based general CO training framework. Several observations guide this exploration: 1) High cost of supervised training. Preparing supervision for TSP is primarily tumeconsuming Even worse, matrix input of general TSP can be intractable for space as well, compared to existing works that often take the convenience of storing coordinate representations only. 2) Embedding limitations. Prevailing GNN methods, often designed for TSP as an edge classification task, heavily rely on coordinate inputs, which remains open problem. 3) Data distribution variability. Notable divergence of data distribution exists subsequent to the reduction of TSP from diverse problem instances. This variability poses considerable challenge for supervised training of GNN.
Our exploration of existing models unveil that meta- neta-learning and RL-based active search strategies in DIMES resonate with our intuitive perspective. We adapt vanilla DIMES into UniCO architecture, underscoring its proper alignment with our motivation of tackling multi-task CO problems, and in turn validating the feasibility of our proposed framework.
Overview. DIMES uses an Anisotropic GNN (Bresson & Laurent, 2018) as backbone to capture representations of different types of problem instances. The vanilla DIMES takes node coordinates as the input node features and the distanrces as the input edge features. To generalize DIMES to general TSP, we empirically use random numbers sampled from [0. 1] of fixed dimension d (d = 64 by default) as the node feature. The training process combines Model-Agnosse and DRL. The primary objective is to enhance the prediction of heatmap initialization that later yields optimal solving results after the RL-based active search in the testing phase. Following the paradigm of meta-lcarning, the training process of DIMES involves outer epochs which optimizes the backbone GNN parameters utilizing the estimated policy gradients computed with one more inner upda-up We present the detailed mathematical formulations below.
Meta- Meta-Learning (MAML)
E.1.1 NETWORK ARCHITECTURE
The GNN layers work as the following message passing scheme:
h = h. + BN U'hi + AJENs (o(el)) @ v'h))]
(22)
1+1 = c/ c + a (BN(P'',) + Q'ni + +R'n)))
(23)
where hy and ely respectively denote the node embedding of node i and the edge embedding of edge (1,5) the 1-th layer, U V P Q', RR. are learnable parameters of 1-th layer, ax.)) is the activation function (set as SiLU (Elfwing et al., 2018) in practice), BN(-) is the batch normalization function.
E.1.2 TRAINING PROCESS
Let F& denote the graph neural network parametrized by Q. For each TSP graph instance reduced from the problem pool C, the instance-specific input to the network is its distance matrix D., and the output 0, E [ Fg ( D2)) acts as the initial heatmap guiding the search of a TSP tour. A higher valued 0z, indicates a higher probability for the edge from node to node j to sampled. The vanilla loss function is articulated the expected cost of the solution for any graph in the collection:
L( S(.c E
(24)
where 5(.) denotes the sampling-based baseline function (Kool al., 2019) from given distribution representation of predicted heatmap. Specifically,, a batch of graph instances of the same problem type and scale is generated randomly from C in every outer training epoch, within which T inner meta-steps are taken to fine-tune the parameters on each instance by RL-based updates, referred to active search (Bello al., 2017; Hottung al., 2021b). The fine-tuned parameters (T)
29

---

Published as a conference paper at ICLR 2025
computed using these gradient updates for each graph instance s with inner learning rate a, thus having { + and for 1 I S T:
(1)) = ( a 4 L {(})).
4(--1)
(25)
Through the inner steps, we obtain the updated heatmap 0! = F aT (D&). For each instance s in the batch, K solutions (r), ,*} sampled the basis of 0! calculate the reinforcement learning-estimated gradient of 0:
=OE-L(A)]-E,,LL67 S(s) V (T)))
(26)
where T.(.) denotes the length of feasible tour and po is an auxiliary distribution to compute the probability of a feasible solution for TSP with random start node and chain rule factorization:
exp(stn.ta4))
Po((nt1lin'sm) Em exp(si..e.r)
(27)
Subsequently, optimize the performance of the graph neural network with the estimated gradient and meta-objective, closing the outer loop:
Linta (C) = E, E
(28)
E.1. RESULTS DISCUSSION
Performance. As demonstrated in Table 8, with our modified input node embeddings, DIMES works finely with our UniCO framework matrix encoder for general TSP, achieving comparable solving quality via active searching. Despite notable gap from DIMES to MatPOENet and MatD- IFFNet, DIMES shows good compatibility of UniCO and have the potential to effectively scale to larger instances, which can also be valuable research direction in the future.
Table 8: Results of UniCO-DIMES trained on mixed problem data.
Scale
Methods
ATSP
2DTSP_
DHCP (LJ, FR1)
3SAT (L), FR1)
Avg. LJ
DIMES
2.2335
4.1696
2.9448
2.67%
2.6660
2.12%
3.0035
20
DIMES-AS(I00)
1.6790
3.9092
0.4596
60.12%
0.2828
77.12%
1.5826
DIMES-AS(200)
1.6439
3,8809
0.4464
61.92%
0.3068
75.16%
1.5695
DIMES
2.3341
6.6271
3.1788
1.56%
5.3656
0.12%
4.3764
50
DIMES-AS(
1,6920
5,9447
0.5908
46,04%
1.5830
20.44%
2,4528
DIMES-AS(200)
1.6794
5.9194
0.5000
54.20%
1.4296
23.36%
2.3821
DIMES
2.5186
9.5777
3.8064
1.16%
3.8064
0.00%
6,4018
100
DIEMS-AS(100)
1.6968
8.3390
0.8480
24.00%
2.8040
7.16%
3.4220
Efficiency. Table 8 lists the solving efficiency of vanilla MatNet and DIMES under our UniCO framework. MatNet benefits from its weight architecture and sequential decision paradigm and have better time advantage. Active search process endows DIMES with better per-instance solving performance, while consumes much more time due to its gradient-based local search.
Table 9: Solving efficiency comparison under our UniCO framework. Setting: N zs 50, batch_size 100, 2500 instances. DIMES(T): DIMES with 7' inner updates of active search.
Backbone
MatNet
MatNet(8x)
DIMES
DIMES(15)
DIMES(100)
Time
15s
2m40s
2m17s
10m35s
1h24m
30

---

Published as a conference paper at ICLR 2025
MatNet v.s. DIMES: MatNet wins on both efficiency and model performance, but DIMES has better scalability. We compare vanilla MatNet without augmentation and DIMES without fine-tuning, both trained with mixed data. We see that MatNet outperforms DIMES significantly. We also present the solving time of vanilla MatNet and DIMES in Table 9, which demonstrates the high efficiency of MatNet. Though MatNet wins both efficiency and model performance, according to their official papers, DIMES can be run on TSP-10,000 (Qiu et al., 2022), but MatNet only scales about TSP-100 (Kwon al., 2021), indicating better scalabilty of DIMES. It because DIMES adopts lighter neural architecture, but MatNet has a complex rollout scheme, causing non-negligible amount of temporal variables, thus limiting its scalability.
DIMES v.s. DIMES-AS(T): The trade-off between efficiency and effectiveness brought by fine-tuning on test cases. By comparing DIMES-AS(I) with vanilla DIMES, DIMES-AS(T) improves DIMES significantly with fine-tuning on the test cases. However, DIMES-AS(T) may suffer from severe scalability issue in real-world applcations. The solving time in Table 9 shows that (15ES(15) may take about 4.6 times as DIMES.
E.2
MORE APPLICABLE PROBLEMS
E.2.1 VERTEX COVER
Definition& (Vertex Cover Problem (VC)). Given an undirected graph G and positive integer k, vertex cover of a set S of vertices that every edge is incident on at least one vertex of G. The problem is to determine whether G has vertex cover of size no more than k.
Reduction from VC to HCP. Let the (undirected) graph of VC instance be G(V,E) and the target to determine whether there exists a vertex cover S containing no more than k vertices. We can construct an HCP graph G'(V,, E') with 4|E + & vertices. Indexing the edges in & from 1 to [8], g' can be mathematically described as:
; V {aI, a2, ..., ak, U ([u, i, 0), [u, i, 1]Iu V)
(29)
where is incident on u.
8' = [[u,,,,) (u, [.)
{0,1)} U ((1u,, Dest. ees k se e< i, V}.
(30)
U [(a,
Transform HCP Solution to VC Decision. If there exists Hamiltonian cycle in g', we first select all vertices in that connect any vertex in {aI, ................................ ox.. The selected vertices are necessarily in the form of < u, u,i,a and all these E V constitute the vertex cover of G within & vertices.
Note that the VC problem has been incorporated UniCO framework and implemented for evaluation. The details of data generation and empirical results are provided in Appendix F.4.
E.2.2 CLIQUE PROBLEM
Definition 5 (Clique Problem). clique is (sub)graph induced by a vertex set K in which all vertices are pairwise adjacent, i.e for all distinct u, v E K, (u, v) E E. A clique of size k is denoted as Kg. The clique problem is to determine whether a graph on n vertices has clique of size k.
Reduction from clique problem to SAT. Given clique instance, introduce the following for an SAT instance:
Variables:
Wär (true if node is the r-th node of the clique) for Si n, Srsk h.
Clauses:
31

---

Published as a conference paper at ICLR 2025
1) For each r, V1,r V2,r V V yn,r (some node is the rth node of the clique).
2) For each i, < s, Wir V -Vi, (no node is both the r-th and s-th node of the clique).
3) For each r # and i such that ji, is not edge of G, -W,, -yja. (If there's no edge from i to j then nodes and j cannot both be in the clique).
That's the entire formula that will be satisfiable if and only if G has clique of size k. As SAT problem can be transformed to 3SAT and further reduced to general TSP in polynomial time, the decision of Clique problem can be solved by -hicO-empowered solvers.
E.2.3 INDEPENDENT SET PROBLEM
Definition 6 (Independent Set). An independent set is vertex set in which no two vertices are adjacent, i.e,, for all distinct u, e S, (u, v) E F.
Definition (Complement Graph). Let = (V, E) be graph, the complement graph of G, denoted as G = (V, F.), is defined such that F. contains all the edges not present in G.
By definition of complement, (u, E ++ (u, v) E. The statement that S C V is an independent set in G is equivalent to the fact that S induces clique in G. Therefore, an IS problem can be transformed into a Clique decision, and solved by the same reduction of Clique problem to general TSP thereafter.
E.2.4 VEHICLE ROUTING PROBLEMS
Solving via sub-TSPs. While problems like CVRP cannot be directly solved by a direct transfor- mation, the TSP solver can still be utilized. E.g, the Cluster-Firs: Route-Second Method (Shalaby et al.. 2021), solves CVRP by first clustering points and then solving each cluster as TSP. Thus, robust TSP solver effective in the second phase for CVRP. Additionally, as mentioned in Ye et al. (2024b), large routing problems can be partitioned into TSPs and TSPs into Shortest Hamiltonian Path Problems (SHPPs), solidifying the significant role good TSP solver plays targeting sub-structures of complex VRPs.
Solving via sub-V VRPs and SAT. We also notice that latest works like Zheng et al. (2024b), CVRP of large scales are divided into sub-CVRPa Thus, a theoretical valid transformation of VRP to SAT problem makes a significant difference to our proposed UniCO framework. Below provides a general formulation of the VRP constraints via variables and clauses in SAT. Subsequently, discuss the challenges of incorporating capacity or other integer constraints via conjunctions and disjunctions of Boolean variables along with our possible solution and analysis of this idea.
Consider the three basic inputs a VRP instance, the number of nodes N, the number of vehicles K, and the pair-wise costs dij- The three-dimensional decision variable Xijk is introduced in the SAT instance, where i, E {0, 1, .... .N} are the indices of N nodes (0 denotes the central depot), and k E [1...., K} the index of К vehicles. Tisk the Boolean variables indicating whether vehicle k is assigned to travel directly from node to node j.
Constraint all vehicles departs from and returns the depot exactly once. Lee.
Wk {1,
K}.
Σ 1=1
Took
Σ Ijok 1,
(31)
which form the following Boolean clauses. For each vehicle h (1,.... K). C1 = (Fuzk V Bu2k V .... V tONK)
(32)
C2 = (Iink V Zzok V... V Nook
(33)
C3 = {(-Zojik V (ooo)))))(Viii.. E (I,...,NN.. #
(34)
C₁ = {(-rr,00 V -Z.,0)) E (1,-.. ,N), i1 #
(35)
Constraint 2: customer nodes should be visited exactly once. Mathematically,
Vi E (1, N}.
Tisk 1,
(36)
32

---

Published as a conference paper at ICLR 2025
which form the following Boolean clauses. For each node i {l....,N
Cs -mm V VaN1) V (mak V 122 V V....Vaaa VaNNK)
(37)
C. (((-res V -1ink))) E (1,'. ,N,. # j2 E (1,.,, K}}
(38)
So far, have built the basic constraints of general VRPs. A Boolean formula can be obtained by N:=1 C₁ in the SAT instance ensure feasibility of a VRP solution.
Next, when stepping into the capacity demands for CVRP (Q: the maximum capacity of each vehicle; my: the demand quantity of each node), the following constraint should be added.
Constraint 3: the loading capacity of all vehicles should not exceed the limit. Mathematically,
N
Ak E (1, .... K},
mj Tijk S Q
(39)
This arouse difficulty for an SAT instance with its binary variables and Boolean clauses di- rectly formulate the complex integer constraint. One way to handle this problem is split the vehicles and customer nodes into many sub-vehicles and sub-nodes with unit capacity and de- mand, according to the quantity of Q and m,, Mathematically, the number of nodes and ve- N m, and KQ, thus the decision space of Tayk is expanding to hicles will be changed to Σ,
i.j E ((1,2,... m1), (m1 + 1, + 2,... mi + m....... Σ, m.} and K E {(L.... Q), (Q - .Q.,,2Q) .... KQ]. Subsequently, extra constraints shall be added to guarantee the consistency among sub-nodes and sub-vehicles which belong to the same original group, i.e., mathematically, For all nodes j.j E (ET= Ms TT- m.). VT E (...... N - }} and vehicle k E (Qr, Q(r + 1)], Vr e {0, (O.... K- 13. we add clauses (MZzga)) V (A(-I()))) to the SAT formula.
Remarks. Thus far, the constraint conditions of the CVRP are transformed into SAT form using the 3-dimensional variables Ziyk- Here, satisfiable variable assignment corresponds to a feasible solution to the VRP instance. The obtained candidates can then be further optimized for lower total costs. This attempt facilitates the possibility of solving sub-VRPs within our UniCO framework in the first place and provides rich implication
another viable perspective of incorporating more COPs with complex constraints using Boolean formulation of SAT. We would like to reiterate that the above descriptions are initial conception to foster as much inspiration for future research. In practice, considering 1) the heavy computational overhead of this transformation. 2) the maturity of the two-dimensional matrix solver for general TSP, and 3) SAT instances shall also be reduced to general TSP later in our framework, we still recommend readers to resort to transforming complex routing tasks into Sub-TSPs, if within our framework.
E.2.5 MATPOENET & MATDIFFNET AS PROBLEM-SPECIEE SOLVER
In addition the problems mentioned above that can be consistently learned and solved by reducing to general TSP. our proposed MatPOENet and MatDIFFNet can also serve as problem-specific individual solvers decoupled from UniCO, thus enabling a wider range of applicable problems, as long as specified in matrix form of parameters quantifying the relationship between two groups of items. For instance, as evaluated in Kwon et al. (2021) and Li et al. (2023b), Flexible Flow Shop Problem (FFSP) and Maximal Independent Set (MIS) problem are readily modelled for MatPOENet and MatDIFFNet, respectively.
Conclusion. Application of the reduction scheme to a wider range of problems are theoretically guaranteed by the computational complexity theory, and will be further studied in our future research. Note that resorting to problem reduction for general solving of different CO problems has limitations, where some tasks with more complicated constraints high transformation complexity are not practical. However, the orthogonality between UniCO and specific solvers should be noted, as more problems has the potential be solved via individual modelling for proposed neural solvers.
33

---

Published as a conference paper at ICLR 2025
Table 10: Ablation studies for the rough solver of MatNet-POE. Scale N = 50. Trained on mixed data, tested with 8x augmentation.
Methods
ATSPL
2DTSP
DHCP (I.), FR1)
3SAT (14,, FR
Avg. T.4
Avg. FR
Non-MatNet-POE
1.7988
5,8178
0.4080
64.72%
1.0020
34.76%
2.2566
49.74%
FI-MatNet- PPE
1.8370
6.0962
0.1920
82.80%
0.6060
55.72%
2.1828
69. 69.26%
MatPOENel (NN)
1.6417
5.7283
0.0172
98.28 %
0.2456
77.60%
1.9082
87.94%
F
SUPPLEMENTARY EXPERIMENTS
F.1 FURTHER EXPERIMENTS POE
Different Initial Rough Solvers. As mentioned in RQ4 the main context, we tested different solvers to prepare the rough solution to initialize POE. In Table 10, among nearest neighbor (NN), farthest insertion (FI) and without initial solution (Non), NN outperforms the others, which proves the efficacy of choosing the simple nearest neighbor heuristic as initial rough solver to capture local information for POE.
Different Initial Node Embeddings. As mentioned in RQ4 in the main context, have addition- ally implemented the two advisable ways mentioned as alternative initial embeddings for MatNet in its paper (K (Kwon et al., 2021). Note that they are both aimed at breaking the dimension restriction as our proposed POE.
Table 11: Results of MatNet model equipped with different initial node embeddings on N 50 dataset. "Trainable": Nmax different vectors made of learnable parameters. "Random": completely random vectors for each problem instance.
Init. Embed. Type
ATSPL
2DTSPJ
DHCP (LJ, FR1)
3SAT (L,, FR1)
||
Avg, L
MatNet-RRndom
2.1044
5.8981
0.8560
33.20%
1.1620
30.44%
2.5051
ColNet-Trainable
1.8923
5.8157
0.4148
63.96%
0.5012
58.52%
2.1560
MatPOENet (ours)
1.6417
5.7283
0.0172
98.28%
0.2456
77.60% %
1.9082
Through this experiment and results in Table 11, we ackowledge the potential capability of tailored trainable emeddings and anticipate further studies, though, within our time and knowledge, better performance is achieved using our proposed POE over vanilla random vectors or trainable parameter matrices of the same shape.
F.2 PRETRAINING-FINETUNNI APPLICATIONS
As claimed in the main context that our proposed UniCO serves properly as a pretraining fintrrninnginniinggggg framework, we hereby present two supportive experiments in conventional scenarios:
i) Cross-task scenario: pretrained on several problem types, finetuned on an unseen problem type.
Table 12: Results of the cross-task finetuning 3SAT. MatPOENet is pretrained under UniCO framework with dataset comprising ATSP, 2DTSP and DHCP instances of as 50 for 2,000 epochs and subsequently finetuned the task of AS data for (a much fewer) 500 iterations.
Description
3SAT (1.) 3SAT(FR)*
#Tipochs
Pretrained on ATSP, 2DTSP, DHCP w/o Finetuning
1.4080
17.92%
2000
0.0404
95.96%
50
Pretrained on ATSP, 2DTSP, DHCP w/ Finetuning on 3SAT
0.0360
96.40%
100
0.0292
97.08%
200
Trained on merely 3SAT (control group)
0.0400
96.08%
2000
34

---

Published as a conference paper at ICLR 2025
From Table 12, We observe that after finetuning the unseen task data (3SAT), the model perfor- mance is improved significantly compared with that without finetuning (the first row the table), and yield similar performance compared to the case where the model is premarily trained on 3SAT only (the third row the table). These results demonstrate the applicability of UniCO for pretraining-fintuiie MatNet-POE.
which also directs feasible path address the generalizability issue of
ii) Cross-scale scenario: pretrained smaller scaled dataset, finetuned on larger scaled dataset.
Table 13: Results of the cross-scale finetuning experiments on N = 100 sets. The MatPOENet model is pretrained under UniCO framework with different dataset of N 50 for 2,000 epochs and subsequently finetuned on mixed data of N z 100 scale for (a much fewer) 500 iterations.
Pretrain data
Finetune data
ATSPL
2DTSP]
DHCP (I.), FR1)
3SAT (I.), FR1)
Avg. T.
Mixed-50
2.5656
8.5404
23.5064
0.00%
17.5564
0.00%
13.0422
Mixed-50
Mixed- 10e
1.9798
8.0573
1.7796
6.60%
2.0664
11.68%
3,4708
ATSP-50
Mixed- 100
1.8855
8.3838
0.6712
46.72%
0,2888
72.76%
2.8073
Mixed-100
1.8655
8.1719
0.0052
99.48%
0.2440
77.12%
2.5717
Remarkably, we observed from Table 13 that pretraining smaller instances of ATSP leads to greatly improved outcomes when fine-tuned on larger scaled multi-task datasets, possibly suggesting the significance of capturing general problem patterns as well as handling hard cases during pretraining. The bold numbers are the hest among finetuned settings, approaching competitive performance the model primarily trained N 100 data (the last row) with much shorter training time.
These empirical findings provide strong support for our assertion regarding UniCO's capability to serve as a peetraining-inettunee framework. Furthermore, they spark further interest and exploration into leveraging this paradigm to enhance the model's 's scalability as well as generalization performance.
F.3 COMPARISON OF LEARNING PARADIGMS
We have already tried to combine the idea of instance reduction to general TSP with supervised approach. To ensure fair competition, we modified MatNet architecture into a heavy-encoder and light-decoder model for SL, which by convention, outputs a heatmap to guide subsequent local searches. Note that calculating supervision solutions for ATSP/2DTSP scale is extremely time- consuming, we implemented the method on decision problem (HCP and 3SAT) instances where the ground truth easier to obtain.
Table 14: Performance comparison for HCP and 3SAT problems with different learning paradigms under UniCO.
Method HCP-50 (L.)
FR
Time
3SAT-50 (L.)
FR
Time
Greedy
6.014
0.04%
Os
5.987
0.00%
LKH
0.000
100.00%
Im29s
0.140
86.28%
2m1 Is
MatNet
0.481
53.04%
4m12s
0.329
73.12%
2m
UniCO-RL
0.017
98.28%
4m8s
0.117
88.44%
2m4s
UniCO-SL
0.000
100.00%
2m29s
0.077
92.32%
2m39s
Table 15: Performance comparison for larger HCP and 3SAT problems with different learning paradigms under UniCO.
Method
HCP-500 (I.L)
FRT
Time
3SAT-500 (1.))
FR
Time
Greedy
6.924
0.00%
1m27s
15.149
0.00%
Im15s
LKH
0.526
55.88%
1hlm
5.812
3.92%
1h10m
UniCO-SI.
0.127
88.12%
1h24m
2.124
65.60 %
1h22m
35

---

Published as a conference paper at ICLR 2025
Results show that SL paradigm also works performantly under UniCO framework, with better scalability but more preliminary overheads for supervision and post searching. (UniCO-RL refers to the setting where UniCO is instantiated by MatPOENet.)
F.4 RESULTS ON VERTEX COVER PROBLEM
Echoing the introduction of more applicable problems in Appendix E.2, we have conducted additional experiments on vertex cover (with 2500 test cases on as 50), following the reduction procedures provided. Similar to the SAT-distributed general TSP, we specified the important parameters for data generation as specified in Table 16. The experimental results are shown in Table 17.
Table 16: Parameters for vertex cover instance generation.
TSP Scale N
Num Edges E Cover Size k NodeN Nvc Range of N
Average N
N = 50
Uniform(10, 12)
Uniform(3,8) 8)
Uniform(8, 17) [43, 56)
50.0
Note that initial experimental results show that proposed models easily adaptable into the UniCO framework and perform decently on the new problem VC. With the transformation of complementary graphs, series of node selection tasks on the graph could also be addressed similarly. Thus far, representative range of edge-wise tasks (TSP, ATSP, HCP), node-wise tasks (VC, Clique, etc.) and decisive problem (SAT) combined have formed a good coverage of mainstream COPs on graphs. In the future, we will delve further into the detailed implementation and improvements on the instance-level performance and work on more problems.
F.5 RESULTS ON STANDARD SYMMETRIC TSP
To better align our work with previous literature in pursuit of 2D TSP, additional experiments have been conducted on the consistent test dataset of symmetric TSP-50 and TSP-100. Each dataset consists of 1280 instances featured by node coordinates. Results are shown in Table and Table 19. The results of previous works are re-implemented or re-executed with the provided model weights within our consistent evaluation environment to ensure fair comparison.
Note. All methods except MatNet and those proposed in this paper adopt 2D coordinates input node features. In contrast, our methods solely encode the distance matrix as input information. Additionally, models can be trained on mixed data, whereas previous works were exclusively trained on symmetric TSP only. These comparative results demonstrate that our models can achieve comparable (and even better in some cases) performance without utilizing coordinates, validating proposed MatPOENet and MatDIFFNet as successful matrix encoders for symmetric TSP.
F.6 RESULTS ON REAL-WORLD INSTANCES
In the main experiment, this paper primarily focuses on synthetic data for testing. To address this limitation, we have additionally tested our methods on subset of standard TSPLIB instances, which are renowned for their real-world scenarios in TSP evaluation. We selected instances with city scales ranging from 14 to 195 (as listed in Table 20). These instances encompass different distance types (such as "EUC 2D", "GEO", etc.) and representation formats (such as "coordinates", "full matrix", "diagonal matrix", etc.). To ensure fair evaluation and optimally leverage the matrix- encoding capability of our unified framework and models, we have rewritten the selected instances
Table 17: Results vertex cover.
Method
Tour length (4)
Found rate (1)
GUROBI
0.000
100.00%
Greedy
7.351
0.00%
MatNet
2.349
1.08%
MatPOENet-8x
0.220
78.28%
2aDDIFFNet-2OPT
0.477
66.60%
36

---

Published as a conference paper at ICLR 2025
Table 18: Performance comparison on standard symmetric TSP-50 test set.
Method
Tour length (1)
Optimality gap (4)
Time/instance
Concorde (Optimal)
5.688
0.074s
AM (Kool al., 2018)
5.747
1.04%
0.013s
POMO (K won et al., 2020)
5,698
0.18%
0.218s
Sym-NCO (Kim al., 2022)
5.738
0.68%
0.077s
GCN (Joshi et al., 2019)
5.776
1.53%
0.008s
UTSP+MCTS (Min et al., 2024)
5.818
2.30%
0.063s
DIMES+S+AS (Qiu et al., 2022)
5.859
3.01 %
2.884s
DIFUSCO (Sun & Yang, 2023)
5.709
0.38%
0.388s
T2T+GS (Li al., 2023b)
5.690
0.04%
1.164s
GNNGLS-Is (Hudson et al., 2021)
5.693
0.10%
1.080s
MatNet-8x (Kwon et al., 2021)
5.857
2.97%
0.056s
MatPOENet* (Ours)
5.781
1.63%
0.059s
MatPOENer 128x (Ours)
5.726
0.66%
0.296s
MatDIFFNe--2OPT (Ours)
5.721
0.59%
0.509s
Table 19: Performance comparison on standard symmetrie TSP-100 test set.
Method
Tour length (1)
Optimality gap (1)
Time/instance
Concorde (Optimal)
7.756
0.404s
AM (Kool et al., 2018)
7.951
2.52%
0.026s
POMO (Kwon al., 2020)
7.883
1.64%
0,205s
Sym-NCO (Kim et al., 2022)
7.927
2.21% %
0.078s
GCN (Joshi al., 2019)
8.307
7.08%
0.01
UTSP+MCTS (Min et al., 2024)
8.069
4.46%
0.223s
DIMES+S+AS (Qiu et al., 2022)
8.061
3.94%
8.508s
DIFUSCO (Sun & Yang, 2023)
7.845
1.14%
0.409s
T2T+GS (Li et al., 2023b)
7.788
0.13%
1.198s
GNNGLS-LE Is (Hudson et al., 2021)
7.837
1.05%
1.389s
MatPOENer*-Br (Ours)
8.127
4.78%
0.262s
1 (Ours)
7.933
2.28%
0.758s
MaDDIFFNet-2OPT (Ours)
7.840
1.08%
0.769s
Table 20: Tested 45 TSPLIB instances of scale range:
[14, 195]
att48.tsp
berlin52.tsp
ch130.tsp
c0tp50ttsp
eil101.tsp
eil51.tsp
ei176.tsp
kroA IroAA10.tssp
kroC100.tsp
kroD100.tspp
105
pr76.tsp
rd100.tsp
st70.tsp
bayg29.tsp
bays29.tsp
brg 180.tsp
fri26.tsp
gr24.tsp
1s48.tsp
gr96.tsp
ulysses16.nm
ulysses22.tsp
bier127.tsp
d198.tsp
150.ts0
kroB 100.tsp
kroB 150.tsp
kroE100.tsp
pr pr107.tsp
pr pr124.tsp
pr136.tsp
pr144.tsp
pr152.tsp
rat195.tsp
rat99.tsp
u159.tsp
brazil58.tsp
dantzig42.tsp
gr17.tsp
gr21.tsp
hk48.tsp
swiss42.tsp
burmal4.r 14
into consistent format of "EDGE TYPE: EXPLICIT" and FULLIMATRIX". with all distances scaled to j0, 1]. The results are given Table 21.
The results demonstrate that our models are also effective problem instances with completely unseen distributions and varying sizes. We would like to kindly remind the readers that an important aspect is that we the first evaluate the TSPLIB instances without any initial knowledge from node coordinates. Thank you again for enhancing the completeness of our evaluation. The task of improving the generalizability towards real-world cases planned for future research.
37

---

Published as a conference paper at ICLR 2025
Table 21: Results TSPLIB instances.
Method
Avg. tour length
LKH3
4.8622
Greedy
5,4455
MatPOENet
5.0811
MatDIFFNet
5.2744
F.7 FULL EXPERIMENTAL RESULTS
For your quick reference, we present complete version of experimental results in Table 22, supple- mentary to Table the main context, containing both major results and most additional results. substantial quantity of empirical investigations conducted to provide comprehensive evaluation of our proposed framework and models.
G FURTHER DISCUSSIONS
G.1 NOTE ON LKH
We have been conducting a preliminary study on the boundary of the strong heuristic LKH when dealing with general TSP beyond the 2D Euclidean space where holds an overwhelming advantage. LKH is a heuristic with three main components: the a-nearest measure, node penalties, and the k-opt searching algorithm. It operates in the following steps:
Compute the a-Nearest Measure: The a a-measure an edge is calculated based on the length of the minimum 1-tree of graph and the minimum 1-tree containing that edge. The oe-meauures are used to specify the edge candidate set.
2. Node Penalties: LKH employs subgradient optimization technique obtain penalties each node and modifies the distances.
3. Search Solutions by O-tpt: k edges in the current tour are exchanged by another of edges from the candidate sets to improve the tour until no more exchanges can be found.
There is fatal flaw of LKH on binary TSP (such the SAT-distributed TSP in our case) in the first step of computing aii, j). For a discrete TSP problem instance, a<i.,) can only be either 0 or 1. This implies that many edges may have the same aii, value of O, making difficult to distinguish effective candidates and consequently leading to suboptimal performance on such discrete instances. Moreover, unlike the generation of HCP instances in experiments where the randomly sampled from a uniform distribution and zero-length cycle is forced in each problem matrix, the 3SAT-distributed TSP cases are more complex due to their highly structured translation from variables and clauses to the HCP distance matrix. One possible approach to address this problem use learned neural mapping network transform some difficult binary distance matrices into the more softened and thus easier space to assist LKH solving.
and zeros
G.2 NOTE ON THE SCALABILITY AND APPLICABILITY
Scalability remains one of the most frequently encountered challenges the field of neural combina- torial optimization. The following is a conclusion of our observations and clarifications regarding the scalability issue, based on our investigations and experiments.
Current Status of General TSP Solving. Firstly, as demonstrated by the main experiments (Ta- ble 22), although the scale the tested instances is not extremely large, the baseline TSP solvers (including both neural methods and strong heuristics such LKH3) do not yield satisfactory results within an acceptable time frame. This indicates that for the relatively undercxplored task of general TSP, the solvers at the current scale still insufficiently effective, not to mention generalizing to larger scales.
A Shared Convention. From peer perspective, common phenomenon can be observed in top published literature targeting "multi-task", "general", and even "universal" combinatorial optimiza- tion, that evaluation on problems with up 100 nodes is generally acknowledged convention.
38

---

Published as a conference paper at ICLR 2025
Table 22: Full experimental results. Reported data for ATSP and 2DTSP are tour length. "Single": models trained and tested on each problem respectively. "Mixed": unified models trained with a mixture of 4 tasks each scale. Asterisked (*): unified model trained with mixture of 4 tasks and 3 scales. "8x": representing 8 parallel trials for sequential model solving. BQ-NCO (Drakulic et al., 2023) and GOAL (Drakulic et al., 2024) reports their results on ATSP but have not been open-sourced yet. We make estimation according to their reported optimality gap for reference only. Bold: the best score of neural solvers in each column. Underlined: the best solved length over the full set for reference. Red box and blue box : ours that outperform LKH with max. trials= and max trials=0000 respectively. Time: the average time (seconds) per instance solving over each
line, with batch size set 1.
Methods
Train Data
ATSPL
2DTTSP
DHCP (L.), PR3)
35AT (L). FR1)
|| Avg. L.]
Arg. Gapl
Avg. FK"
Time
Gunabii
1.5349
3.8347
0.0300
100.00%
0.1000
100.00%
1.3424
100,007
0.135
LKH (10000)
1.349
3.8347
0.0908
99.92%
0.0000
100.00%
1.3426
0.01%
99, 96%
0.327
LKH (500)
15339
3,8347
0.0155
99.40%
0,0000
1000001
1.3438
0.11%
99.72%
0.038
Neanost Neighhee
200099
4.5021
1,8556
0.485
3,0504
0.32%
3.3428
149 024
0.40%
0.000
Farthest Insertio
1,7070
3.9995
3.3136
1.76%
4,8816
0.00%
3.4679
158.344
0.88%
0.800
MaiNet
ATSP
1.5871
4.2612
2.9608
1. 1125
3,4772
0. 0.56%
3.0716
128 82%
0.84%
0.005
MatNee 8x
ATSP
1,5391
3.9135
1,5476
9.28%
1.9184
5.08%
2.2646
67.215
7.68%
0.036
MutNet
Mised
1.6359
3.9114
0.9740
27.60%
13 10.0%%
2.4967
05. 55.95%
0UNS5
MaiNes-Bs
Mised
1.5645
3.8478
0.1966
1.803
71%
11.1%%
Spale:
Non-MuNNas-POE
Mised
1.7138
3,8090
0.8400
0.5760
50
1.7571
80%
POB
Mixed
1,6057
3.8695
0.5444
53.28%
0.3344
57.52%
19.621
0.035
DIMES
Mixed
2,2335
4.16%
29448
2.67%
2,6660
2.12%
3.01335
123
2.39%
0.835
DIMES-AS/100)
Mixed
1,6990
3,9092
0.4996
60. 12%
0-2828
77. 125
18266
17.90%
0.522
DIMES A5/200)
Mixed
1,6439
3,8809
0.4964
61.92%
0.3058
75.10%
L,3695
16.92%
68.54%
1.124
MarPOENee
Mixed
1.6455
3,3643
0.8676
60.
0-4540
61 885
1,7076
27.310
47.24%
0.006
MarPOENNe 8x
Mixed
1.5695
3.8389
0,1760
68%
0.0112
98 58%
1.3989
4.21%
90.78%
0.043
37
MacPDENer
Mixed
1.5933
3.8632
0.4152
62.26% 2415
0.1528
84 84%
1.5156
12.01%
73.56%
0.006
18
MaiPOENee -8x
Mixed
1,5006
3.8372
0.0556
94.44%
0.0008
99.92%
1.3610
1.39%
97.18%
0.043
19
Gurohi
1.5545
5,6952
0.0000
100 00%
0,0000
10000055
1.114
100.00%
0.296
20
LXH (10800)
1.5548
5,6953
0.0000
100 00%
0.3764
74 80%
3.85%
40%
0,513
LKH (500)
135557
5.6964
0.0000
100.00%
0.57%
10%
1.9329
6.65%
30.90%
0,059
Neurest Neighboe
20945
6.9977
5,1120
0.00%
3.9872
0.00%
5.0548
178.90%
0.00%
0.000
Parthest Insertion
1.8377
10,7964
0.00%
5.5893
0.001
MatNet
ATSP
1.5755
7.3618
0.00%
4.7022
150
5.90%
0.007
MatNet-B 8x
ATSP
1,5612
6.9455
0.6036
241
6.3668
0.00%%
3.860
24.62%
MatNee
Mixed
1,3098
6.000
0.286
1.1900
30.52%
36.9515
20.63
OUNUT
MutNer
Mixed
1.7340
5.864
0.3056
1 1225
0.299/2
73.081%
2,0513
13.184
72.30%
0U007
Non-MaNNas-POE
Mised
1/3686
5.8855
10332
1.1416
31 325
2.4817
0.007
29
Non MaiNet POD 3x
Mixed
1.7988
53818
0,00
72.
1.0020
34. 76%
2.2566
24.51%
49.70
0.060
30
Rand- MatNer-PUl
Mixed
1,8282
6.0207
0.5300
1.4604
22 12%
2. 2,5568
41.07%
26.86/6
0L0N6
31
Rand- Maie-MaNN---PPF PP3F-8s
Mised
1.7513
5.8853
0. 3096
71 1.5346
0.4708
50 8.4%
11442
15. 10%
66. 18%
0.063
32
Fl MaiNe: POE 8s.
Mised
1,8370
6,0962
0.1820
82 3013
0.6050
55, 55.72%
2. 2.1828
20.44%
69.26%
0J064
Sale 8
35
MaiNet Random 8x
Mised
2.1065
5.8981
0.8560
33.20/%
L.1620
30. 30.48%
2. 2.5051
38.2256
31.82%
0.064
34
ManNet- MunNes-Triinnli--k Trainsble-8x
Mised
1,8925
5.8157
0.4148
0.5011
55.52%
2.1560
15.064
61.24%
0U871
35
GLOP
Single
1 1,8885
6.6499
3.7244
4.9816
0.76%
4.3111
137 87%
0.80%
0.115
DIMES
Mised
2,3341
6.6271
3.1788
1.50%
5.3656
0.12%
4.3764
141 141.47%
0,84%
0.055
DIMES-ASC100)
Mised
5.9447
20.44%
2.4528
35.33%
2.015
Mised
1.6794
5.9194
0.5000
54.2098
1.42%6
23. 23.36%
2.3821
31.43%
3,879
MaPPDENesax
1.5643
5.7042
0.0652
0.1888
81.72%
1,8806
3.76%
87.62%
0.066
MalPOENNel
Mixed
16681
57764
0.1444
201
1.3644
27.08%
2.2416
23.681
Mixed
16417
5:7283
0.0172
98.2816
0.2556
77.60%
1,9082
5.29%
57.94%
0.067
MaPPOENe
Mixed
1.6753
5.9633
02213
0:8122
40%
2.1417
18.17 17%
44.44
0.008
MaPPOENar--S
Mised
1.6285
5:7575
0.0290
97.30%
0-1172
88.44%
188888
3.58%
92.82%
0.677
MasPOENer-Sx (N d)
Mixed
1.8799
5.9742
0.4548
0.3290
75%5%%
2.1595
19.15%
68.00%
0.062
MasDIFFNNe
Single
2,0713
5.7956
2.0992
1532%
199000
95 10%
2.5033
38. 11%
56.74%
0.157
46
MunDiHNNes2OPP
Single
1.7186
5.7279
08524
440058
0
98.64%
210744
14.40%
71.36%
0.165
47
MoIDiPFNer
Mised
1.8385
6:2332
2 26668
15.768
0.1122
94 68%
3.5609
41 356
55, 23.2
0.155
48
MadDIPPNin-OOPP
Mised
16591
S.8619
0.8192
44 521
0.0496
05 64%
2.0975
15.73%
70.06%
0.164
49
Gunobi
1.5661
7.7619
0.0900
100 00%
0.0000
100.00%
2.3050
100.00%
0.689
50
LKH (10800)
1.5674
7.7709
0.6900
100 08%
1.0088
44 80%
3.5848
10.54%
72.40%
0.811
51
LKII (500)
1,5704
7,8015
0.0000
100.00%
1,6656
28.08%
2.7594
18.33%
64,01%
0.095
Nearest Neighbor
2.1321
9.6696
5.41166
1130%
4.3236
0.00%%
6.399
0.02
Fanihest
19133
8.4847
1,1256
33,5160
0.00%
9.269
13.32%
0.003
MatNet
ATSP
1.6217
19.0644
8606
0.00%
743
0.00%
0015
MaiNes-8x
ATSP
1.5083
11,5106
15,3216
0.00%
631
0.00%
0.094
MatNet
Mixed
19649
8:2551
0.9766
681
2.0408
13.84%
3.3146
22.76%
0,015
Solle N' se 106
MatNes-8x
Mixed
19210
8.0028
0.3640
09 600
0.7740
50.76%
2.7904
19.664
60.18%
0.895
58
GLOP
Single
1.5491
8.3849
2,7850
2.00%
6,4250
0.08%
4.9833
113.84%
1,04%
0.176
59
BQ NCO
ALSP
1.5904
0.016
60
GOAL
ATSP
1.5711
0.039
61
Non-MuNNes-POE
Mixed
2.03077
8.9929)
1.0616
28.76%
1.2044
36.89%
3.3449
43.43%
27.83%
0,015
62
Non MaiNet- POE-8x
Mised
1 19600
8.7895
0.4420
63.60%
1.0796
31 11.80%
3.0728
31.77%
47.70%
0.093
63
DIMES
Mised
2.5186
9.5777
3.8064
1.10%
3.8054
0.00%%
6.4018
174.5246
0.58%
0.124
64
DIEMS-AS(ION
Misod
1 1.6088
8.3390
0.8490
24 000
2.8040
7.16%
3.4230
46 745
15.58%
8.377
65
MarPUENe:
Mised
19183
8.2987
0.994
90.28%
L.1704
32 32%
2.8405
22.06%
61.30%
QUBIT
66
MaPDeNNa-xx
Misdd
1.3655
8.1719
0.0152
99.48%
0.2440
77.12%
2,5717
10.280 289
88.30%
0.94
67
MaPPOlNNe
Mised
1.1007
8:2703
0.0796
92.12%
1.2855
26.0474
2.8616
22.71%
59,05%
0.017
MarPOENer
Mised
1.7607
8.8817
0.0012
0.3244
70.92%
9,01%
MarDiHHNee
Single
199422
7:9684
4.45%
2.00%
0.14004
98. 44%
3.6014
54.45%
0.105
MabDiHNe--OOP
1.7165
7,8482
1.1404
37.72%
0.1240
99 98.60%
2.6622
15.00%
68.16%
0.112
MaIDiFNNel
Mhsdl
1.8763
8,0030
1.2524
1.1040
90
1.5564
52.
0.102
MatDiFFNer
Mixed
1.6965
$.1804
0.9148
43.04%
0.0952
91.44%
2:7217
16.71%
67.24%
0.114
39

---

Published as a conference paper at ICLR 2025
Table 6 presents a recent review of these works, ranging from the applicable problems to the evaluated scales of tasks.
Technical Limitations. The training of MatPOENet consumes O(N²) space (O(N2) space for the attention mechanism and ((N) space for N rollout iterations), making impractical to run on large-scale instances (e.g., N 500) a single GPU. However, shown in Table 5, UniCO's ability to learn larger-sealed instances can be achieved by switching to different learning paradigms. For example, a modified version of heatmap-based MatPOENet performs well on N 500 through vanilla supervised learning. Another approach to improving the ability to solve large-scale combinato- rial optimization problems is to resort to the divide-and-conee and has been proven feasible and effective (Ye et al., 2024b; Fu et al., 2021; Luo et al., 2024). In this instances remains of irreplaceable importance. We
paradigm, which also a consensus
context, a strong solver for mall-to-mmeium-- have readily incorporated the latest work GL.P,, which significantly enhances MatNet's scalability. Moreover, the promising generative models for discrete optimization can be considered as detailed in Appendix G.4, which is also planned for our future work.
G.3 DISCUSSION OF MATPOENET V.s. MATDIFFNET
Trade-off among Quality, Efficiency, and Scalability. As shown in the main result table, MatPOENet excels at smaller instances as a strong yet compact solver with faster inference and more transparent training process but can hardly scale due its RL nature, whereas MatDIFFNet has more potential to scale to larger cases with more accurate proximity of the solution space (especially in continuous 2DTSP and complex discrete space, e.g., 3SAT) via its generative design but consumes much longer time to train and infer due to its heavier architecture and diffusion processes.
Comparison of Stability. MatDIFFNet does not directly generate solutions but decodes the heatmap to obtain them. Consequently, the solution quality of MaDIIFNNtt is less stable than that of Mat- POENet. Specifically, in the case of MatDIFFNet, there an error in predicting a particular node, it will directly impact the predictions of all subsequent nodes. In contrast, MatPOENet generates solutions step by step and can select better subsequent nodes based on the current state even if there is an error in particular node. This instability also results in the relatively poor performance of MatDIFFNet when solving the Hamiltonian cycle problem (HCP).
G.4 DISCUSSION OF GENERATIVE COMBINATORIAL OPTIMIZATION
Strong scalability of neural backbone and sparsification. In addition to the fact that SL.-based neural networks generally outperform their RL counterparts in terms of scalability, MatDIFFNet employs GNN as the backbone encoder, which enables convenient graph sparsification (e.g.. k- nearest neighbor) on TSP. This effectively reduces computational overhead and improves inference efficiency. As demonstrated in previous research (Qiu et al., 2022), training TSP solvers with sparsification factor of, for example 50, significantly reduces the memory and time overhead when training graphs with while maintaining competitive performance. This is also one of the crucial reasons we choose general TSP, an edge-hased selection task, as the endpoint for problem reduction. In contrast, such edge sparsification scheme cannot be adopted when learning solve most node-based selection problems, such as vertex cover and independent set.
Rich expressivity of learning solution space distribution. In our investigation of recent literature on neural solving of combinatorial optimization, especially for graph problems like TSP, notable observation is the growing attention and demonstrated performance of diffusion-based generative models (Sun & Yang, 2023; Li et al., 2023b). From DIFUSCO and T2T to our proposed MatDIFFNNt and its future versions, generative models possess powerful expressive and modeling capabilities. They can learn the distribution of high-quality solutions conditioned on specific problem instances, which is beneficial for providing a good starting point or exploration direction in the solution space. In the context of combinatorial optimization, this means they can potentially generate a variety of solutions that might be closer to the optimal one, rather than being limited to single few predicted solutions as in some traditional methods.
Good prospects of consistency model and unsupervised tuning. Moreover, the latest research on generative combinatorial optimization indicates that diffusion models can be improved through
40

---

Published as a conference paper at ICLR 2025
consistency training (Song & Dhariwal, 2023). Consistency models learn to map directly from different noise levels to the optimal solution for a given instance, thereby achieving a high-quality, rapid one-step generation solution. This approach reduces the number of iterations and enhances efficiency. Therefore, we will introduce consistency models into our framework the future to optimize the inference speed and computational efficiency of diffusion models. Also, suggested in works (Sanokowski et al., 2023; 2024), diffusion models finely foster the applicability of unsupervised learning of combinatorial optimization.
For these reasons, we believe it appropriate to present MatDIFFNet in parallel with MatPOENet in the main context. This represents both conventional powerful autoregressive solvers using reinforcement learning and model with wider extendability and value for further exploration. We maintain that this provides more comprehensive view of the current trend in neural combinatorial optimization.
41


Reviews:
[{"review_id": "9sgdXAgVDl", "reviewer": "Reviewer_WPxC", "summary": "This paper proposes a unified neural solver framework called RedCO, which uses problem reduction techniques to map different combinatorial optimization (CO) problems to the general Traveling Salesman Problem (TSP) format. Two novel neural solvers, MatPOENet and MatDIFFNet, are introduced to handle matrix-encoded inputs and solve these problems efficiently. This work aims to extend neural combinatorial optimization beyond specific problem types by providing a scalable solution for problems like asymmetric TSP (ATSP), directed Hamiltonian cycle problems (DHCP), and 3-Satisfiability (3SAT).", "questions": "1. When converting various combinatorial optimization problems to TSP instances, are there cases where the reduction process fails or underperforms due to problem characteristics? How does the method handle these instances?\n\n2. Given that MatDIFFNet has longer inference times due to complex diffusion steps, are there plans to optimize the model architecture or algorithm to improve inference speed and computational efficiency?\n\n3. In multi-task training, does the interaction between different tasks lead to performance drops in any specific task? Is there a clear mechanism in the model to handle task weight allocation and interdependencies?\n\n4. How robust are MatPOENet and MatDIFFNet when the input data contains noise or incomplete information? Were there any robustness tests conducted?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The introduction of MatPOENet and MatDIFFNet, which use Transformer-based and diffusion-based models, respectively, showcases the application of advanced neural network structures to solve matrix-encoded TSP problems.\n\n- The RedCO framework offers a novel approach by unifying different combinatorial optimization (CO) problems through reduction to a general TSP format. This reduction expands the scope of neural solvers to tackle diverse problem types in a single architecture.\n\n- RedCO's capability to handle non-metric, asymmetric, and discrete TSP instances, unlike traditional Euclidean-focused TSP solvers, significantly broadens its applicability.\n\n- The RedCO framework is designed to incorporate various solver types, including existing methods like DIMES, showing the framework's modularity.", "weaknesses": "- While the framework performs well for medium-scale problems, its efficiency and feasibility for large-scale, real-world instances (e.g., with tens of thousands of nodes) are not thoroughly demonstrated or tested.\n\n- The use of complex neural models like MatPOENet and MatDIFFNet makes it difficult to understand the inner workings and decision-making processes of these solvers. More interpretability features or case studies would be beneficial.\n\n- The paper mainly focuses on synthetic data for testing, with limited discussion on how the models would handle real-world problem instances that could have different statistical properties.\n\n- There is little exploration into how the proposed solvers manage noisy or incomplete data, which is common in practical applications.\n\n- The MatDIFFNet, while powerful for certain problem types, is computationally intensive, which may hinder its use for larger instances or require additional optimization strategies.", "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": "0KV8Nlw5xs", "reviewer": "Reviewer_rbCa", "summary": "Authors propose RedCO, to unify a set of CO problems by reducing them into the general TSP form featured by distance matrices. RedCO demonstrates the potential to efficiently train a neural TSP solver using a diverse range of CO instances, and can also be adapted to specialize for specific problem types.", "questions": "1. Table 2 shows that MatPOENet and MatDIFFNet outperform LKH in solving 3SAT problems, but they tend to produce worse results in most other scenarios. Could you provide some explanations for this?\n2. How does RedCO perform on standard TSPs (Symmetric TSPs)?\n3. In line 268, the POE is based on $f(x) = 1/cosh(100x)$, can you give more introduction of the empirical function?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is well-written and easy to understand.\n2. As far as I know, this is the first study attempting to create a general framework for learning various COPs in a reduction manner.\n3. The experiments conducted are thorough, and the results effectively showcase the framework's capability to handle arbitrary matrix-encoded TSPs.", "weaknesses": "1. The organization of the experimental section is lacking. With seven research questions (RQs) presented, the lack of clear categorization makes this part of the paper somewhat difficult to navigate.\n2. The results for DIFUSCO and T2T are not included. It is noted that MatDIFFNet performs well on 3SAT problems, which is developed upon DIFUSCO and T2T.\n3. While the specific problem reduction is detailed in Appendix A, it would be helpful to have a more detailed introduction to the reduction principles and the applicable COPs. Specifically:\n   - What types of COPs (or what properties must COPs have) can be reduced to a general TSP?\n   - What considerations should be taken into account when performing this reduction?", "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": "EBPgsun4LG", "reviewer": "Reviewer_xiNJ", "summary": "This paper presents an interesting approach to dealing with multi-task CO by transforming several CO problems into equivalent TSPs. This paper also proposes two new solvers, MatPOENet and MatDIFFNet, to solve the following TSP.", "questions": "1. MatDIFFNet is trained on 8 NVIDIA H800 80GB GPUs with Intel Xeon (Skylake, IBRS) 16-core CPU is super computational resource consuming, I am curious about the ablation experiments on computational resources.\n2. The test questions in the article experiments are too limited, this article mentions applicability for ``P ≤P general TSP or P in matrix format (VC, Clique, VRPs, FFSP, MIS, etc.)`` etc., I would highly recommend to introduce evaluations on more CO problems to respond to my concerns on applicability.\n3. In Line 1137, you mention that ``Also, they generally evaluated their proposed methods on no larger than 100 nodes of TSP/VRP instances, with a major emphasis of methodological innovations rather than eager pursuit of scalability at sheer engineering level.`` What means the sheer engineering level? Also, it seems that this paper also mainly focuses on no larger than 100 nodes. Please provide a clear explanation.\n4. This paper uses a unique test problem design, which I think requires the authors to implement more comparative algorithms (e.g., GOAL, MVMOE) on the problems they cover for experimental validation.\n5. The results in Table 5 are not sufficient to illustrate performance on larger-scaled data, I think you should provide experiments without the aid of an external process to explore whether the model has the ability to scale up. Also, this paper does experiments on scales of 20-100, and I doubt that it makes sense to compare methods that address large-scale CO problems such as GLOP.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. This article is well-written and reasonable.\n2. The author has carried out abundant experiments and discussions.", "weaknesses": "I think this article has two major weaknesses that should be considered.\n1. This paper adopts a quite special modeling approach, and its applicability is worrying. I doubt the effectiveness of reducing multi-CO problems into the general TSP form featured by distance matrices. \nAccording to Fig. 1, you show that NP problems can be transformed into SAT, I am concerned if this part can be proved. For some problems, the transformation into TSP is itself an NP problem if you want to maintain the Found Rate ``FR`` (e.g., CVRP, as mentioned in Appendix D.2.4, ``first clustering points and then solving each cluster as a TSP`` will harm the FR), and even if it can be transformed into TSP, the time complexity of such transaction may increase dramatically.\n2. Some of the experiments in this paper are not clearly described. I tried my best to find out but it is still not clear what the exact settings of the * version, single, and mixed in Table 2 are.", "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": "rlZlkTKqHp", "reviewer": "Reviewer_qSht", "summary": "This article focuses on multi-task CO problems, proposes a solution method that is general for several CO problems and presents two efficient solvers.", "questions": "1. In RQ2 you show a comparison of solution times and results with the LKH method. The reason you showed efficiency in this experiment compared to LKH seems to come entirely from superior performance on the 3-SAT problem. I don't think it is fair to take Average L in this case. I am more curious as to why LKH performs poorly on the 3-SAT problem and where MatPOENet and MatDIFFNet excel in this problem. Can you provide a visual example to help me understand this result intuitively?\n2. For solving efficiency, I think this paper should be compared more with Gurobi for efficiency. I am very curious about the results of this part. I also suggest you add time as reference in Table1.\n3. I am having trouble understanding the specific N and d settings for variants in the ii) part of RQ3 and especially in Table 4. I need more explanation about it.\n4. What is the significance of MatDIFFNet? Based on the results so far (ignoring the future work you mentioned) it looks like its lagging behind in performance and efficiency as well as training efficiency. I would suggest deleting this section or putting it in the appendix. Also The authors say in RQ7 that MatDIFFNet has the potential for more accurate solution space for larger scale instances while mentioning in the limitation that ``MatDIFFNet has the potential for direct solving of larger instances but is currently yet to be implemented.`` But I can't find any evidence for this. But I can't find any evidence for this , please explain this.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The Problem reduction of this paper has theoretical support.\n2. The proposed methods of this paper has advantages in terms of effectiveness.", "weaknesses": "1. The RedCO approach proposed in this paper is not intuitively applicable to a wide range of CO problems. I think the value of multi-task CO should be reflected in its applicability to most CO problems.\n2. The contribution of this paper is weak, translating these problems into a TSP is not a new idea and TSP solver is quite well developed.", "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)