COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Authors: Jiale Ma
Wenzheng Pan
Yang Li
Junchi Yan
Venue: ICML 2025 poster (2025)
Keywords: Neural Combinatorial Optimization
Generative Modeling
Primary area: general_machine_learning

Abstract: Despite rapid progress in neural combinatorial optimization (NCO) for solving CO problems (COPs), as the problem scale grows, several bottlenecks persist: 1) solvers in the Global Prediction (GP) paradigm struggle in long-range decisions where the overly smooth intermediate heatmaps impede effective decoding, and 2) solvers in the Local Construction (LC) paradigm are time-consuming and incapable of tackling large instances due to the onerous auto-regressive process. Observing these challenges, we propose a new paradigm named Adaptive Expansion AE with its instantiation COExpander, positioned to leverage both advantages of GP and LC. COExpander utilizes informative heatmaps generated by a global predictor, which is learned under the guidance of locally determined partial solutions, to in turn direct the expansion of determined decision variables with adaptive step-sizes. To ensure transparent evaluation, we further take the lead to canonicalize 29 benchmarks spanning 6 popular COPs (MIS, MCl, MVC, MCut, TSP, ATSP) and various scales (50-10K nodes), upon which experiments demonstrate concrete SOTA performance of COExpander over these tasks. Source code and our standardized datasets will be made public.

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Jiale Ma 12
Wenzheng Pan"
Yang Li
Junchi Yan
Abstract
ing (near) optimal solutions within reasonable time remains daunting challenge. Over the past decade. the neural com- binatorial optimization (NCO) community (Zhang et al., 2023; Guo et al., 2023; Wang et al., 2024) has fostered copi- ous work to explore the potential of data-driven methods for CO solvers and have shown considerable promise in terms of both effectiveness and efficiency of problem solving.
Despite rapid progress in neural combinatorial optimization (NCO) for solving CO problems (COPs), as the problem scale grows, several bot- tlenecks persist: 1) solvers of the Global Pre- diction (GP) paradigm struggle in long-range decisions where the overly smooth intermedi- ate heatmaps impede effective decoding, and 2) solvers of the Local Construction (LCC) paradigm are time-consuming and incapable of tackling large instances due to the onerous auto-regressive process. Observing these challenges, we propose new paradigm named Adaptive Expansion (AE) with its instantiation COExpander, positioned to leverage both advantages of GP and LCC COFx- pander utilizes informative heatmaps generated by a global predictor, which is learned under the guidance of locally determined partial solutions, to in turn direct the expansion of determined deci- sion variables with adaptive step-sizes. To ensure transparent evaluation, further take the lead to canonicalize 29 benchmarks spanning 6 popular COPs (MIS, MCI, MVC, MCut, TSP, ATSP) and various scales (50-10K nodes), upon which exper- iments demonstrate concrete SOTA performance of COExpander over these tasks.
Learning- based solvers for CO typically employ neural net- works to generate neural predictions for either solution con- struction or search guidance. Given that divide-and-conquer (D&C) frameworks (Ye et al., 2024b; Zheng et al., 2024) and solution optimization approaches (Chen & Tian, 2019; Ma et al., 2023) are theoretically orthogonal to and practi- cally applicable over the main solving stage, in this paper, we focus on the core part of NCO, i.e., the acquisition of so- lutions for COPs, and categorize the mainstream neural CO solvers into two paradigms' based on the way the solutions are constructed. As the first type, Local Construction (LC) methods (Kool et al. (2018); Berto et al. (2024); Drakulic et al. (2023); Pan et al. (2025), etc.) cast COPs as Markov Decision Processes (MDPs) and the neural networks are trained to predict the best next-step action given the current state. This process continues until complete solution is assembled, as depicted in Fig. 4 (a). While I.C solvers effec- tively decompose the solving process into the step-by-step construction to leverage local states for the next decision, they suffer from a lack of global perspective and encounter scalability problems due to the laborious and myopic auto- regression. On the other hand, Global Prediction (GP) approaches (Joshi et al. (2019); Qiu et al. (2022); Sun & Yang (2023); Li et al. (2023; 2024; 2025), etc.) use neural networks to globally predict the likelihood of each node or edge being selected, and then decode the probability heatmaps (via heuristics as simple as greedy) to obtain solu- tions, as shown in Fig. 4 (b). This paradigm provides global guidance mapped from the entire graph structure for con- structing the solution. However, as problem scales increase, the predicted heatmap through one-shot inference tends to be overly smooth (with many noisily similar values), hinder- ing its guiding effect for the subsequent decoding procedure. We delineate these observations in Appendix B.2 and B.3.
1. Introduction
Combinatorial optimization problems (COPs) possess exten- sive applications in diverse fields including logistics (Wang & Tang. 2021), transportation (Baty et al., 2024), supply chain management (Singh & Rizwanullah, 2022), and net- work design (Paschos, 2014), in search of optimal solutions within discrete states. However, due to the inherent NP- hardness for most (especially large-scale) COPs, approach-
'Equal contribution 'Sch. of Artificial Intelligence & Sch. of Computer Science, Shanghai Jiao Tong University 'Shanghai Innovation Institute. Correspondence to: Junchi Yan <yyn- junchi eeeeesttcco.. wwt.ttueeuu.ooooo edu. cn>. This work is partly supported by NSFC (62222607, 623B 1009). Code available at github repository.
The issues of these two paradigms can be generalized as
Proceedings of the 4rnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
'A paradigm is detached from any particular model or solver.

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
opposing extremes in the decision granularity, i.e., the quan- tity of variables determined at each step, where GP leans entirely global prediction while LC depends solely on lo- cal information for moblem-ssllving We note that diffusion- and consistency-basee solvers (Sun & Yang, 2023; Li et al., 2023; 2024) constitute a distinct subset of GP solvers, en- deavoring to generate globally complete solutions through sequential denoising process. However, they still fail to ensure the intermediate steps interpretably direct the deter- mination of variables, for the ultimate solution is unrevealed until the final stage. Hence, a promising direction is to explore a principled mechanism to adaptively control the decision granularity in each forwarding step, replacing the current practice of using a fixed step size, e.g., resolving variables one a time or updating them all at once.
Definition 1.2 (Solving Paradigms), Given VDP(N, k), we defined the following paradigms based on and N:
When & = 1, all decision variables are determined in a single step, this process is defined as Global Prediction.
Whhen k N, each step determines exactly one variable, this process is defined as Local Construction.
When 1 < k < N, the process is defined as Expansion. Further, if the difference between consecutive steps is not constant, the process is referred to as Adaptive Expansion.
to-full" to an adaptive "partial-to-full" manner of neural mapping. Instead of predicting full solutions from proba- bilistic noise, the "partial-to-full approach starts from state with several decision variables already determined, effectively narrowing the search space. The reasoning pro- cess, thus guided, attentively leverages the most informative portion of the inferential output of the neural model in each determination round, thereby leading to more stable and consistent predictions. On the other hand, in contrast LC solvers, COExpander evolves from the fixed "next-token" to a flexible "next-few-token" manner of solution construc- tion and incorporates global guidance. This progress chiefly stems from the supervised global predictor in COExpander which furnishes more comprehensive information in a single inference than ICC solvers, i.e., providing the probabilistic estimation of all decision variables rather than merely that of the next node to be selected. This augments both efficiency and scalability while sustaining the quality of solutions. We highlight our main contributions as follows:
Definition 1.1 (Variable Determination Process). Given an optimization problem with N decision variables, we define Variable Determination Process VDP k) as an iterative procedure transitioning from complete uncertainty to full determination in steps. Let do, di..... d 1 be the number of determined variables each step, which satisfies do < d1 <. .... < dx-1, with do 0 and dx- = N.
To fulfill the above motivation, we first define new paradigm for NCO solving, namely Adaptive Expansion (AE). Paralleling GP and LC, AE encompasses a model- agnostic training and solving pipeline that orients at fully utilizing the intermediate state information during problem solving while maintaining an adaptively controllable gran- ularity regarding the step-size of the decisive predictions produced by the neural networks. Further, we devise a novel neural solver COExpander as a forerunner instantiation of AE, where informative heatmaps are generated by global predictor learned under the guidance of locally determined partial solutions, and in turn, guide an adaptive process to expand the set of determined decision variables. Specifi- cally, sketched in Fig. 1, embedded masks representing random intermediate solving states are fed as prompt input along basic graph features to train COExpander to predict the full distribution under partial guidance. At solving stage, iterative determination processes are performed, and in each round only the most convincing components of the output heatmap is accredited to determine arbitrary number of decision variables and update the neural masks denoting current partial solution state that prompts the next iteration.
We propose the Adaptive Expansion (AE) paradigm and the COExpander solver for COPs. It bridges the global prediction (GP) and local construction (L.C) paradigms via utilization of a partial state prompted solution genera- tor, replacing the rigid decision with adaptive step sizes beyond auto-regression and one-shot solving.
To establish a unified protocol for performance evaluating and reporting for COPs, we re-wrap 5 non-learning base- line solvers (Appendix D) and re-cononicalize 29 standard datasets (Appendix E). providing a just and generalizable benchmark for 6 commonly studied COPs.
Compared with previous neural state-of-the-arts (SOTA), COExpander has reduced the average optimality drop on 6 COPs from 3.807 % to 0.657%, with speedup of 4.0x. Besides, COExpander shows good cross-scale and cross-distribution generalization ability on real-world and ultra-large instances within each problem type.
In Def. 1.2, we provide a formal formulation of AE as well as the comparison with the other two paradigms. Notably, AB combines the merits of both and rectifies their individual shortcomings by incorporating guidance derived from both global and local perspectives. On the one hand, compared to GP solvers, COExpander evolves from the previous "noise-
2. Related Work
GP Solvers. Different ways of learning have been applied to generate effective heatmaps globally. including supervised learning (SL) (Joshi et al., 2019; Fu et al., 2021), unsuper- vised learning (UL) (Wang & Li, 2023; Min et al., 2024), and meta- reinforeedd learning (RI. like DIMES (Qiu et al.,
2 Following Ahn et al. (2020), we regard the solving of a COP as the determination process of decision variables, see Def. 1.1.
2

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Until V M. Mr =1
Mj =
H fea(
x, X.M
G, G,,, md)
= =
Edge-Saeecnn Node-Selectin
Prisstt Order
Determine
until conffict or Eng M
Prirrty Order
Determine
untäl couffict or Mag M
Current State
Neural Model
Probability Heatmap
New State
Solution
Undetermination Optimization Consistency
Adaptive Expansion (Determine) Undetermination
Complete Determination
Figure 1. General pipeline of COExpander under AE x: decision variables; M: mask; y: partial solution; G: graph data; O: model parameters; H: probability heatmap: D: determination operator. A comparative illustration of the pipelined paradigms is provided in Appendix B. In this paper, node-selection problems include MCI, MCut, MIS and MVC; edge-selection problems include TSP and ATSP.
2022), etc. Lately promising are the graph diffusion-
argmin c(x, G), where Ω denotes the feasible set of x that xEQ
generative approaches (DIFUSCO (Sun & Yang, 2023), DIFFUCO (Sanokowski et al., 2024), T2T (Li et al., 2023; 2024), etc.) to learn the instance-level solution distribution.
satisfy the constrains and c(+s)) is the objective cost function of corresponding problems. The formal definitions of the six COPs are presented in Appendix C.
LC Solvers. Most commonly, the policy of the next- step prediction is learned by RL (AM (Kool et al., 2018), POMO (Kwon et al., 2020), MatNet (Kwon et al., 2021), SYM-NCO (Kim et al., 2022), RL4CO (Berto et al., 2024),
Global Predictor for COExpander. Joshi et al. (2019) pio- neered with success to adapt Graph Convolutional Network (GCN), the fundamental model for graph data processing, to solving COPs like TSP. Later, Sun & Yang (2023) and Sanokowski et al. (2024) revealed the prospect of gener- ative CO, proposing to integrate the diffusion principles with graph representations and GCN, which entails a serial noising process that converts the initial solution into a noisy vector and learnable denoising process in reverse. Further, T2T (Li et al., 2024) devises the scheme of training consistency for vanilla diffusion to ensure that all noised trajectories conditioned on the same graph converge to the same initial solution, which largely reduces the denoising steps needed and puts forward the edge of NCO perfor- mance to great extent. Along this chain, we intuitively aim to improve upon Fast-T2T, thus adapting the consistency model as the global predictor of COExpander in favor of its superior performance and efficiency.
etc.) with manually imposed masks to hard-guarantee the feasibility. Lately, BQ-NCO (Drakulic et al., 2023) and GOAL (Drakulic et al., 2024) managed to incorporate su- pervision for sequential decisions to improve the scalability.
We also notice few works that appear to contain similar determining manners to our AE paradigm (Ahn et al., 2020; Zhou et al., 2025), and defer the detailed discussion, com- parison, and empirical studies on them to Appendix B.4. Besides the aforementioned methods to which COExpander the most comparable, we also discuss in Appendix A 1) traditional solvers from operations research, 2) machine learning-enhance heuristies, 3) solution optimization meth- ods, and 4) neural divide-and-congee frameworks, to pro- vide comprehensive review of existent methods for CO.
3. Preliminaries
4. Methodology
Problem Definition. The COPs studied in this paper can be
4.1. Model Learning: Partial Solution Prompted Generation with Consistent Diffusion
consistently characterized by the graph structure, i.e., G
(V,E), where V = (1,.... N) denotes the node set and E
4. DIFFUSION NOISING PROCESS
the edge set. Following previous works (Sun& & Yang, 2023; Li et al., 2023), we define x = 1) M as the corresponding decision variables of a given COP. For MCI, MIS, and MVC,
Following the definitions in Sec. 3, the distribution of the solution space can be characterized by an --dimensioonll Bernoulli distribution p(x) E [0, 1] MX2 The objective of applying generative modeling to mroblem-solving is to leam the distribution of high-quality solutions conditioned given G, mathematically po (x())). For initial solution
M = NV and x, indicates whether the node is selected. For MCut, M N and x; indicates which subset the node i belongs to. For TSP and ATSP, M = 222 and x indicates whether the edge (f. j) is selected. Mathematically, the optimization objective is to find optimal solution x"
Xo, we adhere to the previous graph-based diffusion and
3

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
consistency models (Austin al., 2021; Sun & Yang, 2023; Li et al., 2024) define the noise process, i.e.,
with hyper-parametter p controlling Pr(M; = 1). This scheme enables the model learn make predictions in aware of current solving progress (featured by the partial solution). To guarantee a fundamental performance while promoting data diversity of the model, P is also generated conforming to a probability function of
3 1 B
B1
((x[|x0)= = p0x)) Q2: Q:
(1)
3
where Q - Q: Q2 ... Qe is the cumulative transition prob-
ability matrix with Sg [0. 1] to ensure doubly stochasticity.
P(p) a. - 00 (1-a)
(5)
4.1.2. OPTIMIZATION CONSISTENCY
where 5()) denotes the Dirac delta function and U-) uni- form distribution over the interval [0, 1]. In this paper, we set a as 0.9, and the relevant ablation study is presented in Appendix G.I. Subsequently, the sampled . is updated according to the constraints of the specific COP type. For in- stance, in the context of MIS, if node j that belongs to the maximum independent set (i.e., xj 1) is in prompted state (where M, = 1), then all its neighboring nodes will also be placed in a prompted state.
Given a problem instance G and the optimal solution x", the noising process for discrete diffusion applied to x" is formulated as a trajectory Xo.7 = X0, X1, X2, XX,, where Xo = x" and each x; is sampled from the distri- bution ((x) While vanilla Diffusion demands multi- ple inference steps model pa (x |xx; G) which is time- consuming in practice, to achieve efficient one-step model generation, Consistency Models (Song et al., 2023) have put forward the concept of self-consistency that maps any point at any time step to the trajectory's ' starting point, and Fast- T2T (I.i et al., 2024) has further defined the optimization consistency for COPs that all points along any trajectory map to their optimal solution conditioned on instance G.
4.2. Problem Solving: Adaptive Expansion via Multi-Step Determination
1.2.1. THE MAIN PROCESS OF PROBLEM-SOLVIN
The consistency function is denoted as fo(X,, I, G) with learnable parameters 0. According to the definition of self- consistency, for two noised points Xt, and Xr, on the same trajectory, the original learning objective of the model is to minimize the distance .) between their mapping points:
In general, with a well-trained model fo(-s---). COEX- pander generate solutions x for given instance G through multiple determination steps. In each determination process, we first sample Xy from the uniform distribution and update it with the current partial solution x and its mask M, then we follow -2T to use the model to obtain the probabil- ity heatmap H. via multi-step inferences. After that, H is utilized as guide to expand the number of determined de- cision variables in solution set and correspondingly update x and M, as formulated in Algorithm 1.
[(0) =B[d (fo(x) =[(( t1, G), fo(x t2, ].
(2)
To better utilize the supervising information of x" during training-stagee stage, the distance between the mapping points fe(x,, t, G) and x" can be specified as d (fo(x,, f, x"). Further in this work, the triangle inequality is leveraged to bound and reformulate the training objective as
Algorithm Multi-step solution expanding.
Input: COExpander model fe(-,...-), problem instance graph G, decision variable x with its mask M, determination operator D, sequence of time points тi > T2
((0) S E dffo((x, 11, G), x) ) + difo t2, G), x² x²)] (3)
TN,-1, sequence of determination numbers no < m2
This way, the only concentration as clear as an optimiza- tion over the neural estimation fo. via supervised learning with d(., -) Binary- Cross_EEtrropy(:
< N.N.,
Initialize determination step: d + M
while 0 E M do
Sample x from uniform distribution U4
Update with partial solution: yr + Y(x,, x, M))
4.1.3. THE PROMPT OF PARTIAL SOLUTION
Model Inference: po (Xo G) + folyr, T, G. for 1 to N,- - do
Beyond previous graph-based diffusion and consistency models that directly feed (x,; I, G) to the neural network, we introduce an additional prompting component to the model input, i.e., a masked array of (yr, t, G.M. Here,
Sample xo from distribution ps ps (xo C)
X-. p(xx) NTo + Yxx,,(,,... XM
Gx + fo(y Tw. M)
end for
Predict probability heatmap of x: H ~ po (xo X. <- D(H, G,x,M d ddd+1 end while Output: Solution x
(xx) M: =0 (y:); = XX,,,",, = (x'); M; 1' (4)
where M E M3 has the same shape of the solution x and is sampled from -imieensinnal Bernoulli distribution
4

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
4.2.2. DETERMINATION OPERATIONS FOR COPS
Model Input. Similar the training stage, a masked array
(yt, 1, M, G) is obtained as described in Sec. 4.1.3 and fed to the model. Note the ground truth x² in Eq. 4 should be replaced by the current (partial) solution x at solving stage.
Overview. A determination operator D generally consists of two parts. 1) An order prioritizing the decision variables X; x based on H. and 2) A rule to assign values to the de- cision variables and update the mask accordingly. Note that to avoid extra sensitivity to ad-hoc designs, the operators are implemented upon the simplest greedy hcuristics.
Embedding Layers. The input items are first projected to h-dimensional embeddings before convolution.
(hey he: h,) embed M.,.E,
(6)
During problem solving, given the predicted probabil- ity heatmap H R graph instance G. current (par- tial) solution E {0, with the corresponding mask ME {0, 1jM, and the maximum number of determination rounds nd, D functions iteratively in the following generic manner. It traverses x in the order of priority, in the case where M₁ = (implying an undetermined x;), assign X; = X E {0, 1 and update its mask via certain rules, the number of determined decision variables (i.e., Σm M,) reaches Vid. or if the next assignment of x; would violate the constraints of the problem, then terminate this round of determination and return the updated and M. Empirically, we define the problem-specife operators as follows.
where h,, he and h, are the embeddings for the node, edge and time step, respectively. detail, for all 6 COPs, h, = (t).. For node-selection problems. h, S(y,). h. S(E). For TSP, h, S(V). h, S(y)). For ATSP, h. is not used, he = S(y)). Here, S(.) W ((S where S*(.) denotes sinusoidal embedding layer and W denotes learnable linear layer.
L S'()) = cat sin
L sin T
cDs
COS
(7)
T
T
T
where d is the embedding dimension, T is a large number (e.g., 10000), and c-t(.) denotes concatenation.
node i with descending order of Hi. Rule: expand the clique set with node i and assign x, = 1, M, = 1. Further, for vj E V, (1, & E, update x; = M, = 1.
MCL. Order:
Convolution Layers. Developed upon Joshi et al. (2019),
this process can be expressed a compact formulation:
(h : h,th)=+++++))))t) = Conv' h() + h; (a. 1 - a), (8)
MCut. Order: node with descending order of HH- 2 Rule: expand either partition set with node i, i.e., assign x; HH 1 J. MM = 1. Note that MCut has no constraints that incur chain reactions for extra variable assignments.
Specially, for ATSP, we only perform convolution on the edges, using the original edge features & to update:
(b = Conv' (h,, + h, (a,1-a) -a)- a),
(9)
MIS. Order: node i with descending order of H4. Rule: expand the independent set with node i, i.e., x; = 1, M, = 1. Further, for Vj& E V. (i.5) E ε, update x, = M, = 1.
where a is the indicator of the COP's type (1 for node- selections and 0 for edge-selections). h UReL is the time-step feature and Conv(..-) denotes the cross- layer convolution operation, i.e., aggregating messages from neighboring nodes/edges and Re) activations.
MVC. Order: node with ascending order of H.. Rule: select node that should not belong the vertex cover set, and assign X; 0, M, 1. Further, for Vj V, (i, E, update X; L, =1 1.
Output Layers. To generate heatmaps for both node- and edge-selection tasks, after a group normalization Norm 2-D convolution is employed to transform the I-th (final) graph convolutional outputs into binary classification logits (corresponding to the Bernoulli distribution), followed by a
TSP and ATSP. Order: edge (i, with descending order of Hiy- Rule: Select edge (i, to prolong the tour and assign Xij = 1, MMj = 1. Further, if node has been entered and left, all its neighbors shall also be assigned M 1, = O.
Softmax function to form predicted probabilities.
4.3. Model Architecture: A Task -ankstiiostic Graph Convolutional Network
Hnode = Sottmax(Cau2((Nooo((1)
(10)
Hedge = Softmax((onvv((Nomm)))
(1I)
Sec. 4.1 and Sec. 4.2 have so far depicted a high-level the- oretical pipeline of COExpander. Next, we introduce the specific graph convolutional network (GCN) to embody the 0 that previously parameterized the framework. Provided the generality of the six different COPs mentioned earlier, the model is designed with the best cross-problem compati- bility so that different COPs can be handled with a single unified model, mainly encompassing tailored embedding layers, graph convolutional layers, and output layers.
5. Experiments
5.1. Datasets and Metries
Synthetic Data. For node-selection problems, we have generated datasets of three types, RB (Xu et al., 2005), ER (Erd6s & Rényi, 1960), and BA (Barabási & Albert, 1999). Following DiffUCO (Sanokowski et al., 2024), DI- FUSCO (Sun & Yang, 2023), we generate RB- RB-SMALL. and
5

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Table Results on MIS. GP: global prediction; I.C. local construction; AE: adaptive expansion, hereinafter.
RB- RB-SMALL
RB-LARGE
ER-700-800
SATLIB
METHOD
TYPE
OBs.
DROP,
TIMEI
OB:.
DROP
TIMEI
Ous.
DROP]
TIMEL
Ou1.1
DROP]
TIME]
KaMIS
Heuristies
20,09"
0.00%
45.81s
43.00"
0.00%%
56.976
44.97
0.,00%
60.75%
425.95
0.00%
24.374
Gurobi
OR
20.09
0.00%
0.54c
42.19
1.83%
33.84s
38.78
13.75%
60.49%
425.92
0.01%
3.95:
DIFUSCO (S-11-500)+
GP
38.64
14.08%
2.80s
424.74
0.29%
2.74s
GP
19.50
2.89%
0.41s
40.69
9.51%
1.03%
424.44
0.30%
1.70s
DIfTUCO; CE F=1)
GP
19.20
4.37%
38.49
10.43%
4.71s
COEspander (S=1_,;200000)))
AE
19.66
2.09%
0.11s
41.23
4.06%
0.62s
42.38
5.75%
0.476
425.05
0,22%
0.236
DITUSCO|S=111-55
GF
40.97
8.89%
5.445
425.11
0.20%
2.96s
Fas-T2T ($=1,,,551==5)+
GP
19.74
1.70%
0.86s
41.74
7.17%
1.96s
425.00
0.25%
2.67s
DiaUCO: CE [S=4, F
GP
19.38
3.46%
1.50%
39.55
7.94%
25.48s
COExpander ($=1D,
AE
19.71
1.88%
0.12s
41.44
3.58%
1.30s
42.56
5.34%
0.70%
424.78
0.28%
0.27s
COExpunder (551
AE
19.79
1.48%
0.65%
40.69
5.31%
5.48s
42.13
6.32%
4.30s
425.28
0.16%
1.06s
RB-LARGE for MCI, MIS, MVC, ER-700-800 for MIS, and BA-SMALL and BA-LARGE for MCut. For TSP, we follow DIFUSCO to conduct experiments on TSP-50, TSP-100, TSP-500, TSP-IK, and for ATSP, we conduct experiments on ATSP-50 and ATSP-100, 100-100,AAAA 400 and A7SP-500.
2022), Meta-EGN (Wang & Li, 2023), BQ-NCO (Drakulic et 2023), DIFUSCO (Sun & Yang. 2023), RL4CO (Berto et al., 2024), DiffUCO (Sanokowski et al., 2024), Fast- T2T (Li et al., 2024), GOAL (Drakulic et al., 2024).
Training Settings. During the training phase, we set the number of convolution layers to 12, the learning rate to 0.0002, and the number of training epochs to 50. During the fine-tuning phase, we set the learning rate to 0.00005 and the number of training epochs to 10. Detailed parameters are provided in Appendix F.
Real- World Data. Following Meta-EGN (Wang & Li, 2023), we conduct experiments for MCI, MVC on two real datasets Twitter (Jure, 2014) and COLLAB (Yanardag & Vishwanathan, 2015). For MIS and TSP, we follow DI- FUSCO (Sun & Yang, 2023) to use SATLIB and TSPLIB.
Ultra-Large Data. To further study the generalization of the model, we generate the ultra-large scale datasets. RB-GIANT for MCI, MIS, MVC; ER- ERR-1400-160 for MIS; BA-GIANT for MCut and TSP-IOK. Detailed information regarding the datasets are introduced in Appendix E.
Basic Solving Settings. 1) Inference Step Ig: the number of time-steps the model denoises in the inference phase. 2) Sampling Number S: the number of heatmaps sampled from po (zo|ss) with different random seeds (Sun & Yang, 2023).
Special Solving Settings. 1) Determination Step D,; ap- plied by our COExpander, the maximum number of deter- mination; 2) Gradient-search Step Gg: applied by Fast-T2T the number of gradient search steps. 3) Evaluation Factor F: applied by DiffUCO, the times the number of diffusion steps is increased compared to that used during training.
Metrics. 1) Objective. The average objective of the so- lutions w.r.t. the corresponding instances. For MCI, MIS, MVC, the objective is the vertices number of the selected subset. For MCut, the objective is the sum of weights of edges between the two partitioned subsets. For TSP and ATSP, it the total distance of the solved tour. 2) Drop. The relative performance drop w.r.t. the objective compared to the solutions obtained by the baseline exact solver or heuris- tic solver. Mathematically, drop- c(x=G) c(
Note on the Implementation. First, all the aforementioned traditional solvers have been re-implemented and, in the process, we find several insights into their solving perfor- mance worthy of further discussion (see Appendix D). Con- sequently, this paper refrains from citing several obsolete data from previous research. Second, for neural solvers, we employ pre-trained checkpoints to replicate their perfor- mance whenever available (in the table: f). Otherwise, we retrain the models from scratch (in the table: #). Gener- ally, we present the re-evaluated results of all the compared methods obtained on our standardized datasets and a uni- fied hardware configuration, thus ensuring an impartial and consistent comparison.
:G) 100%.
3) Time. The average computational time per instance. Un- less otherwise specified, all experiments were conducted with batch size set to 1 or in single-thread mode.
5.2. Evaluated Methods and Model Settings
Baseline Solvers. We take Gurobi (Gurobi Optimization, 2023) for MCI, MCut, MIS, MVC; KaMIS (Lamm et al., 2016) for MIS; I.KH (Helsgaun, 2017). GA-EAX (Nagata & Kobayashi, 2013) and Concorde (Applegate et al., 2006) for TSP, as baseline solvers to obtain reference solutions for computing the optimality drops of the other solvers.
5.3. Problem-Specific Improving Techniques
By convention, typical per-instance searching techniques are used to further enhance the quality of solutions.
Neural Solvers. We compared the following recent neural methods. GCN (Joshi et al., 2019), MatNet (Kwon al., 2021), GNNGLS (Hudson et al., 2021), DIMES (Qiu et al.,
Beam Search. For MIS and MCL, when D, set as the
6

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Table 2. Results on MCI, MVC and MCut. BS: beam search. FT: finetuned model.
MAXIMUM CLIQUE
TYPE
RB-SMALL
RB-LARGE
MIS
OB1.1
DROP,
TIMEL
OBI.
DROFJ
TIMEL
Drop (2
MEI
MVC
Gurobi
OR
19.08
0.00%%
0.90s
40.18"
0.00%
276.66s
Meta-RGN
GP
17.51
8.30%
0.27s
33.79
15.49%
0.54s
DINUCO; CE (S=1, F=1)
GP
15.14
18.25%
0,56s
COExpander (2=1
AE
18.77
189%
0.05s
36.75
8.82%
0.15s
COExpunder (S-1, BS
GP
18.66
2.51%
0.024
38.75
3,00%
0.10s
GF
16.21
122.3%
176s
Inference Steps (Is)
COEspunder -51-2)
AE
19.00
0.50%
0.65%
39,06
2.991
6.36s
10
MBS
COEspander -1-11, BS
GP
18.98
0.68%
0.06s
39.88
0.90%
0.37%
Drop (%)
RB-SMALL
RB-LARGE
MINIMUM VERTEX COVER
TYPE
MCM
OB1.
DROP.
TIMEL
OBI.L
DROPj
TIMEL
Gurobi
OR
305,76'
0.00%
3,34s
968.23
0.00%
290.23s
Metn-RGN
GP
208.97
1.56%
0.30s
1010.09
4.40%
1.03s
COExpander ((=1_1))
AB
206.75
0.48%
0.216
969.92
0.18%
0.52s
Determination Steps
COExpander (S=1D))2044=)
AE
206.51
0.37%
0.3%
969.81
0.16%
0.63s
BA-SMALL
BA-LARGE
MIS
MAXIMUM CUT
TYP8
Drop (%a)
MET
OBI:7
DROP,
TIMEL
OBs.7
DRUP
TIMEI
MYC
Gurobi
OR 727.84
0.00%
60.61s
2936.89
0.00%
300.21s
DiaUCO: CE (S=1, 3
GP
726.90
0.15%
0.20s
2986.93
-1.69%
0.65:
COExpunder (S-1,,)-001--))
AE
727.53
0.06%
0,18s
2978.20
-1.39%
0.20s
COExpinde-FFT -1
AR
726.54
0.20%
0.174
2980.51
-1,47%
0.20s
DinTUO: (
GF
727.53
0.06%
0.61s
2969.46
-1.77%
2.70:
Multiple Sampling (S)
GP
728.32
-0.08%
0.20s
2960.66
-0.80%
0.36s
Figure Ablation study.
GP
728.27
-0.04%
0.20s
2987.14
-1.69%
0.36s
determination process can be enhanced by a beam search strategy where & (default: 16) candidate sets are maintained simultancously during the search. When node is being determined, each candidate set is checked, and once the constraints met, the node added to the corresponding set.
5.4. Main Results
Main experimental results are presented in Table (MIS),
Table 2 (MCI, MVC and MCut), and Table 3 (TSP & ATSP). The complete results with more model settings evaluated and standard deviations of the performance drop reported are provided in Table 18 through Table 23 in Appendix G.
Objective Guided Wine-Tuuine Inspired by Sanokowski al. (2023; 2024), we adopt the energy function of MCut an unsupervised loss function to fine-tune the MCut model, where C' is constant (1000) to limit the loss function value. Note that we used the same training set as initial training.
Node-selection Problems. Compared previous SOTA, COFxpander reduces the drop by 37.9%. %, 94.4%, 92.4% and 1.4% average, with speedup of 8.4x, 1.1x, 2.2x and 5.9x, on MIS, MCI, MVC, and MCut, respectively.
L= Σ
1 (2x, - 1) (2x, -
(12)
Edge-selection Problems. Compared to previous SOTA, our COExpander achieves an average performance improve- ment of 27.8% 75.4% on TSP and ATSP respectively.
(1.))E
Two-Opt. Two-Opt is widely employed to improve the so- lutions for routing problems (Deudon et al., 2018; da Costa et al., 2020; Li et al., 2023). For given a distance matrix D and an initial tour X1, Xp. Xp+1,....... Xy-1, Xg. Xg+1, two nodes Xp and X, are selected to perform the Two- Opt operation, i.e., connecting the two nodes and swap- ping the subsequence between them and resulting a The reward r = Dpst1 + Dg.gt - Dpg - Dpt1.t+ denotes the improvement after the swap. For ATSP, given an initial tour Xi...., Xp, Xp+1. X Xy+1, Two- Opt performing on nodes x, and x, results in new path X1, Xp. Xg. Xp+1 Xpp1..xx.....11.................
5.5. Ablation Study
On Inference Steps. As shown in Fig. 2 (top), with Ia increasing (1, 5, 10, 20), the optimality drop generally varies in a downward trend, decreasing from an average of about 7.0% to 4.1 %. This naturally aligns with what has been observed in previous diffusion-based models.
new path X1, Xp. Xq. Xq-1 Xp+1, Xpt
On Determination Steps. As D, increases from to 20, the drop decreases significantly from an average of about 7.0% to 2.2% (Fig. 2 (middle)). This also reasonably conforms to the motivation of AE that more determination rounds enables a more precise utilization of each prediction.
with reward r Dp.tt1 + +D + D D1 - p.a- - -D Dg.pt1 D D--1--1- In each iteration, the new tour that yields the maximum reward is fixed for the next round. The iteration terminates when either no further improvements can be made or the maximum number of iterations (default: 5000) reached.
On Multiple Sampling. As shown in Fig. 2 (bottom), the drop decreased intuitively as S grows, reaching 4.8% as S set to 8 to allow richer diversity of solution sampling.
7

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Table 3. Results on TSP and ATSP across problem sizes.
TSP-50
TSP-100
TSP-500
TSP-1K
Memon
TYP6
OBt..
DROP,
TIMEL
OBI.
DBOR]
TIMEL
OBI.
DROrt
TIMEL
OB1.4
DROPL
TIMEL
Cancorde
Exact
5.69'
0.00%
0.06s
7.76'
0.00%
0.24s
16.55'
0.00%
18.67%
23.12"
0.00%
84.41s
(500)
Heuristiss
5.69
0.00%
0.06s
7.76
0.00%
0.18:
16.55
0.00%
1.85s
23.12
0.00%
4.61s
GA-EAX
Houristies
5.69
0.00%
0.10s
7.76
0.002
1.86s
16.55
0.00%
1.86s
23.12
0.0078
17.54
GCN 2
GP
5.69
0.07%
0,01s
7.78
0.24%
0
16.77
1.35%
0.96s
23.53
1.77%
0.236
GNNGLS + 20PT**
GP
5.71
0.33%
0.02s
7.86
1.30%
0.13s
DIMES 20PT
GP
5.89
3,58%
0.00s
8.11
4,54%
0.01s
17.66
6.71%
0.318
24.91
7.74%
0.66s
(SPU1)00 20PT:
0.10%
2.5%%
7.78
0.22%%
2,0%
16.81
1.59%
2.78s
23.54
1.83%
3,4%s
Fis-TZT (5
GP
5.69
0.02%
0.25%
7.76
0.07%
0.25%
16.70
0.11%
0.33g
23.39
1.16%
0.95s
RLACO (Sy
LC
5.73
0.68%
0.17s
7.89
1.75%
0.32s
BQ-NCO + 20PT
LC
5.80
1.89%
0.21s
7.89
1,77%
0.39
16.84
1.77%
2.45
23.65
2.29%
5.72s
COExpande (S=1.,,=31,++++
AE
5.69
0.02%
0.08s
7.76
0.04%
0.09s
16.63
0.49%
0.24s
23.34
0.95%
0.70s
(S=1:==0== 20PT:
GP
5.69
0.02%
2.69s
7.76
0.07%
2.69s
16,70
0.92%
3.03s
23.12
1.31%
7.8%%
Fus-T2T (5=4,,,55+
GP
5.69
0.01%
0.26s
7.76
0.025
0.27s
16.63
0.5016
0.47s
23.29
0.74%
1.93s
BQ-NCO + 16am-16420PPT
LC
5.79
1.72%
0.21s
7.87
1,18%
0.90s
16.77
1.33%
4.02s
23.51
1.71%
10.34s
COExpande (5110, 2OPT
AE
3.69
0.01%
0.0%
7.76
0.01%
0.186
16.59
0.25%
0.66s
23.27
0.64%
2.435
ATSP-50
ATSP-100
ATSP-200
ATSP-550
METHOD
TYPE
OR).
DROP.
TIME)
ORI.
DROR]
TIMRI
ORI.
DROP]
TIMEL
OR].4
DROPL
TIME]
IKH (1000)
Heuristies
1.55
0.00%
0.10s
1.57
0.009
0.24s
1.56
0.00%
0.72s
1.57
0.00%
4.38%
MatNer
LCC.
1.38
1.32%
0.84k
1.62
3,209
0.066
3.83
145.08%
0.11s
GOAL #
LC
0.31s
1.64
4.61%
0.64s
1.62
3.35%
1.46
1.72
9.02%
3.26s
AP
1.57
1.13%
0.00%
1.60
2.26%
0.10s
1.60
2.56%
0.52s
1.61
2.41%
1.77%
12""
1.36
00300
0.044
1.30
T.56%
0.97%
3373
T38 40FA
0.16m
GOAL, + 16am-16
LC
1.63
4.74%
0.35%
1.62
3,53%
0.91s
1.61
2.86%
4.69%
1.30
8.13%
32.244
COExpande: 13,-,,)) 2OPT
AE
1.56
0.17%
0.10s
1.58
0.98%
0.52s
1.59
1.50%
1.10s
1.60
1.57%
6.60s
Table 4.
Results for generalization experiments on ultra-large scale node-selection problems.
RB-GIANT (MCI)
BA-GIANT (MCut)
RB-GIANT (MIS)
ER-1400- 1600 (MIS)
RB EB--IIAN (MVC)
METHOP
TYPE
OBI.1
TIMEL
OBI.t
TIMEL
OBI.1
TIMe_
OBI.1
TIME,
OBI.
TIME!
Gurobi (60s)
OR
50.98
60.25s
7216.96
61.23s
44.76
56.01s
40.82
62.14s
2400.80
60.01s
Gurbbi (300s)
OR
51.92
302.648
7217.86
300.50x
46.72
302.73s
41.20
304.49s
2398.48
211 211.42s
Gurobi (3600s)
OR
81.52
3606.20s
7217.90
3601.34s
48.56
3426.21s
44.81
3602.52s
2396.78
1813.79s
COExpander
AE
84.12
1.52s
7381.92
1.76s
46.64
14.66s
48.43
4.52s
2400.36
8.20s
Additionally, under the same number of model calls (c.g., with Dy I, fixed), the "partial-to-full" multi-step determi- nations (AE) demonstrate better stability and effectiveness than the "noise-to-full multi-step inferences (GP). Com- plete results are provided in Table 17 (Appendix G).
Cross-Scale Generalization: On Ultra-Large Scale Data. For pode-selection problems, COExpander is trained on RB-LARGE and ER-700-800, and tested on RB-GIAN and ER- 14100400000 Results in Table demonstrate COExpander as the first neural solver to outperform Gurobi(3600s) by 1.9 % with significant speedup of 1134.1x. For TSP, we fine-tune the TSP- model to solve 7SP-10K, reducing the drop from 1.595 % to a new SOTA of 1.450% with a speedup of 1.39x as shown in Table 22.
On Backbone Models. Despite our design choice of the ad- vanced generative model to embody COExpander, we also test vanilla GCN to empower AE. Results in Table 16 show superior performance of COExpander- GCN over GCN, val- idating our stance that any backbone model (readily tai- lored for COP solving) can be adapted to instantiate the AE paradigm to enjoy the model-agnostic performance gain.
A summary of results on all COPs comparing COEx- pander with previous SOTA is listed in single Table 25.
6. Extended Discussions and Experiments
5.6. Generalization Study
6.1. Sampling Methods for the Node-Selection Problems
Dist-Disttibttion Generalization: On Real- Real-World Data. For MCI and MVC, we train COExpander on RB-SMALL and test it on Twitter and COLLAB. As shown in Table 19 and Table 20, COExpander achieves a performance improve- ment of 19.7% on MCI and 98.5% on MVC compared with the previous SOTA, i.e., MeNa-EGN. For TSP, we test our model on 2D Euclidean instances selected from TSPLIB with 51 to 1002 nodes. A competitive drop of only 0.367% is achieved. Per-instance results are provided in Table 24.
In addition to learning-based methods, sampling methods like iSCO (Sun et al., 2023) and RLSA (Feng & Yang, 2025) have shown strong capabilities in solving COPs with simple constraints, such as node-selection problems in this paper. These methods transform problem into energy function and perform sampling guided by gradient information.
Given that these sampling methods do not depend on spe- cific distributions and do not require training, we take the
8

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Table Using the RLSA as a post-pu processoo for COExpander on MIS. 7p: initial temperature; regularization factor, k: parallel numbers; t: iterations; 3: penalty factor of the energy function; on &az: initialization factors; FAIL: no feasible solution generated.
RI RIASA SETTINGS
RI.SA A (using 21)
COEXPANDER RI.S
DATASET
d
k:
t
8
OBI.
DROP!
TIME!
OBJ.
DROP1
TIME.
RB-SMALL
0.01
5
1000
500
1.02
0.16
0.3
20.084
0.028:10.112%
0.534s
20.070
0.0931:0.555%
0.449s
RB-LARGE
0.01
5
1000
1000
1.02
0.09
0.3
41.870
2.569+ 745%
2.166s
42.400)
1,93%%
1.738s
ER 22-700--S 800
0.2
10
1000
1000
1.001
0.12
0.3
44,906
0.180
1.657s
44.984
-0,041 1..399 %
1.352s
SATLIB
0.01
5
1000
1000
1.02
0.67
0.3
FAIL
425.316
0.13%%
1.778s
ER-1400- 160D
0.2
10
1000
1000
1.001
0.07
0.3
50.414
1.019:1133558
3.797s
50,719
0.418::1.489 %
4.416s
RB-GIANT
0.01
5
1000
1000
1.02
0.04
0.3
FAIL
47.880
2.741+-2.001%
9,526s
Table 6. Results on CVRP across problem sizes.
CVRP:50
CVRP-100
CVRP-200
CVRP-500
METRON
OBl.
DROP]
TIMEL
OB).
DRORj
TIMEI
OBI.
DROP
TIMEL
OB1.
DROe]
TIME,
HGS (Vidal al., 2012)
Heuristics
10.37*
0.00%
1.01s
15.56'
0.00%
20.03s
19.63*
0.00%
60.02s
37.15*
0.00%
360.38s
RL,00 (8ym-NCO)) + Classic-LS*+ #
LCC
10.56
1.91%
0.99s
15.93
2.38%
0.176
20.19
2.88%
0.34g
38.70
4.17%
0.884
COExpander Classic-LS
AE
10.77
3.90%
0.04s
16.22
4,25%
0.06s
20.59
4.89%
0.15
39.12
5.34%
0.61s
RLSA as an example and orthogonally apply it post- processing plugin for the vertex selection problem on top of our method. Algorithm 2 shows how we integrate RLSA as a post-processor, where To denotes the initial temperature: represents the regularization term, where the d-th largest gradient value is used to control the overall flipping probabil- ity; indicates the number of parallel runs, which must be greater than d; t represents the total number of iterations; 0g denotes the noise factor. To diversify the initialization and facilitate escaping local optima, we introduce some noise to the initial solution Xg- Besides, we have adjusted the initialization part of original RLSA by incorporating prior knowledge: the initial probability of each node is changed from pa 0.5 to po 0.5aj, where ai = 2 Σi (x.).
method, but there are also cases where no feasible solution could be found. However, when served as a post-processor, since the initial state starts from a feasible solution, the phe- nomenon of not finding a feasible solution can be avoided.
6.2. Applied to Capacitated Vehicle Routing Problem
We have attempted to apply COExpander to CVRP-50, CVRP-100, CVRP-200 and CVRP-500, as shown in Table 6, where Classic-LS is the post-processing method for CVRP that we have designed based on previous works (Prins, 2004; Vidal et al., 2012). Details of the experimental setup and corresponding discussions provided in the Appendix H.
The results demonstrate that COExpander performs less favorably on CVRP. We believe this is due to the limita- tions of the global predictor, i.g. consistency model, of COExpander. To our best knowledge, before our work, con- sistency model (Li et al., 2024) has only been applied to two combinatorial optimization problems: TSP and MIS, As a direction for future work, we elaborate in Appendix H on the potential of extending AE to more complex constrained problems such as CVRP, via integration with Markov De- cision Processes (MDP) and Proximal Policy Optimization (PPO, Schulman et al. (2017)).
Algorithm 2 RLSA as Post- Post-Processor.
Input: Graph C. Energy Funetion H(.), hyperparameter (70. d, k. t. 022), Initial Solution Xo.
Parallel k:
x < Bernoulli(1 a2) Xo + az Bernoullip = 0.5)) for = 1 to t do
---- 7a )-
A + (2x- 12xx1))VH(s)
for 1 = to do
p Sigmoid (AA (22))
c <~ Bernoulli(p)
x, + +x, (1 - c) + xx)x x,)
end for
7. Conclusion and Future Work
if H < [xxx)) then
x" x
We propose the AE paradigm and COExpander model for NCO, combining the advantages of global prediction and local construction methods to achieve adaptive granularity of neural decisions. Our method reaches SOTA performance on 6 COPs compared to 11 neural baselines. Future work includes 1) coupling outer mask updates with inner diffu- sion steps; 2) solving more COPs like the vehicle routing problems; and 3) fine-tuning the iterative determination with RL for a more principled expansion. Details of future work and limitations of our paper discussed in Appendix H.
end if end for Output: Solution
We conduct experiments the MIS using RLSA a solver and as post-processor for COExpander, as shown in Ta- ble 5. It should be noted that, to ensure fairness in the time dimension, we used twice the number of iterations when employing RLSA as a solver. The experimental results demonstrate the strong solving capability of the sampling
9

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Impact Statement
Drakulic, D., Michel, S., Mai, F., Sors, A., and Andreoli, J.-
M. Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization, 2023.
This work aims to improve the field of neural combina- torial optimization with streamlined generative method of stronger performance, higher efficiency and better inter- pretability. To the best of our knowledge, aspect of our research raises ethical issues or harmful insights.
Drakulic, D., Michel, S., and Andreoli, J.-M. Goal: A
generalist combinatorial optimization agent learner, 2024.
Erd6s, P. and Rényi, A. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci, 5:17-61, 1960.
References
Ahn, S., Seo. Y., and Shin, J. Learning what to defer for maximum independent sets. In International Conference on Machine Learning. PMLR, 2020.
Feng, S. and Yang. Y. Regularized langevin dynam- ics for combinatorial optimization. arXiv preprint arXiv:2502.00277, 2025.
Applegate, D., Bixby, R., Chvatal, V., and Cook, W. Con- corde tsp solver, 2006.
Fu, Z.-H., Qiu, K.-B., and Zha, H. Generalize small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI conference on artificial intelli- gence, volume 35, pp. 7474-7482, 2021.
Austin, J., Johnson, D. D., Ho, J., Tarlow, D., and van den Berg, R. Structured denoising diffusion models in discrete state-spaces, Advances in Neural Information Processing Systems, 14:17791-17999 2021.
Guo, W., Zhen, H., Li, X., Luo, W., Yuan, M. Jin, Y., and Yan, J. Machine learning methods solving the boolean satisfiability problem. Machine Intelligence Research, 2023.
Barabási, A.-L. and Albert, R. Emergence of scaling in random networks. science, 286(5439):509-51,, 1999.
Baty, L.. Jungel, K., Klein, P. S., Parmentier, A., and Schif- fer, M. Combinatorial optimizationnenriche machine learning to solve the dynamic vehicle routing problem with time windows. Transportation Science, 2024.
Gurobi Optimization, L. Gurobi optimizer reference manual (2020), 2023.
Helsgaun, K. An extension of the lin lin-kernighan- ----eeiiihhn--hllgamm tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12, 2017.
Berto, F., Hua, C., Park, J., Luttmann, L., Ma, Y., Bu, F., Wang, J., Ye, H., Kim, M., Choi, S., Zepeda, G., Hottung, A., Zhou, J., Bi, J., Hu, Y., Liu, F., Kim, H., Son, J., Kim, H., Angioni, D., Kool, W., Cao, Z., Zhang, Q. Kim, J., Zhang, J., Shin, K., Wu, C., Ahn, S., Song, G., Kwon, C., Tierney, K., Xie, I.., and Park, J. RI4co: an extensive reinforcement learning for combinatorial optimization benchmark, 2024.
Holme, P. and Kim, B. J. Growing scale-free networks with tunable clustering. Physical review E, 65(2):026107, 2002.
Hudson, B., Li, Q.. Malencia, M., and Prorok, A. Graph neural network guided local search for the traveling sales- person problem. arXiv preprint arXiv:2110.0522 2021.
Chen, X. and Tian, Y. Learning to perform local rewrit- ing for combinatorial optimization. Advances in neural information processing systems, 32, 2019.
Joshi, C. K., Laurent, T., and Bresson, X. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv: 10X6.0990000/22. 2019.
da Costa, P. R. d. O., Rhuggenaath, J., Zhang, Y., and Akcay, A. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Pan, S. and Sugiyama, M. (eds.), Proceedings of The 12th Asian Conference on Machine Learning, volume 129 of Pro- ceedings of Machine Learning Research, pp. 465-480. PMLR, 18-20 Nov 2020.
Jure, L. Snap datasets: Stanford large network dataset collection. Retrieved December 2021 from http://snap. stanford. edu/data, 2014.
Kim, M., Park, J., and Kim, J. Learning collaborative policies to solve np-hard routing problems. In Advances in neural information processing systems, 2021.
Deudon, M., Cournut, P., Lacoste, A., Adulyasak, Y., and Rousseau, L.-M. Learning heuristics for the tsp by pol- icy gradient. In Integration of Constraini Programming, Artificial Intelligence, and Operations Research: 15th In- ternational Conference, CPAIOR 2018, Delft, The Nether- lands, June 26-29, 2018, Proceedings 15, pp. 170-181. Springer, 2018
Kim, M., Park, J., and Park, J. Sym-nco: Leveraging symmetricity for neural combinatorial optimization. Ad- vances in Neural Information Processing Systems, 35: 1936-1949, 2022.
10

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Kim, M., Choi, S., Kim, H., Son, J., Park, J., and Bengio, Y. Ant colony sampling with GFlownets for combinatorial optimization. In The 28th International Conference Artificial Intelligence and Statistics, 2025.
Ma, Y., Cao, Z.., and Chee, Y. M. 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.
Kool, W. Van Hoof, H., and Welling, M. Attention, learn to solve routing problems! arXiv preprint arXiv: 1803.08475, 2018
Min, Y. Bai, Y., and Gomes, C. P. Unsupervised learning for solving the travelling salesman problem, 2024.
Nagata, Y. and Kobayashi, S. A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem. INFORMS Journal on Computing, 25(2)344- 363, 2013.
Kool, W., van Hoof, H., Gromicho, J., and Welling, M. Deep policy dynamic programming for vehicle routing problems. In International conference on integration of constraint programming. artificial intelligence, and operations research, pp. 190-213. Springer, 2022.
Pan, W., Xiong, H., Ma, J., Zhao, W., Li, Y., and Yan, J. UniCO: On unified combinatorial optimization via problem reduction to matrix-encoded general TSP. In The Thirteenth International Conference Learning Representations, 2025.
Kwon, Y.-D., Choo, J., Kim, B., Yoon, I., Gwon, Y., and Min, S. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Informa- tion Processing Systems, 33:21 18982198,, 2020.
Paschos, V. T. Applications of combinatorial optimizution. John Wiley & Sons, 2014.
Kwon, Y.-D., Choo, J., Yoon, I., Park, M., Park, D., and Gwon, Y. Matrix encoding networks for neural combi- natorial optimization. Advances in Neural Information Processing Systems, 34:5133-51440 2021.
Prins, C. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & operations research, (1(12)11885222) 2002, 2004.
Lamm, S., Sanders, P., Schulz, C., Strash, D., and Wer- neck, R. F. Finding near-optimal independent sets at scale. In 2016 Proceedings of the eighteenth workshop on algorithm engineering and experiments (ALENEX), pp. 138-150. SIAM, 2016.
Qiu, R., Sun, Z., and Yang. Y. DIMES: A differentiable meta solver for combinatorial optimization problems. In Advances Neural Information Processing Systems 35, 2022.
Sanokowski, S., Berghammer, W., Hochreiter, S., and Lehner, S. Variational annealing graphs for combi- natorial optimization. Advances in Neural Information Processing Systems, 36:63907-63930 2023.
Li, Y., Guo, J., Wang, R., and Yan, J. From distribution learning in training to gradient search in testing for com- binatorial optimization. In -eirtt--eventth Conference on Neural Information Processing Systems, 2023.
Sanokowski, S., Hochreiter, S., and Lehner, S. A diffusion model framework for unsupervised neural combinatorial optimization. In Forty-first International Conference on Machine Learning, 2024.
Li, Y., Guo, J., Wang, R., Zha, H., and Yan, J. Fast 12t: Opti- mization consistency speeds up diffusion- based training- to-testing solving for combinatorial optimization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint 1007:11777.0647 2017.
Li, Y., Ma, J., Pan, W., Wang, R., Geng, H., Yang, N., and Yan, J. Unify ml4tsp: Drawing methodological principles for tsp and beyond from streamlined design space of learning and search. In The Thirteenth International Conference on Learning Representations 2025.
Singh, G. and Rizwanullah, M. Combinatorial optimization of supply chain networks: A retrospective & literature review. Materials today: proceedings, 62:1636-1642, 2022.
Lischka, A., Wu, J., Chehreghani. M. H., and Kulesár, B. A great architecture for adge-based graph problems like tsp, 2024.
Song. Y., Dhariwal, P., Chen, M., and Sutskever, I. Consis- tency models, 2023.
Loshchilov, I. and Hutter, F. Decoupled weight decay reg- ularization. In International Conference on Learning Representations, 2018
Studio, I. I. C. O. V20.1: User's manual for cplex. IBM Corp. pp. 1-20, 2020.
Sui, J., Ding, S., Liu, R. T., Xu, L., and Bu, D. Learning 3-opt heuristics for traveling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learning, 2021.
Luo, F., Lin, X., Wang, Z., Tong, X., Yuan, M., and Zhang, Q. Self-improved learning for scalable neural combinato- rial optimization, 2024.

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Sui, J.. Ding, S., Xia, B., Liu, R., and Bu, D. Neuralgls: learning guide local search with graph convolutional network for the traveling salesman problem. Neural Com- put. Appl., 36(17):9687-977) October 2023. ISSN 0941- 0643. doi: 10. 00.10007600021--22--00000
Ye, H., Wang, J., Liang, H., Cao, Z., Li, Y., and Li, F. Glop: Learning global partition and local construction for solving large-scale routing problems in real-time. In Proceedings of the AAAI Conference on Artificial Intelli- gence, 2024b.
Sun, H., Goshvadi, K., Nova, A., Schuurmans, D., and Dai, H. Revisiting sampling for combinatorial optimization. In International Conference Machine Learning, pp. PMLR, 2023.
Zhang, J., Liu, Li, X., Zhen, H.-I.,, Yuan, M., Li, Y., and Yan, J. A survey for solving mixed integer programming via machine learning. Neurocomputing, 519:205-222 217, 2023.
Sun, 7. and Yang. Y. DIFUSCO: Graph-based diffusion solvers for combinatorial optimization. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Zheng, J., He, K., Zhou, Jin, Y., and Li, C.-M. Combin- ing reinforcement learning with lin- kernighan-helseee algorithm for the traveling salesman problem. Proceed- ings of the AAAI Conference on Artificial Intelligence, 35 (14):12445-12452 May 2021. doi: 10.1609/aami, v35i14. 17476.
Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., and Rei, W. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3):611 1-24,, 2012.
Zheng, Z., Zhou, C., Xialiang, T., Yuan, M., and Wang, 7. Udc: A unified neural divide-and-comquee framework for large-scale combinatorial optimization problems. The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Wang, H. and Li, P. Unsupervised learning for combina- torial optimization needs meta-learning. arXiv preprint arXiv:2301.03116 2023.
Zhou, S., Ding, Y., Zhang, C.,, Cao, Z., and Jin, Y. Dualopt: A dual sovide-and-optimiie algorithm for the large-scale traveling salesman problem. In Proceedings of the AAAI Conference on Artificial Intelligence February 2025.
Wang, Q. and Tang, C. Deep reinforcement learning for transportation network combinatorial optimization: A survey. Knowledge-Basse Based Systems, 233: 233:107526, 2021.
Wang, R., Guo, Z., Pan, W., Ma, J., Zhang, Y., Yang, N.,
Liu, Q., Wei, L., Zhang, H., Liu, C., et al. Pygmtools: python graph matching toolkit. Journal of Machine Learning Research, 25(33):1-7, 2024.
Watts, D. J. and Strogatz, S. H. Collective dynamics of 'smallworlke world''oooooo'kks nature, 39366684):440-444, 1998.
Xin, L., Song, W., Cao, Z., and Zhang, J. Neurolkh: Com- bining deep learning model with aikernighan-helsgaaal heuristic for solving the traveling salesman problem. In Advances in Neural Information Processing Systems, vol- ume 34, 2021.
Xu, K., Boussemart, F., Hemery, F., and Lecoutre, C. A simple model to generate hard satisfiable instances. arXiv preprint cs/0509032, 2005.
Yanardag, P. and Vishwanathan, S. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Ye, H., Wang, J., Cao, Z., Liang, H., and Li, Y. Deepaco: neural-enhancel ant systems for combinatorial optimiza- tion. Advances in Neural Information Processing Systems, 36, 2024a.
12

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
A. Additional Related Work
Prior to the prevalence of end-to-end neural combinatorial optimization as we introduced in Sec. and See. 2, traditional solvers from operations research and some -huual-e attempts were widely applied, demonstrating the progress of the manner and level of neural involvement for solving COPs. Additionally, series of solution optimizing approaches as well as divide-and-com -nde-uuue frameworks have also been devised as post- prior-inference techniques at higher and orthogonal level for solving COPs. We hereby include them as related work to form a comprehensive review.
Solvers from Operations Research. These methods depend on linear (integer) programming algorithms to discover exact or near-optimal solutions to COPs, commonly resorting to branch and bound, cutting planes, meta-heuristics, etc. Representatively, CPLEX (Studio, 2020), Gurobi (Gurobi Optimization, 2023), etc., are globally leading large-scale optimizers. For certain tasks, Concorde (Applegate al., 2006), LKH (Helsgaun, 2017), GA-EAX (Nagata & Kobayashi, 2013) for TSP, and KaMIS (Lamm et al., 2016) for MIS, etc., are designed with reputed efficiency and quality. These traditional solvers have exhibited strong performance their respective problems, yet at the cost of a great deal of expert knowledge and solving time, especially when the instances scale up large.
Machine Learning Enhanced Heuristies. These works have focused on devising or improving heuristics incorporating machine learning components. They either adjust partial parameters of traditional solvers or design heuristics under neural guidance. VSRLKH (Zheng et al., 2021) and KeuroLKH (Xin al., 2021) combine L.K with reinforcement learning (RL) and supervised learning (SL) respectively. GNNGLS (Hudson et al., 2021) and NeuralGLS (Sui al., 2023) hybridize GNNs and Guided Local Search (GLS) for TSP solving. Similar works (da Costa et al., 2020; Sui al., 2021; Ma et al., 2023) are there to solve COPs by neurally defining 2-, 3-, and k-opt hcuristies in data-driven manner. Kool et al. (2022); Ye et al. (2024a); Kim et al. (2025) also explore to combine ML techniques with heuristics upon dynamic programming, ant colony, and probabilistic search algorithms. Note that a common drawback is their heavy dependence on established solvers and lack of universality, as they require tailoring specialized neural tricks for particular base solvers to achieve satisfactory synergy.
Solution Optimization Approaches. These works primarily focus on how to optimize starting from an initial solution, which is typically obtained using simple heuristic, such greedy algorithm. NeuRewriter (Chen & Tian, 2019) uses neural networks to learn how to select heuristics (e.g. k-opt) and iteratively rewrite local parts of the current solution to optimize it. NeuOpt (Ma et al., 2023) learns to perform flexible k-opt exchanges based on a tailored action factorization method and a customized recurrent dual-stream decoder, and proposed the Guided Infeasible Region Exploration (GIRE) scheme, applying the idea of taboo search to combinatorial optimization. Att-GCRN (Fu et al., 2021) use the heatmap obtained from the global predictor to guide the Monte Carlo search (MCTS), thereby optimizing the initial TSP tour.
Sriide-and-Conquer (D&C) Frameworks. terms of solving large scaled CO problems, resorting to -ndide-and-conquer paradigm is popular and proved feasible and performant, as shown in Fig. 3. Fu et al. (2021) trains a lightweight model to predict sub-heatmaps which are later combined for large TSP instances. Luo et al. (2024) proposes self-improved learning method for better scalability. Most recently, GLOP (Ye et al.. 2024b) and UDC (Zheng et al., 2024) learn to partition large routing problems into sub-TSPs or sub-VRPs and conquer them via local revisers. Kim et al. (2021) introduces a collaborative policy framework that explicitly decouples exploration (via diversified solution generation) and exploitation (via parallelized local revision). In this paper, we primarily focus on the solution construction process, yet D&C methods can always be further employed on top of these paradigms.
Sub -TP Solver Conguer
Unselected
Selected
Greedy Insertion
Neural Model
Divide
Compuse
Instance G
Initial Tour
Solution
Neural Model
Figure The solving pipeline of the D&C frameworks (GLOP (Ye et al., 2024b)). They are mainly applied for edge-selection problems.
13

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
B. Discussion on the Paradigms for Neural Combinatorial Optimization
B.1. Comparison of Solving Pipelines
Local Construction (LC). As shown in Fig. (a), LC use the well-trained neural networks to predict the best next-step action (e.g., selecting the next node/edge) given the current state. This process executed continuously until a complete solution is constructed.
Global Prediction (GP), As shown in Fig. 4 (b), given graph data G, GP use the well-trained neural networks (i.e. fo(-)) to globally predict the probability H that each node edge is selected, and then decode H to obtain solutions
Adaptive Expansion (AE). As shown Fig. 4 (c), given graph data G, AE iteratively perform adaptive expansion processes. For each process, AE use the global predictor (i.e. :)(: to globally predict the probability H that each node or edge
selected, and then utilizes the most convincing components of the to determine (i.e. :(:"""::s))) the corresponding decision variables x. We further discuss existing methods that can be categorized in generalized AE family in Sec. B.4.
Until vi E M,M,
Selected
fu(G, M.
X,M Action(x.5.M)
Current State
Neural Model
Score
New State
Solution
(a) Local Construction.
G (W,8)
Pa(Xa]G) e- fo(G)
H-Pa(Xo
Decode(3()
Unselected
Kode-Seledion
Selected
Instance
Neural Model
Heatmap
Solution
Edgeo Selectio
Unselected
Selected
Instance
Neural Model
Heatmap
Solution
(b) Global Prediction.
decision variables are determined
Undetrmined
Determined and not selectd
fuly,
DIX
Node Seteeant
Current
Neural Model
Heatmap
Solution
(c) Adaptive Expansion (ours).
Figure 4. The solving pipeline of the three paradigms. G: graph data; æ: decision variables; M and M: mask: yr partial solution: 0:
model parameters; H: probability heatmap; D: determination operator.
14

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
B.2. Limitations of Existing LC Solvers
Modeling Limitation. The past LC solvers (Kwon et al., 2021; Drakulic et al., 2023; Berto et al., 2024; Drakulic et al.. 2024) generally involves primarily trained to learn how predict the next node to select/visit the next node based on the current state rather than determining whether the next nodes belong to the solution set. Therefore, they are difficult to directly apply to the four node-selection problems discussed in this paper.
Subpar Performance and Inefficiency. We take TSP as an example to compare the differences between Fast-T2T (GP solver) and SymNCO (LC solver) in terms of performance and time. Both adopt a greedy decoding method, and the results are presented in Table 7. Despite the consistent total amount of reasoning information (For TSP-K, GP reasons K2 edges in one inference, and LC also reasons a total of K2 edges in K inferences), the actual reasoning time of LCis obviously higher than that of GP due to its sequential decoding method. Additionally, when the scale increases, the solving performance of Sym-NCO drops sharply, and it is even worse than the greedy insertion algorithm when it comes to TSP-500.
Table 7. Comparison of performance and time of LC and GP paradigms on TSP.
TSP-50
TSP- 100
TSP-500
METHOD
TYPE
OBJ.
DROPL
TIME
OD1.
DROPL
TIMEL
OBJ.J
DROPL
TIME
Concorde (Applegate et al., 2006)
Exact Heuristic
5.688'
0.000%
0.074s
7.756'
0.000%
0.404s
16.546'
0.000%
18.672s
Insertion (Ye et al., 2024b)
6.126
7.708%
0.002s
8,508
9.699%
0.003s
18.608
12.461%
0.006s
Fast (S=1, 1,=1) (1. et al., 2024)
GP
5.706
0.297%
0.058s
7,858
1.269%
0.0684
17.828
7.500%
0.164s
Sym-NCO (RL4CO) (Berto et al, 2024)
5.738
0.877%
0.169s
7,927
2.209%
0.304s
21.105
27.561 S
0.460x
B.3. Limitations of Existing GP Solvers
Modeling Limitation. We find that the graph neural networks (GNNs) used by previous GP solvers (Joshi et al., 2019; Sun & Yang, 2023; Li et al., 2024) all performed convolutions on nodes, which required initial node features, such as the node coordinates in TSP. Therefore, these GNNs were difficult to apply the ATSP, which only has distance matrix. The MatNet (Kwon et al., 2021) of LC paradigm provides a method for obtaining node features from an asymmetric matrix, but we fail to apply it to our convolutional network. To address this issue, we abandoned node features and adopted convolutions only on edges. To our best knowledge, this is the first global predictor with good performance for ATSP.
Prediction Conflicts. Although GP solvers can obtain a large amount of information, i.e., probability heatmap H. in a single inference process, they still require specific decoding methods extract solutions from H. Take the most common greedy decoding algorithm applied to MIS an example. When selecting nodes from high to low according to H. the most tricky thing is the addition of the current node causing constraint conflicts. Since the acquisition and decoding of H. is two-stage process, the only way for GP solvers to deal with such conflicts in the decoding stage is to skip the conflict node and continue searching, which leads to poor final solving results. We refer to this kind of conflict as prediction conflict, and use Nº. to denote the total number of prediction conflict, use C1 to denote the number of determined nodes/edges when the first prediction conflicts occurs. We take T2s (Li et al., 2024) as the representative of GP solvers to study and the results are shown in Table 8. We provide the following explanation for the experimental results: 1) An increase in the number of inferences can reduce the frequency of prediction conflicts in the heatmap decoding and delay the first occurrence of prediction conflicts; 2) The reduction of prediction conflicts generally improves the decoding results. However, when the first prediction conflict occurs relatively early (i.e., Ci < Obj.) the interpretability of subsequent predictions is lower, thereby leading the possibility that single step of inference may perform worse than multi-steps.
Table 8. Study of prediction conflicts on MIS.
RB-SMALL
SATLIB
METHOD
Obj."t
Obj-t
Dropl
No.1
C2 1
Obj.'t
Obj.t
Dropl
No 4
C2 f
Fast-T2T (,=1, (Li et al., 2024)
20.090
18.552
7.553%
39.334
9.604
425.954
421.734
0.995%
187.240
291.448
Fast- (S=1, 1,=3) (Li et al., 2024)
20.090
18.412
8.239%
9,532
15.034
425.954
423.266
0.634%
97.326
343.450
F2st-T2T (,=), (Li et al., 2024)
20.090
18.818
6.265%
3.092
17,272
425.954
424.112
0.434%
27.862
407.824
ER-700-800
BRR-1400-10
Метнов
Obj. '
Obj-t
Drop1
Nr 4
f
Obj.'
Obj.t
Drop1
No. 4
f
Fast-T2T (S=1, 1,=1) (Li al., 2024)
44,969
36.922
17.888%
152.070
17.414
50.938
36.414
28 28.499%
1116.219
4.531
Fast- (,=), 2024)
44,969
36.117
19.680%
73.539
21.359
50.938
34.305
22.649%
1010.984
4.039
Fast-T2T (,5) (Li al., 2024)
44,969
37.375
16.888%
22.289
29.516
50.938
33.203
34.806%
959.797
5.016
15

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
B.4. Comparison of Existing AE Solvers
Similar the mature paradigms GP and LC, we are dedicated to fostering our newly proposed AE paradigm so that more innovative works can be subsumed within this category. To our knowledge, similar concepts have been devised in few previous works, while systematic proposal and analyses of new solving paradigm have yet to emerge till our work. LwD (Ahn et al., 2020) introduces deferred Markov Decision Process (MDP) that dynamically adjusts the number of decision stages by allowing the agent to either determine or defer vertex inclusion at each step. Extended upon LCP (Kim et al., 2021) and GLOP (Ye et al.. 2024b), DualOPT (Zhou et al., 2025) attempts to address TSP through a dual divide- and-conquer strategy. It integrates a grid-based partitioning phase, which decomposes the problem into subgrids solved in parallel using LKH3, and a path- bash- optimization phase, where neural solvers refine subpaths iteratively. The nodes and edges within each round of conquering process is determined by the rough solution from LKH (Helsgaun, 2017), and only interior determinations are fixed towards subsequent rounds.
Table 9. Comparison of methods with similar design as our AE paradigm.
METROD
PARADIGM
TECHNIQUE
APPLICABLE PROBLEMS
LwD (Ahn et al., 2020)
AE
GCN+RL
MIS (locally dccomposable)
DualOPT (Zhou el al., 2025)
AE
LKIH+GAT+RL
TSP
MIS. MVC, MCI, MCui, TSP. ATSP, CVRP
COExpander (Ours)
AE
Diffusion+SL
Table 10. Comparative results on MIS and TSP of AF Solvers. denotes results reported from the original paper.
ER-700-800
ER-1400-1600
MIS
TYPE
OBI.f
DROP]
TIME!
OBI.f
DROP]
TIMEJ
KaMIS
Heur.
44.97"
0.00%
60.75s
50.94
0.00%
60.82s
LwD (Ahn et al., 2020) (S=1)
AE
37.29
17.07%
0.59s
39.52
22.40%
1.47s
COExpandor (S=1.,,=20.I.=1)
AB
42,38
5.75%
0.47s
48.16
5.43%
2.21s
LwD (Abr et at.. 5020) (S=4)
AE
39.21
12.30%
0.61s
42,48
16.60%
7,48s"
COExpander (I=II,,200II=I1)
AB
42.56
5.34%
0.46s
48.43
4.91 %
4.52s
TSP-1K
TSP-10K
TSP
TYPE
OBI.
DROP_
TIME
OBI.
DROP!
TIMEJ
Concorde LKH(500)
Exact/ / Heur.
23.12"
0.00%
84.41s
71.76"
0.00%
332.76s
DualOPT (Zhou et al., 2025)!
AE
23.31
0.83%
5.60s
72.62
1.21%
33.90s
COExpander
AE
23.27
0.64%
2.43s
72.80
1.45%
29.50s
Reproduction of LwD. We follow the training code provided in the github repository' of the Lwd (Ahn et al., 2020) and have made some fixes. We train the model for 20,000 iterations on the unlabeled ER-700-800 dataset (generated randomly) and test it on our ER-700-800 and 2RR11400/10 1400--600 datasets. The results are shown in Table 10.
Remark. Lwd is trained using reinforcement learning (Proximal Policy Optimization), which inevitably encounters challenges such sparse rewards and scalability constraints. Moreover, its application scope is relatively narrow, solely applicable to the "locally decomposable" problems (i.e., node-selection tasks in our discourse). DualOPT, on the other hand, places greater emphasis on the divide-and sonde-and-conqqee principle. Its core competence stems from the robust initial solutions computed by LKH, even requiring up to 10 runs. However, it is exclusively tailored for TSP. Notably, COExpander represents a pioneering effort in synergizing the latest generative architectures with supervised learning, exhibiting extensive applicability across
(isolated constraints like MIS), edge-selection tasks (simple global constraints like TSP), and even more complex-constraing VRPs (discussed thoroughly in Appendix ??). On basic COPs on graphs, COExpander achieves state-of-theearr performance without relying any external pre-solving techniques. Despite the limitations inherent in these methods, we retain an open-minded stance to view them as the preliminary practices within the paradigm of adaptive solution expansion (AE) for combinatorial optimization problems on graphs. It is our hope that this novel NCO pipeline will foster further innovations.
Phttps://githoin com
defer
16

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
C. Formal Problem Definitions
In this paper, our proposed method is evaluated on six representative COPs on graphs. Given a graph G = (V, where V 1L,2,....N. denotes the node set and the edge set, the tasks can be defined as follows.
Maximum Clique (MCI, Given G, clique K C V is subset of nodes such that every pair of nodes in K is adjacent. Mathematically, it aims to find K that maximizes ||| s.t., Vi,j E K, (i.5)= E.
Maximum Cut (MCut). Given G, a cut C = (S is a partition of the node set V into two disjoint sets S and 3. Mathematically, the problem is to find a cut C that maximizes Eies.JE3 Cij, where C is the adjacency matrix of G.
Maximum Independent Set (MIS). Given G, an independent set C V is subset of nodes such that no two nodes in are adjacent. Mathematically, it aims to find S that maximizes |S] s.t., Vi, j E S. (i,5) & E.
Minimum Vertex Cover (MVC). Given G, a vertex cover C S V is subset of nodes such that for every edge (i.j) E E, at least one of i is in C. Mathematically, it aims to find C' that minimizes |C| s.t., v(i,j) E, f.ee E Cr j C.
Traveling Salesman Problem (TSP), Given G along with a cost matrix C of shape N x N where the entry Cij is the cost for edge () &, it aims to find the tour т (in,". ,ix) to minimize the cost ExEL Cicint: + Ciyh
Asymmetric Traveling Salesman Problem (ATSP). ATSP is special case of TSP where the cost matrix is not necessarily symmetric, i.e., Cij = Cy: dose not always hold for all i.j E V. In particular, we follow (Kwon et al., 2021: Drakulic et al., 2023; Ye et al., 2024b) to study the metric ATSP where the triangle inequality holds, i.e., City + Cyk 2 C. for any different three nodes i, j. and k:
D. Discussion of Non-Learning Baseline Solvers
During our experimental implementation, number of issues have been uncovered regarding the baseline solvers and benchmark data referenced in numerous prior articles. 1) there is continuous citation of articles from several years past, yet the cited solvers are either outdated or have incorrect parameter settings. 2) the performance of the devices (dating back several years) utilized is subpar, which presents an obvious unfairness when compared to neural combinatorial optimization (NCO) approaches employing advanced CPU and GPU equipment. Therefore, we have used the more recent versions of all the non-learning traditional solvers employed in this paper, analyzed and discussed the solving parameters of some solvers, and conducted experiments on the dataset in a fair and advanced CPU environment. Additionally, to facilitate the use by future researchers, we have encapsulated all solvers and wrote convenient Python versions.
D.I. Gurobi
Introduction. Gurobi (Gurobi Optimization, 2023) is a versatile optimization solver used for solving various types of mathematical programming problems, including linear programming (LP), mixed iitterr programming (MIP), quadratic programming (QP), and more. In this paper, we use Gurobi to solve problems such as MCI, MCut, MIS and MVC. Although the field researching these problems is currently making extensive use of the Gurobi, we notice that there is no work that systematically introduces how Gurobi solves these problems. Therefore, we will provide detailed introduction to the three stages of Gurobi's solution process for these COPs, thereby providing a basis for the setting of Gurobi's s time limits. Note that we use the version 11.0.3 released on July 11, 2024.
Solving Stages. 1) Pre-solving. The pre-solving stage is the first step in Gurobi's optimization process. During this stage, Gurobi performs several operations to simplify the problem. The objective of pre-solving is remove unnecessary variables, constraints, and simplify the structure of the problem, making it easier to solve. Additionally, Gurobi will also use built-in heuristic algorithms to obtain an initial solution during this stage. 2) Root Relaxation. After pre-solving, Gurobi will solve the root relaxation, which refers to solving a relaxed version of the MIP (e.g. treating integer variables as continuous). Root relaxation is a key part of Gurobi's branch-and aanuh---nd--uunn algorithm, providing an initial solution and helping guide the subsequent search process. 3) Optimization. The optimization stage follows the root relaxation and begins the main branch-and-boun process. During this stage, Gurobi explores the search tree by branching on decision variables and sol solving subproblems recursively. The optimization process continues until optimal solution is found or the time limit is reached.
An Example. We take an instance each from the RB-LARGE and RB-GIANT test datasets of MCI as examples. As shown in
'https: htttpp::/wwwwwce gurobi. wom www./oommoadd///rraaaoooooooo
reacme-
v11-0-3/
17

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Fig. the time for Pre-Solve is very short, which means the solver obtained a heuristic initial solution very fast speed and then began the Root Relaxation. During the Root Relaxation stage, the solver is dealing with the relaxed problem, it does not modify the solution of the original problem. Therefore, if the preset time limit is reached during this stage, it is equivalent to directly returning relatively poor heuristic solution. This is also why the results are so poor when we set 300-second time limit for Gurobi to solve RB-GIANT. Therefore, when setting the time limit for Gurboi, it is necessary to first obtain the approximate time for Root Relaxation of the problem to be solved, and the time limit must exceed this time.
Optimization Progress Over Time (MCI-RB-LARGE)
Optimization Progress Over Time (MCI RB-GIANT)
Incumbent
Incumbent
Bound
Objective Value
Objective Value
60
80
70
30
50
90
200
800
Time
(a) LARGE
(b) RB-GIAN
Figure 5. The curve of objective during Gurobi solving MCI. Incumbent: the current searched best solution.
D.2. LKH
LKH (Helsgaun, 2017), Lin- Lin-Kernighan Heahaann-Hlsguun,,. is heuristic algorithm for solving the TSP and its variants, such as the ATSP. LKH uses local search and neighborhood exchange techniques (like 2-opt, 3-opt, etc.) to iteratively improve the current solution, generating shorter paths. Known for its strong performance, LKH can find opar-optimal solutions and excel real-world applications, especially for large-scale problems. The version of LKH we used is 3.0.75.
We greatly appreciate the work done by PyLKH which provides a Python interface for LKH and has been widely used in various previous studies ML4TSP, such DIFUSCO (Sun & Yang, 2023), T2TCO (Li al., 2023), FastT2T (Li et al., 2024), etc. However, during our re-implementation process, we discovered that the Ikh package? utilizes the SPECIAL parameter when calling LKH. This setting affects several parameters, including Gain23Used. When SPECIAL is enabled, Gain23Used set to 0 in LKH, which disables the use of both 2-opt and 3-opt. Therefore, we removed this setting when solving the TSP, resulting improvement of 97.7% in terms drop when trials set 100 and 95.8% % when trials to 500; for ATSP, the performance improvement is 99.7% % and 99.9% respectively.
significant improvement. As shown Table 11, for TSP, we achieved an average performance
D.3. Others
KaMIS Solver (Lamm al., 2016) is a powerful tool designed for solving the MIS problem. KaMIS employs combination of greedy algorithms, local search techniques, and meta-heuristies like Simulated Annealing and Genetic Algorithms explore the solution space. These methods are designed to quickly converge good solutions, even for large-scale graphs where exact methods would be too slow. We use the version 0.3.0% released on Oct 11, 2024.
Concorde Solver (Applegate et al., 2006) is an exact solver for the TSP. It combines advanced mathematical optimization techniques such as plain and granch-and-bout to achieve exact solutions efficiently. We use the version 12.19 released on Dec 19, 2003.
ruc. http:://aat.aateeeeeeee//////eep
18

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
GA-EAX Solver (Nagata & Kobayashi, 2013) is genetic algorithm-based method for solving TSP. It leverages the Edge Assembly Crossover (EAX) operator, well-known crossover technique specifically designed for TSP, to generate high-quality solutions. We use the version 1.0",, released on Dec 29, 2021.
Table 11. Comparative results regarding re-implemented LKH and the widely used original package. "Improv"" denotes the relative improvement in terms of the optimality drop.
LKH Package
Re- Re-Implementation
DATASET
TRIALS
IMPROV.
OBI.
DROPL
TIME
OBI.J
DROP!
TIME
TSP-50
100
5,68941
0.03120 15186%
0.03379s
5,68770
0.00180=0.02239%
0.03667s
94,231 %
TSP-50
500
5.68787
0.00478+0.05548%
0.04831s
5.68763
0.00071=000136%%
0.05833s
85.146 %
TSP-I00
100
11.77524
0.2237440.37015%
0.056158
1.75615
0.00039::000000000
0.07887s
98.239%
TSP-100
500
7.76210
0.08038++0.
19958%
0.07386s
7.75593
0.00099=00014139:
0.17751s
98,768 %
TSP-5000
160
16.79727
0.37958%
16.34771
00:01533500022733
0.72745s
99,241 %
TSP-500
500
16.69069
0.87548++.39330%%
0.41296s
16,54616
0.00217=0.01022%
1.84759s
99.752% %
TSP-IK
100
23.60515
1.31383s
23.12207
0.01709-00.020020
2.11221s
99.189 %
TSP-IK
500
23.43974
1.39137
1.36344s
23.11936
0.00536=0.01069%
4,64110s
99.615 %
ATSP-50
100
1.55778
0.05988s
1.55449
0.00068
0.05986s
99.674% %
ATSP-50
500
1,55572
0.0776440.2344399
0,08643s
1.55449
0.000141 0.0049966
0,08226s
99,820% %
ATSP-100
100
1,57642
0.66077+0.6499268
0.115576
T.56606
0.00131+0000 127%
0.12431s
99.802 %
ATSP-100
500
1.57037
0.27665
0.16125s
1.56604
0.00007=1000236%%
0.21403s
99.975 %
E. cc-Stanndadizzatin of Benchmark Datasets
Upon reviewing the recent work relevant to the COPs investigated in this paper, we have identified a substantial disparity in the benchmark datasets employed for evaluation among the works that examine the same problems, including, but not limited to, unfixed data generation process, varied quantity of testing samples, different normalization tricks, etc. This significant variation considerably reduces the informativeness and fairness of the evaluation process. In response this issue, our work represents the first and vastest attempt to standardize the training and testing datasets within the NCO community for the six COPs included in this paper. Through this effort, we have established total of 29 normative datasets that serve as benchmarks for different scales of the corresponding problems, as summarized in Table 12. The specific parameters for data synthesis of each type are introduced separately below.
E.1. Datasets for Node-Selection Problems
RB Graph. Following previous works (Li et al., 2024; Sanokowski et al., 2024), we use the so-called RB-Model (Xu et al., 2005) to generate RB Graph. Three main generation parameters: 1) n: the number of cliques, which are groups of nodes that are fully interconnected;; 2) k: the number of nodes within the clique are specified. 3) p. the parameter that controls the level of interconnectivity between different cliques. We have generated three scales of RB datasets, each corresponding to distinet number of nodes. RB-SMALL:
(200,300), E (20, 25). k (5, 12), p (0.3, RB-LARGE. E (800, 1200), n E (40,55) k E (20, 25). p E (0.3, 1.0). RB-GIANT: (2000, 3000), E (50, 60) k (40, 50), p E (0.3, 1.0). v denotes the number of nodes in graph.
ER Graph. ER graph (Erd6s & Rényi, 1960) is randomly generated with each edge maintaining a fixed probability of being present or absent, independently of the other edges. We follow DIFUSCO (Sun & Yang, 2023), Fast-T2T (Li et al., 2024) to set the probability as 0.15 and generate two datasets of different scales: ER-700-800 and ER-1400-1600.
BA Graph. BA graph (Barabási & Albert, 1999) scale-free graph where nodes are added incrementally, linking preferentially to highly connected nodes. At each step, a new node is added to the graph, which connects to at most existing nodes. We follow DiffUCO (Sanokowski et al., 2024) to set as 4 and generate three datasets of different scales: BA-SMALL., BA-LARGE, and BA-GIANT. The number of nodes are consistent with the RB graph.
Twitter Graph and COLLAB Graph. Twitter Graph dataset (Jure, 2014) and COLLAB dataset ( (Yanardag & Vishwanathan, 2015) are both part of the Stanford Network Analysis Project collection. Twitter Graph represents a snapshot of the social network formed by Twitter users and their interactions, and COLLAB Graph represents collaboration networks among scientists in various fields (nodes are scientists, and edges denote co-authorships). We download the original datasets from
hhtpps:////t thub. com www./////naaeeeeoe hwam://agaaaaaaaa wawagattayuiiiaao yuichii Saahii/AAAAa
19

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
TUDataset and follow Meta-EGN (Wang & Li, 2023) to select 20% of the data the generalization test sets.
E.2. Datasets for Edge-Selection Problems
Uniform Graph. For TSP, we follow Sun & Yang (2023) to generate TSP instances by randomly sampling nodes from a uniform distribution over the unit square and the data scale ranges from 50 to 10K. For ATSP, we follow the pioneering work (Kwon et al., 2021) to randomly sample the distance matrix from uniform distribution over the unit square and ensure the satisfaction of triangle inequality. Note that unlike recent works (Drakulic et al., 2023; Ye et al., 2024b; Drakulic et al., 2024; Lischka et al., 2024) that re- permute or re-normalize the distance matrices differently, we resist performing any additional tricks on the graph data to ensure fair comparison. The data scale of ATSP includes 50, 100, 200, 500.
SATLIB. Follow previous works (Qiu et al., 2022; Sun & Yang, 2023; Li et al., 2024), we divide the SATLIB dataset, and then transform the SAT problems into MIS problems.
TSPLIB. We select 2D-Fuuclidean distance data with the number of nodes ranging from 51 1002 from TSPLIB
Table 12. List of our re-collated datasets benchmarking six COPs for training and testing COExpander and any related neural solvers. The "MODEL" column denotes the dataset on which the model is trained. Lee. datasets with the same "TYPE" and "MODEL" is suggested for i.i.d. training-testing. whereas datasets with different "TYPE" and "MODEL" (with "testing" part only) are designed for evaluating the o.o.d. generalization performance of models trained on the corresponding (smaller-scaled, differently distributed, etc.) data. The parentheses indicate the solver parameters used: the maximum solution time for Gurobi and KaMIS; the maximum trials for I.K..
Training
Testing
ID PROBLEM
TYPE
MODEL
DATA SIZE
SOLVER
STORAGE
DATA SIZE
SOLVER
OBJ.
MCI
RB-SMALL
RB-SMALL
64,000
Gurobi(60s)
3,42GB
Gurobi(60s)
19.082
2
MCI
Twitter
RB-SMALL
195
G6r)hi(60s)
14.210
3
MCI
COLLAB
RB-SMALL
1000
Gurobi(60s)
42.113
4
MCI
RB-LARGE
RB-LARGE
6,400
Gurobi(300s)
4.74GB
500
Gurobi(300s)
40.182
5
MCI
RB-GIANT
RB-LARGE
50
(wrobi(3600s)
81.520
6
MCut
BA-SMALL
BA-SMALL
128,000
(urobi(60s)
L.78GB
500
Gurobi(60s)
727.844
MCut
BA-LARGE
BA-LARGE
128,000
Gurohi(300s)
8.08GB
500
Gurohi(300s)
2936.886
8
MCUt
BA-GIANT
BA-LARGE
Gurobi(300s)
7217.900
9
MIS
RB-SMALL
RB-SMALL
64,000
KaMIS(10s)
3,52GB
500
KaMIS(60s)
20.090
10
MIS
RB-LARGE
RB-LARGE
6,400
KaMIS(60s)
4.74GB
500
KaMIS(60s)
43.004
11
MIS
RB-GIANT
RB-LARGE
50
KaMIS(60s)
49.260
12
MIS
ER-700-800
ER-700-800
12,800
KaMIS(60s)
7,83GB
128
KaMIS(60s)
44.969
MIS
FR-1400-1600
FR-700-800
128
KaMIS(60s)
50.938
14
MIS
SATLIB
SATLIB
39,500
KaMIS(60<)
3.75GB
500
KaMIS(60s)
425.954
15
MVC
RB-SMALL
RB-SMALL
128,000
Guro
7.01GB
500
Gurobi(60s)
205.764
16
MVC
Twitter
RB-SMALL
195
G6r)
85,251
17
MVC
COLLAB
RB-SMALL
1000
Gurobi(60s)
65.086
18
MVC
RB-LARGE
RB-LARGE
6,400
Gurohi(300s)
4.74GB
500
Gurohi(300s)
968.228
19
MVC
RB-GIANT
RB-LARGE
Gurobi(300s)
2398.480
20
TSP
Uniform-50
Uniform-50
1,280,000
Concorde
2,48GB
1280
Concorde
5.688
21
TSP
Uniform-100
Uniform- 100
1,280,000
Concorde
4.95GB
1280
Concorde
7.756
22
TSP
Uniform-500
Uniform-500
64,000
Concorde
1.26GB
128
Concorde
16.546
23
TSP
Uniform- IK
Uniform-1K 1K
64,000
LKH(1000)
2.53GB
128
Concorde
23.118
24
TSP
Uniform- 10K
Uniform-10K
6,400
IKH((500)
2.59CBB
16
LKH(500)
71.755
25
TSP
TSPLIB
Mixed
49
Concorde 8.062
26
ATSP
Uniform-50
Uniform-50
640,000
LKH(500)
14.72GB
2500
LKH(1000)
1.5545
27
ATSP
Uniform-100
Uniform-100
128,000
LKII(500)
11.78GB
2500
LKI1(1000)
1,5660
28
ATSP
Uniform-200
Uniform-200
32,000
LKH(1000)
11.76GB
100
LKH(1000
1.5647
29
ATSP
Uniform-500
Uniform-500
6,400
LKH(1000)
14,70GB
100
IKH((000)
1.5734
Broader Impact. Future research on NCO solvers can be conveniently and consistently evaluated within the unified protocol of our re-standardized benchmarks and re-implemented baseline solvers.
"/teosss//esssrrrs..cataaaaaaaaa cs. http://www......ooooo//////////a http://///////eeeedsss____.
Phttp://comopt: ifi, uni - hhi otw.:
20

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
F. Details of Model Setting
Hardware. All models are trained and tested using NVIDIA H800 (80G) GPUs and an Intel(R) Xeon(R) Platinum 8558 96-Core Processor CPU. For all test evaluations, single GPU utilized, and the batch size is set to to ensure fair comparison of the solving time across different models.
Training Settings and Hyper-panee pappe--prameters. We have organized the training settings and model parameters of COExpander in Table 13. In the table, we adopt the name of the targeted training data to denote each individually trained model (21 in total) throughout this paper. In a curriculum-lcaming manner, models trained on larger-scale data are initialized from those trained on smaller-scale data. For instance, we first train the model for MCI problem on RB- S--LL dataset (line 1) for at least 50 epochs from scratch, and subsequently use the exact model weights initialize the training on RB-LARGE (line 2) for at least another 10 epochs. Note that AdamW (Loshchilov & Hutter, 2018) optimizer is adopted with a cosine-decayed LR scheduler and weight decay of 0.0001 train all the models.
Table 13. sepee-parameters and datasets for training COExpander different COPs. Pre-train: the checkpoint initialize corresponding model. Epoch: the minimum number of training epochs required (over corresponding data size) to guarantee reliable reproduction of reported results. IRR: learning rate. I.R and hatch size tuned align each other suit computational resources. Sparse:
sparsification factor by K-Nearest Neighbors, with -I meaning the model trained on dense graphs. Layers: the number of GCN layers.
Training Parameters
Model Parameters
PROBLEM
MODEL
PRE-TRAIN
DATA SIZE
EPOCH
BATCH SIZE
LR
SPARSE
LAYERS
HIDDEN DIM.
RB-SMALL
64,000
50
2e-4
12
RB-LARGE
RB-SMALL
6,400
10
5e-5
12
MCut
BA-SMALL
128,000
50
8
2c-4
N/A
12
256
MCut
BA-SMALL-FT
BA-SMALL
128,000
10
5e-5
N/A
12
256
MCut
BA-LARGE
BA-SMALL
128,000
10
5c-5
N/A
12
256
MCut
BA-LARGE-FT
BA-LARGE
128,000
10
5c-5
N/A
12
256
MIS
RB-SMALL
64,000
50
8
2c-4
N/A
12
256
MIS
RB-LARGE
RB-SMALL
6,400
10
5e-5
N/A
12
256
MIS
ER-700--00
12,800
50
2c-4
N/A
12
256
10
MIS
SATLIB
39,500
50
2e-4
N/A
12
256
RB-SMALL
128,000
50
2e-4
12
RB-LARGE
RB-SMALL
6,400
10
5e-5
12
13
TSP
Uniform-50
1280,000
50
32
2c-4
-1
12
256
TSP
Uniform-100
Uniform-50
1,280,000
50
16
2e-4
12
256
15
TSP
Uniform-500
Uniform- 100
64,000
50
2e-4
50
12
256
16
TSP
Unifonn-IK
Uniform-500
64,000
50
2
2c-4
100
12
256
17
TSP
Uniform- 10K
Uniform- IK
6,400
10
5c-5
50
12
256
18
ATSP
Uniform-50
640.000
50
32
2c-4
12
256
19
ATSP
Uniform-100 100
Uniform-50
128.000
50
16
20-4
12
256
20
ATSP
Uniform-200
Uniform-100 100
32,000
50
4
2e-4
12
256
ATSP
Uniforn-500
Uniform- 200
6,400
10
5e-5
12
256
Discussion on Graph Sparsification. For node-selection problems, the original data is sparse by nature, eliminating the need for additional processing. In contrast, for edge-selection problems, c.g., TSP and ATSP, in order to cut down on training memory and shrink the search space, the prevalent approach employ K-Nearest Neighbors (KNN) to sparsify the distance matrix. However, the application of KNN inevitably results in the loss of partial information from the original problem, which consequently causes deviations in problem-solving
For instance, given graph data G, consider an edge e. belonging to the optimal solution set x", if ei.j is the s-th nearest edge from point i, and if less than s, then the optimal solution of the sparse problem G i.e., xj. will no longer be equivalent to that on the original dense graph, i.e., x". We define R2 as the proportion of edges in x" that remain in G which reflects degree influence introduced by sparsification over the quality of the training data with supervision. Additionally, define the K-nearest sparse loss as L c(xi -)--))=-xx000 ;G) 100%, which represents the relative performance drop cix" c(x":G)
of x with respect to x". Obviously. the choice of K involves a trade-off among R2. Ci and the benefits of sparsity, such as reduced memory usage and accelerated search. Therefore, we conduct experiments on the sparse factor K for each node-selection problem, and the results are demonstrated in Table 14. The experimental results indicate that graph sparsification has little adverse impact on problem-solving for TSP (Rx 100% with K 50), thus justifying the

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
presumption that x x" when K is as 50. However, for ATSP, such impact is significant: even with large value assigned K (e.g., K > 100), a considerable number of optimal edges would be excluded from the supervision label after sparsification. Consequently, in this paper, we apply graph sparsification with K 50 to TSP, but refrain from using graph sparsification for ATSP. Table 14. Results on edge-selection tasks with different sparsification factors.
K 20
K
50
K- 100
PROBLEM
OBJ.*
R
OBI
R5
OBI.
R
OBI
TSP-500
16.546
99.990%
100.000%
TSP-1K
23.118
99.993%
100.000%
ATSP-200"
1.3647
95.120%
I.6999
8.2896%
98. 480%
1.6082
2.7630%
95.455%
1.3800
0.9551%
ATSP-500
1.5734
94.802%
1.7391
10.5228%
98.054%
1.6365
4.0116%
99.124%
1.6000
1.6945%
150
K 200
K = 250
PROBLEM
OBI.4
R5 4
OBJ.
45 4
R5
OBI.
R
OBI.
CK
ATSP-200
1.5647
99.860%
1.5688
0.2566%
ATSP-500
1.5734
99.488% %
1.5884
0.9526%
99.668%
1.5830
0.6064%
99.794%
1.5802
0.4267%
G. Supplementary Experiments and Discussions
G.1. Supplementary Results of Ablation Study
Ablation in Eq. 5. To determine the value of a in Eq. 5, conduct ablation experiments MIS(RB-SMALLL
example. We train the same model under six different settings (a [0.2, 0.5, 0.8, 0.9, 0.95, 0.99)), focusing primarily the results of the first seven epochs, as shown in Table 15 and Fig. 6. Since is merely probability value for prompting and does not directly affect the loss function, the training results tend to converge when the number of epoch is large. The experimental results show that, when the value of a is set relatively low (c.g.. 0.2, 0.5), the model has poor effect on one-shot reasoning. And when set relatively high (e.g., 0.95, 0.99), due the smaller proportion of prompted samples, there may be certain delay the model's learning of the mask M.. Therefore, we believe that the value of alpha should be set around 0.8 0.9. Furthermore, we observed that the first determination round often dominates the final performance, thus ultimately chose 0.9 in this paper, with the expectation that the model will be sufficiently trained on cases to solve from scratch while balancing the training diversity for solving from arbitrary intermediate states.
Metric
7.0
Metric
14
Alpha 0.2
0.2
Alpha 0.5
Alpha 0.5
Alpha = 0.9
Alpha 0.9
Alpha 0.99
6.0
Alpha = 0.99
Drop (96)
Drop (%)
12
5.0
4.5
4.0
10
3.5
3
5
Epoch
Epoch
(a) COExpander (S=1, D,=1,
(b) COExpander (S=1, D,=20, 1,=1)
Figure 6. Ablation study on a: in Eq. using MIS (RB-SMALL)) as an example
22

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Table 15. Ahlation study on a in Eq. 5 using MIS (RB-SMAIL.) as an example.
COExpander (S=1, D,=I,T=11)
EPOCH-1
EPOCH-2
EPOCH-3
EPOCH-4
EPOCH-5
EPOCH-6
EPOCH-7
0.2
17.200, 14.210%
17.478, 12.873%
17.584, 12.356%
17.584, 12.348%
17.762,
11.480%
17.642, 12.053%
17.782,
11.372%
0.5
17.338, 13.562%
17.508, 12.703%
17.756, 11.512%
17.668, 11.931%
17.732, 11.598%
17.828, 11.144%
17.842,
11 11.064%
0.8
17.608, 12.222%
17.644, 12.044%
17.824, 11.146%
17.878. 10.881%
18.012, 10,229%
17.968, 10.229%
17.950.
10.522%
0,9
17.470, 12.894%
17.730, 11.594%
17.634, 12.098% %
17.740.
11.567%
10.890% 17.878,
17.868, 10,940%
17.924,
10.651%
0.95
12.509% 17.548,
12.073% 17.634,
17.644,
12.046%
17.890, 10.817%
17.922,
10.662%
17.924,
10.662%
17.948,
10.546%
0.99
17,418, 13.147%
17.658, 11.974%
17.792, 11.314%
17.836, 11.107%
17.950, 10.531% %
18.064, 9.985%
18.080, 9.895%
COExpander (S=1. D,= I==1)
EPOCH-1 1
EPOCH-2
EPOCH-3
EPOCH-4
EPOCH-5
EPOCH-6
EPOCH-7
0.2
18.970, 5.515%
19.214, 4.291 %
19.238, 4.153%
19.268, 4.057%
19.312, 3.804%
1..33,3.7199
19.344, 3.665%
0.5
90.054.5.1136
19.184. 4,454%
19.240, 4.172%
19.334, 3.70%%
19.304, 3.856%
19.312, 3.836%
19.296, 3.900%
0.8
00.114.4.792%
19.166, 4.540%
19.306, 3.839%
3,598%
19.348, 3.636%
19.364, 3.550%
19.356, 3.600%
0.9
19.052. 5.13%
19.252. 4.095%
19.246, 4.133%
19.334, 3.704%
3.721%
19.356, 3.602%
19.378. 3.502%
0.95
18. 18,9 5.810%
146, 4. 632%%
19.184, 4.437%
19,31,, 3.817%
19.350, 3.632%
19,340, 3.688%
19.366, 3.540%
18.684, 6.911%
928,, 5.706%
19.198, 4.383%
19.246, 4.120%
19.256, 4.097%
19,320, 3.782%
19.340, 3.690%
Ablation on Backbone model. In this paper, we primarily adopt the consistency model (Li et al., 2024) as the global predictor for its powerful expressiveness and performance. However, this does not mean that AE is dependent on the specific consistency model. should be noted that the AE we propose a solving paradigm and does not rely on any specific model or solver. To verify this point, we have supplemented experiments using GCN (Joshi et al., 2019) as the global predictor on the MIS problem, as shown in Table 16. The experimental results indicate that the GCN model applying the AE paradigm achieved an average performance improvement of 68.4%. Additionaly, it can also be seen that the consistency model (single inference) has an approximate 6.6% performance enhancement compared with the GCN model.
Table 16. Ablation results of different backbone models for COExpander on the MIS problem. Compare the line of method "X" and the line of method "COFxpander-X" learn the as referred to as "COExpander" elsewhere in this paper.
enhancing effect of our AE paradigm. COFxpander-CNM is the same model
RB-SMALL
RB-LARGE
METHOD
TYPE
OBI.1
DROP
TIMEL
OBJ.1
DROPI
TIME,
KaMIS (Lamm et al., 2016)
Heuristics
20.090*
0.000
45,809s
43.004
0.000
56.974s
Gurobi (Gurobi Optimization, 2023)
OR
20.090
0.000++0.000%
0.538s
42.192
1.829+2.942%
33.843s
GCN (Joshi et al., 2019)
GP
18.056
9.997-16.68
8
0.014s
36.040
16.029-16.4499
0.044s
COExpanderGGCN (D,=5)
AE
19.292
3,905.13 936%
0.050s
40.092
6.683:13 705%
0.188s
COExpander GCNN (D,=10)
AE
19.376
3.480 3.53%%
0.084s
40.674
5.361 +: 3.2 166
0.361s
COExpander-GGI GCN (D,=20)
AE
19.464
3.055 3.26%
0.121s
40.892
1.862.1..0042%
0.650s
CM (Li et al., 2024) L,1)
GP
18,400
8,305
381 1
0.014s
36.394
15,219 L..2%%%%
0.044s
(S-
AE
19.500
2.877-F-5.4866
0.052s
40.674
33359--5.220246
0.1883
COExpander-CM (S=1. 1, 1,=1)
AE
19.596
2.410.13.003 .388%
0.092s
41.056
4.477
0.364s
COFxpander-CM (S=1, D,=20, I,=))
AR
19.662
2.088 2.088++2.888 +2891 %
0.112s
41.234
4.060 +.822%%
0.624s
ER-700-800
ER-1400-1600
METHOD
TYPE
OBI.1
DROP|
TIMEL
OBJ.1
DROPL
TIME!
KaMIS (Lamm al., 2016)
Heuristics
44.969*
0.000+0.000%
60.753s
50.938*
0.000+0.000%
60.824s
Gurobi (Gurobi Optimization. 2023)
OR
38.781
13.749=3.017%
60.489s
44.813
12.015-22.36%
3602.519s
GCN (Jushi et al., 2019)
GP
35,359
21.360
4.087%
0.039s
37.742
25.895 48.4%
0.118s
CÖExpandei-GGi (D,==)
AE
40.477
9,984-F3.
340%
0..12s
43.695
14.20443.3558
0.5313
COExpander-GCN (D,=10)
AE
41,656
7.356.12.
909%
0.313s
45.453
10.75512..0024
1.016s
COExpander (D,=20)
AE 42.117
6.331+2.712%
0.477s
46.203
9.284+22.49497
1.555s
CM (Li et al., 2024) (S=1,1,=1)
GP
35.711
20.580 169%
0.039s
37.859
25.670=23.0 368%
0.117s
COExpander CM (S=1. T,E))
AE
41,055
0886-1311844
0.172s
45.625
10.41723.
2,22
0.531s
COExpander (S=1, 10= I,=1)
AE
41.961
6.683.12.886
866%
0.305s
47.094
7.538 866%
1.001s
COExpander-CM (S=1, D,=20, I,=I)
AE
42.383
5.746+22.639%
0.469s
47.523
6.691+2.566% %
1.508s
Ablation on S, D. and Ig. The complete table of the ablation study (corresponding to Fig. 2) is presented in Table 17.
23

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Table 17. Ablation results on the number of sampling (S), determination steps (Da), and inference steps (Ta). S: SMALL; L. LARGE; FR-7700-00;; ST: SATLIB.
ER:
Settings
MIS-RB-S
MIS-RB- RB--
MIS-ER
MIS-ST
MCI-RB-S
MCI-RB-I.
MVC-R-S
MVC-R-I.
MCnt-BA-S
MCur-BA-I.
S=1,D,=I1,=1
8.305%
15.219%
20.580%
1.031%
4.870%
9.809%
0.827%
0.696
3.504%
5,231
S=1,D,=1.1=5
6,420%
14.208%
15.231%
0.5395
4.748%
22.722%
0,972%
0.621%
0.789%
0.523%
$=1,D,=1,1,=10
4.646%
11.485%
12.380%
0.413%
3.220%
16.967%
1.032%
0.543%
0.548%
-0.011%
$=1.0,=1,1,=00
3.710%
9.388%
10.618%
0.329%
2.850%
12.672%
0,984%
0.453%
0.319%
-0.669
S=1,D,=511,=1
2.876%
5.359%
8.686%
0.356%
2.801%
8.870%
0.466%
0.256
0.379
66,599%
S=1,D,=101,=1
2,410%
4.464%
6.683%
0.2695
2.406%
8.355%
0,410%
0.205%
0.157%
-1.124%
$=1,D,=20.1=1
2.088%
4.060%
5.746%
0.215%
1.892%
8.817%
0.398%
0.176%
0.058%
-1.38%%
S=2.D,=1.1=1
7.502%
15.228%
19.226%
0,964%
2.292%
5.018%
0.732%
0.651%
3.243%
5,009%
$=1,1,1111111
6.877%
12.82916
18.095%
0.914%
1.510%
2.977%
0.665%
0.614%
3.080%
4.821%
S=1,
6,409%
12.083%
17.382%
0.878%
1.027%
1.720%
0.611%
0.581%
2,949%
4.670%
G.2. Supplementrryy Results of Generalization Study
TSPLIB. For TSP, we conduct generalization experiments on the well-known TSPLIB. The results are shown in Table 24.
Our average gap on the number of nodes ranging from 51 to 1002 is only 0.367% %.
G.3. Complete Results on the Six COPs
Results for MIS. The complete results are presented in Table 18. Compare with pervious SOTA NCO solvers. COExpander has significant advantages in both performance and time. Without using sampling, COExpander achieves performance improvement of 27.7% %. 61.1 %. 39.6% % 24.6 %, 80.4%. 61.3% % and a speedup of 3.7x, 7.6x, 2.2x, 12.0x, 1.6x, 8.6x on RB-SMALL, RB-LARGE, ER-700-800, SATLIB, ER-1400-1600, RB-GIANT, respectively. When all methods employ sampling (x4), COExpander realizes a performance improvements of 14.7% %. 54.9%. 25.5%, 20.0%, 20.0% 1. 20.0%, and a speedup of 1.5x, 19.6x, 2.8x, 2.8x, 1.5x, 23.1x. Compare with traditional solvers, COExpander is superior in solving speed, and as the scale increases, such as ER- 1000-140000000 COExpander even excels Gurobi in solving performance.
Results for MCL. The complete results are presented in Table 19. Compared with previous SOTA NCO solvers, COExpander has significantly enhanced the solution performance, with a 94.8% improvement for RB-SMALL; and a 94.2% % improvement for RB.LA. Besides, we have studied how the time limit affect the solution quality of Gurobi on RB-GIANT and have made a detailed analysis in Appendix D. However, even when Gurobi is set with a maximum time limit of 3600 seconds, COExpander can still achieve an improvement of 6.4 % with a speedup of 2372.5x, which fully demonstrates the significant advantage of COExpander in large-scale MCI problems.
Results for MVC. The complete results are presented in Table 20. Compared with previous SOTA NCO solvers, COExpander has significantly enhanced the solution performance, with a 81.4% improvement for RB-SMALL; and a 96.3% % improvement for RB-LARGE. Besides, we have extended the problem scale to RB-GIANT for the first time and have surpassed Gurobi-60s.
Results for MCut. The complete results are presented in Table 21.
On BA-SMALL dataset, COExpander have achieved a breakthrough surpassing the previous SOTA as well as Gurobi-60s: on BA BA-LARGE and BA-GIANT dataset, although there was no improvement in performance, COExpander achieves speed increase of 7.5x.
Results for TSP. The complete results are presented in Table 22. The TSP is one of the most extensively studied problems in NCO, which is also the only one among the six problems discussed in this paper that covers three paradigms as well as the divide-anddconquer (D&C) method. From the experimental results, we can observe that the GP solvers and our COExpander have significant advantages in both performance and speed compared to the LC solver and the D&C method. The previous SOTA is Fast-T2T, which is also the global predictor adopted this paper, and our COExpander has achieved an improvement of about 17.5% % on this basis.
Results for ATSP. The complete results are presented in Table 23. Compare with pervious SOTA NCO solvers, COExpander has achieved performance improvement of 50.8 %, 36.6%, 45.5%. 70.7% on ATSP-50, ATSP-100, ATSP-200, ATSP500 respectively. Besides, it is worth noting that when D. 1, COExpander can be regarded as a type of GP solver. To our best knowledge, this is the first effective global predictor for ATSP.
24

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Table 18. Complete results on MIS.
RB-SMALL
RB-LARGE
METHOD
TYPE
OBI.
DROPL
TIMEL
OBI-1
DROPL
TIMRI
KaMIS el al., 2016)
Heuristics
20.090"
0.00010.000%
45.809.
43.004
0.000100.000%
56.974s
Gurohi (Gurohi Optimization, 2023)
OR
20.090
0,000+00000%
0.538s
42.192
2.929
33.843s
Fast-T2T ($11) (Liett 2024)
GP
19.498
2.887.33325%
0.414s
DiFUCO: CE ($=1,==1) (Sanokowski al., 2024)
GP
19.200
4.369 3.6965
0.470:
38.490
10.428 3.552%
4.712s
COExpander ($=1.,,=11_=)))
GP
18.400
6.500-56.388 1%6
0.014s
36.394
13.21926.22 259%
0.044s
COExpander ($=1,1)
19.662
2.088.1 1..991 %
0.112s
41.234
4,060 2.822%
0.624s
COExpander -5111
%
0.192s
740%
0.714x
COExpander (5_110,
19.604
2.375443.0038
0.802s
40.590
5.559--3.3338 33344
3,562s
COExpander ($=1.D,; Beani--iB
GF
18.466
6.
0.020%
36.530
14.3022:3 5,942
0.104s
Fast-TT (S= 2024)
GP
19.738
1.700=33321
0.860s
DifUCO: (S=..=1)) (Sankkowkii al., 2024)
GP
19.380
3.464 388%
1,587s
39.546
7.944:13.177 1711%
25.479s
=L= COExpander (S=4.D;=201==1)
GP
18.690
188775566756
0.018s
37.424
12.829 7.749% 764%
0.138s
19.706
1.880=2..00 691%
0.120s
41.438
3.582:12.3799
1.298s
COExpander (S=1.0);111=20))
1.690:12.4676
0.332s
40.066
6.742.1.3.711%
2.398s
COExpander ($=110),
AE
19.786
1.442:12.417% %
0.652s
40.686
5.30611...901%
5.484s
COExpander (S=4.D,=1.L=1))> Beam-16
GP
18.748
6.584:15 404%
0.052s
37.498
12.658:5..6199
0.368s
ER-700-800
SATLIB
MCTIOD
Oal.f
DROP4
TIMEL
OBJ.f
DROPL
TIME!
KaMIS (Lamm et al., 2016)
Heuristies
44.969
0.000=0.000%
60.753s
425.954
0.000=00.00%%
24.368s
Gurobi (Gurobi Optimization, 2023)
OR
38.781
13.749:1.017%
60.489s
425.924
0.007:10.07%%
3.953s
DIFUSCO (S=1 (0)) (Sun Yang, 2023)
GP
38.641
14.079:6.5644
2.797s
424.744
0.285 252%
2.744s
Fast-T2T ($=1 aL.
40.688
9.513#33. 153%
1.031s
424.438
0.358:10.556
1.704s
COExpander -5,
GF
35.711
380--44 T69
0.03%
42T.575
T.03T T.63T 50
0.006s
COExpander 10=1,
42.383
5.746:t2.6399
0.46%
425.046
0.215:10.235
0.228s
COExpander (S=1.D,=1.L=20))
GP
40.195
10.618 177%
0.641s
424.556
0.329:10.2479
0.190s
COExpander ($=1.0))3.11220)
AE
41.992
6.610:2..771%
3.188s
424.734
0.287:10.228%
1.034s
UIFUSC0 (Sun Yang. 2023)
GP 40.969
3.88993.. 122%
5.445s
425.108
0.200:10.001 201%
2.962s
Fast-T2T [c
41.742
7.179%2..33%%
1.961s
425.002
0.252:10.1 197%
2.670s
COExpander (S=4.D,=I.L.-))
36.828
095--9953 726%
0.10%
422.078
0.914460 480%
0.036s
COExpander ($=4.D,=20.1=I)
42.563
5.3433:2.222%
0.703s
424.776
0.278
245%
0.268s
COExpander ($=1.D,=1.1=20))
GP
41.430
7. 7,867
0.677:22.4600 460%%
2,094s
425.276
0.160:10. 161%
0.428s
COExpander ($...0)=3.1.=20)
AE
42.125
6,321 2.333%%%
4.297s
425,278
0.160:0.16885
1.056s
FR- 1600-1600
RB-GIANT
METHOD
TYPe
OaI.1
DROP
TIME]
O81.1
DROP)
TIME;
KaMIS (Lamm et al. 2016)
Heuristics
50.938
0.000=00.000%
60.824s
49,260"
0.000.10.000%
60.960s
Gurohi (3600)) (Gurobi Optimization, 2023)
OR
44.813
12.015112.36%%
3602.519%
48.560
1.377.1
3426.207s
Gurohi (300s)
Optimization, 2023)
304.485s
302.726s
Gurobi (60s) (Gurobi Optimization, 2023)
40.820
19.856-t2.5755
62.141s
44.760
8.806 10.968%
56.010s
Fast- T2T ( (I.i 2024)
GP
36.797
3.570s
DiHUUC: CE [S=1,F==) (Sanokowski al., 2024) 2024)
GP
40.480
17.722+55. 0.0---577666 765%
45.680s
COExpander ((,,))
GF
33.8859
23.66701.3
868
0.1178
36.200
162.3.666.772 (
0.2200
COExpander ($=1,),=)011===
48.164
5.432 2.188888
2.211s
45.840
6.856 3,531 %
5.340s
COExpander (5-1,
13.43004-3.
5.117s
38.380
21 21.9955-6.499
($==
25.417.1.2.19
6.961s
DifFUCO: CF ((5_4_111 (Sanoowwkkk 2024)
GP
42,120
14.352+4..5220
339.010s
CoExpandei ($=:000550.1.1))
AE
48.429
4.911-F2.107%
4,316
36.640
5.221 1..976%
14.660%
COExpander ($=4.D,=1.1=50)
GP
46.
9.446:12.65455
23.781s
40.260
1. 109%
43.760s
25

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Table 19. Complete results on MCI.
RB-SMALL
RB-LARGE
METHOD
TYPE
Oul.f
DROPL
TIME!
OBI.1
DROPİ
TIME
Gurobi (Gurobi Optimization. 2023)
OR
19.082
0.000:10.000%
0.900s
40.182
0.000:10.000%
276.657%
DiRUCO: CE (S=1 (F=1, (Sanoknwski et al. 2024)
GP
15.142
18. 185%
0.559s
Meta-EGN (Wang 2023)
GP
17.512
8.300=12.7199%
0.270s
33.792
15.4871188 576%
COExpunder (S=1.D,=11I,-1))
GP
1.,70=10.775%
0.016s
36.402
9.809= 700%:
0.042s
COExpander (
AE
18.766
1.892:1-4.499
0.046s
1..17:15.3266
COExpander (S=I.D,=I.-=20)
GP
186608
650 945%
0.200s
35.384
12.672-119.87455
0.708s
COExpander ($=1.0)=$.I:20))
AE
18.686
2.374 1%
0.516s
36.176
10.159:1:1..80 15.6%
1,660s
COExpander (S=1.D,=1,1,=1)+ Beam-
GP
18.664
2.510:16.024%
0.022s
38.754
3.79819.0339
0.104s
COExpunder (5.1, Beam-16
GP
18.768
1.914:14.745 %
0.200s
DiAUCO: CE (B== al. 2024)
GP
16.206
12.527 18. 18.3%%
1.412s
GP
18.846
1.500=4,088
0.0185
39.074
2.97143, 2.66
0.130s
COExpander ($=4,1);2001;==)
AE 18.922
1.018+ 3.000%
0.056s
39.170
2,722 77.87%%
0.414x
COExpander ($=44,),1,,1122))
GP 18.982
0.60742.52199
0.328s
38. 18.706
4.197:: 11 1.56%
2.386s
COExpander (S=1.D,=5.I=20))
AE 19,002
0.503:12.0777 %
0.646s
39.062
2.993:1 985%
6.358s
COExpander ($=4,D;=1,1;=11- Beam-emm--
GP 18.976
0.675 156%
0.058s
39.880
0.898:13.1500
0.368s
COExpander (S=41,),1111=220)
Twitter
COLLAB
METHOD
TYPE
OR1.1
DROP
TIMRJ
OBI.1
DROPJ
TIME_
Gurobi (Gurobi Optimization, 2023)
OR
14.210
0.000=0.000%
0.276s
42.113*
0.000:10.000%
0.063s
Meta-EGIN (Wang Li. 2023)
GP
13.677
6.81226.352%
0.134s
41.993
0.662413 392%
0.129s
COExpander (11,.))
GP
13.051
9.3361:1 13.44%
0.015s
41.393
2.496.19 210%
0.013s
COExpunder ($=1,,,=20,1.=1)
AE
13.528
6.154=11.88
0.067s
41.874
1.808:8.00 0.002809925 %
0.139s
COExpander (S=1.D.=1.I=20)
GP
12,236
16.911#24.0144
0.195s
39.501
14.496.1226 836%
0,222s
COExpander (S=I.D,=11I==1++ Beam-16
GP
13.303
6.504.13.411%
0.021s
41.7f2
1.69515.767
0.014s
COExpander (S=1.D,=1.1,=20) Beam-16
GP
10.067:1 192%
0.200s
41.084
15.%%
0.220s
COExpander (S==41),=1.1.=1)
COExpander (S=I.D,=20.I=I))
AE 13.805
3.997=10.243%
0.082s
42.040
0.84116.363%
0.092s
COExpander (S=4.D.-1.L=20))
GP
13.349
8.596: 106%
0.297s
41,051
5.974 17.730
0.314s
COExpander [S=[06,=1,,,=1++ Beam-
GP
T3380
127661477777
0.0455
42,034
3.333T-3.TT83
TT.025.
COExpander (S=4.D,=1.I=20)) Beam-16
GP
13.610
5.157%9
0.318s
41.620
3 3.023-19.230%
0.437s
RB-GIANT
METHOD
TYPE
O8ı-f
DROPL
TIME
Gurobi (3600s) (Gurohi Optimization, 2023)
OR
81.520*
0.000:0.0009%
3606.201s
Gurobi (300s) (Gurobi Optimization, 2023)
OR
$1.920
32.774=23.133
1311%
302.640s
Gurobi (60s) (Gurobi Optimization. 2023)
OR 50.980
33.917=22.69314
60.248s
COFxpander (,=,,)
GP 60.860
22.902 39.840%
0.240s
COExpander (S=I.D.=I.I=1)+ Beam-16
GP
77.340
2.732-24.92444
0.420s
COExpander ($...)
GP
77.860
2.1455
25.00
0.820s
COExpander ($=1,,,=1.I==1)+ Beam-
GP
84.120
-6.424 :: 26.720
1.520s
26

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Table 20. Complete results on MVC.
RB-SMALL
RB-LARGE
METHOD
TYPE
OBJ.
DROPL
TIMEL
OBI
DROPL
TIMEL
Gurobi (Gurobi Optimization, 2023)
OR
205.764*
0.000+0.000%
3,341s
968.228'
0.000:10.000%
290.227s
Meta-EGN (Wang & Li, 2023)
GP
208.974
1.56310.5799
0.297s
1010.692
4.400-1..337%
1.025s
COExpander ($1,,1
GP
201.460
0.827+0.3755
0.016s
974.950
0..96-F0.2769:
0.044s
COExpander (S=1,D,=20.1==1)
AE 206.576
0.398:10.381 %
0,108s
969.922
0.176:10. 1.18%
0.522s
COExpander ($=1,0;=1.1=20)
GP
207.778
0.984=0.577%
0,186s
972.608
0.453:10.1 195%
0.718s
COExpander ($=1,0)=551,=20)
AE 207.374
0.787=0.535%
0.870s
970.734
0.259:+0. 151-
3.520s
COExpander (S=4,D,=1.1,=1)
GP
207.126
0.665=+0,500%
0.018s
974.162
0.614:+0.244%
0.132s
COExpander ($=4,1)=2001,==)
AE 206.360
0.290+0..332% %
0.086s
969.806
0.163+ 0.11%
0.626s
COEspander ($=1,0
GP
207.060
0.633+0.4625%
0.322s
971.420
0.330 1635%
2,412s
COExpander (S=4,,,5511,-1
AE
206.906
0.557=10.430%
0.646s
970.416
0.227 1244%
4.778s
Twitter
COLLAB
MеTHOD
TYPE
OBJ.
DROPL
TIMEI
OBI.
DROP]
TIMEL
Gurobi (Gurobi Optimization, 2023)
OR
85.251
1.000-1.0005.
0.133s
65.086
0.000-10.000%
0.058s
Meta-EGN (Wang & Li, 2023)
GP
92.728
L.6701445989
0.192s
65.694
1.248:22.457%
0.148s
COExpander (200,1)
AE
85.574
0.326 0.574 %
0.138s
65.121
0.347:F0.3033
0.056s
COExpander ($5..D,=5.I.=0))
AE
86.031
0.857=+1 .666%
0.862s
65.114
0.057=10.39 %
0.503s
COExpander (S=4,D,=20.11
AE
85.446
0.204110.483 %
0.062s
65.107
0.028:10.227%
0.038s
COExpander (5=,,0
AE 85.574
0.318:10.588%
0.446s
65.092
0.008::0.110%
0.354s
RB-GIANT
METHOD
TYPE
OBJ.
DROP]
TIME!
Gurobi (3600s) (Gurobi Optimization. 2023)
OR
2396.780"
1.000-10.0004
1813.786s
Gurobi (300s) (Gurobi Optimization. 2023)
OR
2398.480
0.067=0.1 113%
211.428s
Gurobi (60s) (Gurobi Optimization, 2023)
OR
2400.800
0.162=#0.1229
58.121s
COExpander ($=I,D;=II,=I)
GP
2407.540
0.45010.1 110%
0.240s
COExpander (S=1.D.=501.=1)
AE 2400.600 GP
0.160:10.011 %
4.360s
COExpander (S=,,1,=1,,==)
2406.066
0.388-0.. 104%
0.820s
COExpander (S=1.,,=50.1.=1)
2400.360 AE
0.149:00.052%
8.200s
27

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Table 21. Complete results on MCut.
BA-SMALL
BA-LARGE
METHOD
TYPE
OBI.1
DROPj
TIMEL
OBI.1
DROPL
TIMEJ
Optimization, 2023)
OR
0.000=0.000%
DiffUCO: CE (S=__F==)(Sucoooooskk 2024)
GP
726.900
0.146=0.483%
0.197s
2986.932
-1.68800.480
0.654s
COExpander ((,,))
GF
7702.376
7.500-T88477
2781.34
5522T-7..569
6.016s
COExpander (501.))
AE 727.526
0.05%=0.419%
0.182s
2978.200
-1.387 1.51%
0.204s
COExpander ($=110
GP
725.624
0.519=
0.172s
2948.112
0.369
0.194s
COExpander -$112,,
AE 725.888
0.284 00500%
0.888s
2952.520
LL.118+0.5555.
0.992s
GF
718.592
7.755
0.0146
2941,740
-0.153-50.583%
0.016s
AE 726.382
0.255%
0.184s
2975.712
-1.304
0,202s
GP 726.538
0.195=0.476%
2980,508
-...7
0.196s
COEx:ande-F((S:11::311-0)
726.524 AE
0.196=0.495%
0.884s
2978.486
-1.39910.50094
0.972s
DiffUCO: CE (Sanlooo 2024)
GP
727.534
0.061=0.462%
0.610s
2989,458
-1.773=0.466%
2.701s
GP
705,446
3.080-1.500
0.016s
2705.804
4.801=1.051
0.024s
COExpander (S=1.,;=201==))
AE 726.798
0.449%
0.064s
2961.500
40.221
0.114s
GP 728.316
0..4990..37 %
0,202s
2960.664
0.797110.994%
0.362s
GP 720.240
0.056=0.666%
0.016s
2954.102
-0.57420.534%
0.024s
AE 726.232
2238-0.46655
0.064s
2980.652
-1.475+0.475%
0.114s
728.272
0.043:0.3865
2987.142
-1.693-04744%
BA-GIANT
METHOD
TYPE
OB1.1
DROP]
TIMEL
Gurobi (3600s (Gurobi Optimization, 2023)
OR
7217.900*
0.000=0.000%
3601.342s
(300s) (Guroii Optimization, 2023)
OR
7217.860
0.001=0.003%
Gurobi (60s) (Gurobi Optimization,
OR
7216.960
0.011=0.075%
61,228s
DifTUO: CE [S=1,F=1) (Sanokowski al., 2024)
GP 7384.020
-2.306:t0.32691
2,480s
DiTUCO: CE ($=4F==1) F=1)
(Sanokowskiee 2024)
GP 7387.760
-2.358 : 0.325
10.760s
CoExpander [$=1_
GF
6860 220
4.935=0.841&
0.060%
COExpander ($=1..,.011))
AE 7369.980
-2.111:0.3304
0.720s
COExpander (S=1_D;==11=500))
GP
7308.260
-1.258:10.4037
0.700s
COExpander (S=4.D,=11==00))
GP 7329.420
-1.55340.33 3399%
1.760s
GP
7264.660
-.665-+-0.4448
AE
7361. 800
-1.997--.3188%
0.740s
COExpandee-P(S=::D:==1-133
GP
7372.100
-2.13420.3306 330%
0.720s
GP
7381.920
1.2776-0.323 %
1.760s
28

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Table 22. Complete results on TSP.
TSP-50
TSP-100
METHOD
TYPE
OBI.
DROP]
TIME,
OBIL
DROPL
TIMEL
Concorde (Applegate et al., 2006)
Exact
5,688
0.000=0.000%
0.059s
7.756'
0.000=0.000
0.238s
LKH (500) (Helsgaun, 2017)
Heuristies
5.688
0.001 1.001+0.0149
0.058s
7.756
0.001 +0.014%
0.176s
GA-EAX (Nagata & Kobayashi, 2013)
Heuristics
5.688
0.000-0.0019
0.101s
7.756
0.000=0.0004
1.862s
GCN + 2OPT (Joshi et al., 2019)
GP
5.691
0.066=0.3116
0.007s
7.775
0.243=0.5465%
0.009s
GNNGLS GLS (Hudson et al., 2021)
GP
5,707
0,333=0.800 8009
0.020s
7,857
1.295#1.0266
0.129s
DIMES + 2OPT (Qiu al., 2022)
GP
5,891
3.578+2.361
0.007s
8.108
4.543+1 838%
0.012s
DIFUSCO ($=1,1,5 2OPT (Sun Yang.
GP
5.693
0.099
2.587s
7.776
0.265=0.4633
2.691s
F2T ($=1,1=5)) 2OPT (1ietal,, 2024)
GP
5.689
0.022 0.083%
0.254s
7.762
0,074 0.226 %
0.252s
RI4CO [AM] + 20PT (Berto al. 2024)
LC
3.733
0.7991.0 9332%
0.171s
7,902
1.88=1.11774
0.247s
RL4CO (POMO)+ 2OPT (Betto et al., 2024)
LC
5.727
0.656
0,221s
7,918
2.097 1.19%
0.319s
RL4CO (SymNCO) 2OPT (Betto ot at, 2024)
LC
5,726
0,680=0,8075,
0.169s
7,891
1.746 1.08 %
0.315s
BQ-NCO + 2OPT (Drakulic et al., 2023)
LC
5.795
1.894 1.02%
0.205s
7,893
1.772
0.387s
GLOPP (N=:3._.0000331g111100....0 (Ye et al., 2024b)
D&C
5.704
0.287-0.495%
2.71%
7,831
0.973+
2.777s
COExpander (SI_,===L++ 20PT
GP
5.691
0.045%0..44%
0.007s
7.773
0.529%
0.009s
COExpander [EE=p=nndor COExpander ($=1. 2OPT
AE
5.689
0.029=0.1454
0.018s
7.765
0.124
0.021s
GP
5.689
0.029=0.119%
0.030s
7.762
0.078=00.195
0.031s
COExpander (5=11,==3,,,,,,1++++++++
AE
5.689
0.018 0.059%
0.084s
7.759
1.13:0.107% %
0.091s
DIFUSC00 2OPT (Sun & Yang, 2023)
GP
5.689
0.016-00.063%
2.688s
7.761
0.067 7.067+0.15499
2.692s
(Li al., 2024)
GP
5.688
0
0,256s
7.757
0.017:1.058 %
0.265s
BQ-NCO Be---Baam------- 20PT 20PT (Drakulic et 2023)
LC
5.785
1.723=1.8376
0.239s
7,871
1.484 1.229%
0.901s
GLOP (0000 (Ye et al., al. 2024b)
D&C
5,697
0.169=0,39499
2.722s
7,817
0.783
2.969s
GP
5.691
0.051
0.00%
7.768
0..377
0.021s
COExpander (5
AE
5.689
0.020=00.136
0.023s
7,762
0.076=#02245
0.046s
COExpander (5=55 2OPT
GP
5.688
0.006::0.038%
0.031s
7.757
0.017
0.065s
COExpander (3=1,,33-+ 20PT 2OPT
AE
5.688
0,0055 0.030%
0.088s
7.757
0.044
1.180s
TSP-500
TSP-IK
METHOD
TYPE
OBI.
DROPJ
TIME.
OBI.
DROP_
TIMEL
Concorde (Applegate al., 2006)
Exact
16.546
0.000
18.672%
23.118
0.000%
84,413x
LKH (500) (Helsgaun, 2017)
Heuristies
16.546
0.002=00010%$
1.848s
23.119
0.005 1%
4.641s
GA-EAX (Nagata & Kobayashi, 2013)
Heuristies
16.546
0.001 0..0110.004%
1.857s
23.118
0.000 %
17.544s
GCN + 2OPT (Joshi et al., 2019)
GP
16.769
1.348--055999
0.063s
23.527
1.769 + 00.43%%
0.227s
DIMES + 20PT QQuu al., 2022)
GP
17.655
6.707=1.121%
0,314s
24.906
0.73510.823%
0.662s
DIFUSCO ($=1,1;=00) 2OPT (Sun & Yang. 2023)
GP
16.810
1.593:0.722%%
2.781s
23.540
1.82610.5400%
3.422s
Fast-T2T ($=====5++++++0000000 2OPT (Li al. 2024)
GP
16.696
0.907_0.573%
0.328s
23.387
1.144=0.421%
0.953s
BQ-NCO + 2OPT (Drakulic
2023)
LC
16.838
1.76620.625%
2.4546
23.647
2.287
5.722s
GL.PP GL.0P:0W
2024b)
D&C
17.196
3.932
5,796s
24.200
4.682%+0.003%
5.967s
COExpander [SS 2OPT
GP
16.750
1.283%
0.055s
23.481
1.571 10.412%
0.211s
(5F 20PT
AE
16.684
0..377-1.519%
0.070x
23.421
1,309 +0.38%%
0.273s
COExpander (S:Da:=
GP
16.690
0,869
0,102s
23.423
1.31910.887%
0.328s
COExpander (S=1.,,:])
AE
16.626
0.487 0.388%
0.242s
23.337
0.946 0.409
0.703s
DIFUSCO (S=41,50) 20P
2OP (Sun & Yang, 2023)
GP
16.697
0.917=0.375%
3,031s
23.421
1.308 0.396/
7,891s
Fast-T2T (S--1) (Li 2024)
GP
16.629
0.500=0.2839
0.469
23.289
0.740=0.2574 %
1,930s
BQ-NCO B6 (Drakulic al., 2023)
LC
1..96%
4.0168
23.513
0.366%
10.336x
GI.OP (... (Ye 2024b)
D&C
17.094
3.313--0.608%
5.836s
24.085
0..53%
6.1166
GP
T6.698
0.9207-0.50665
0.T80s
23.428
0.3
0.719%
COExpander (1= 20PT
AE
16.644
0.594=0.3411
0,219s
23.359
1.042=0.31188
0.945s
COExpander ($==, 2OPT
GP
16.627
-0.29449
0.320s
23.339
0.954 + 0..11%
1.141s
(S=,,,,33. 2OPT
AE
16.587
0.251 2251-0..11 0.193%
0.656s
23.266
0.640- 1..210%
2.430s
TSP-10K
МETHOP
TYPE
OBI.
DROP]
TIME.
1.KH (500) (Helsgaun, 2017)
Heuristies
71.755
1.000+-00005%
332,758s
(S-L.00)) + 2OPT (Sun & Yang, 2023)
GP
73.955
3.066=2.119 197%
55.438s
Fast-T2T ($=1L:5)) 2OPT (Li et al, 2024)
GP
72.900
1.595_0.086%
40.938s
GL.OP (5=1 (Ye al., 2024b)
D&C
75.902
5.780+-0.6999
11.776s
COExpander (S=1
GP"
72.982
102:0.00100
I20%&
28.3135
COExpander (5=11, 20PT
AE
72.796
1.500-00966%
29.495s
29

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Table 23. Complete results on ATSP.
ATSP-50
ATSP-100
METHOD
TYPE
OBI.
DROPJ
TIMEL
OBI.
DROPL
TIMEL
LKH (1000) (Helsgaun, 2017)
Heuristics
1,5545
0.000+0.0000%
1.5660
0.0000+0.00000S
0.238s
LKH (100) (Helsgaun, 2017)
Heuristics
1.5545
0.0007:10.1
1.5661
0.0013+0.01139
MatNet (Kwon et al., 2021)
L.C
1.5752
1.8232++1.0733
0.035s
1.6171
3.2551+1.2724
0.061s
GOAL (Drakulic et al., 2024)
1.6450
5.8473 3.089%
0.313s
1.6382
4.6066:22. 1008%
0.638s
COExpander (S=1,1)
GP
1.6623
6.94844:5 1644%
0.006s
1.6651
6.3286-+
0.008s
COExpander (S=1,D;33.1.=)
1.6367
5.3044:4. 2257%
0.019s
1.6455
5.0855#3.
0.023s
COExpander (S=1,D;=1.1,=5)
1.6019
3.0433++4. 0200%%
0.029s
1.6275
4.9351=+2.377380
0.033s
COExpander (S=1,D.=31..5))
1,5823
1,7901
%
0.086s
1.6666
6.2326:12.191233
0.099s
COExpander 20%
1.6135
3.8045
2.911
0.007s
1.6303
4,1041+-2. 2. 1430%
0.009
COExpander +
1.6014
3.0289+2.54430%
0.019s
1.6186
3.361 1.963%
0.024s
COExpander +
1.116012.2944299
1.6076
2.6648.11
66667%
0.034s
COExpander (5=1.
1.123-1186644
0.086s
1.6013
2.2576:11.56279
0.099s
MaNNet (x16) et 2021)
2011)
LC
1.5592
0,3001 0.4365%
0.037s
1.5909
1.5823-10.1 1.9233--0.74966
0.067s
GOAL 16 (Drakulic 2024)
LC
1.6277
27,551227116665
0.354s
1.6212
3,5325-t1 66100%
0.913s
(5D4,1111)) COExpander (8=1,1);=311==1)
GF
1.6541
6.44197-44.
0.008s
T.6479
5.23 926%
0.029s
1.6152
3.9176+3.4778 %
0.024s
1.6207
2.8899+2.24888
0.103<
CORxpander (5=4,1);=1111==5)
1.5620
0.4850+ 1.4123%%
0.033s
1,5946
1.8267++1.658
0.161s
COExpander (S=4,,,331.=5)
1.5587
L.2685=1002259
0.101s
1.5878
1.3929:11.4988
0.51
COExpander ( 2OPT
GP
1,6088
3.501 2. 8542%
0.009s
1.6192
3.3956:1 1,91789,
0.032s
COExpander 2
1,5890
2.2313+-2.1855 1.1566
0.025s
1.6026
2.3398 1.5522%
0.101s
COExpander +
GP
1.5583
0.2414+0.7138%
0.034s
1.5842
1.1596++1..
1.117%% 187%
0.167s
COExpander (S=4.D.=31.55)
1.5572
0.1709=0.6111%
0.101s
1.5808
0.9464:1
0.516s
ATSP-200
ATSP-500
METHOD
TYPE
OBI.J
DROPJ
TIMEL
OBI
DROPL
TIME
LKH (1000) (Helsgaun, 2017)
Heuristics
1.5647*
0.000010.00005
0.724s
1.5734
0.0000:10.00000
4,376s
LKH (100) (Helsgaun, 2017)
Heuristics
1.5647
0.001110.0056%
0.244s
1.5735
0.0010:10.0099%
1.022s
(Kwon et al., 2021)
3.8307
145.0832.48..
GOAL (Drakulic et ul., 2024)
1.6170
1.2360%
1.412s
1.7152
9.0157::1.30333
4.056s
GLOP MatNet
2024b)
D&C
2.0222
29.3824#:21 .4443%
0,1438
2.3353
1..4783:+1.550055
0.352s
COExpander (S=1.1),=11.==1)
1.6785
+2.4788%%
1.6747
6.4434++1 1.5366%
0.1276
COkxpander ($,1,1);=31,==1)
1.6284
00780+2.054.14
1,6463
4.6344++1.77
0.403s
COExpander (S=I.D.I1...=5)
1.6381
4.6773 0666%%
0.162s
1.6410
4.2941=1..63344
0.558s
COExpander (S=1,D,=3..=5)
1.6146
3.2001
0.547s
1.6228
3.1280::1.4024%
1.669s
COExpander (S=1.))=1..,:))++2
1.6524
1. 9575%
0.046s
1,6534
5.0880 1.975%
0.231s
COExpander 20PP
1.6161
3.29266+ 1,5259%
1,6299
3.5915++1.
0.478s
COExpander (S=ID:==11.:5)+20PP
1.6154
3.2517
0.168s
1.6218
3.0776:11.000 1.007%
0.648s
COExpander (S
1.6047
1.5694=1.11599
0.517s
1.6114
2.4080-1.88883
1.766s
MaNNet (x16)
2021)
3.7263
138.
402444.
0.156s
GOAL Beam-16 (Drakulic 2024)
1.6093
1.0017%
1.7012
8.1275
32.239s
COExpander (5=4,,,_111,=-))
1.66.22
6.2877.E2.000
0.087%
1.6520
4,9994511.
0.497s
COExpander (5,,..1)))).
2.7981 1.1689%
0.278s
1.6233
3.1669-10.827
COExpander (S=1,D,=1.1=55)
1.6083
2.7717 1.0595%
1.6135
2.5429+0.82899
2.144s
COkxpander (S=4,1);3311==5)
1.7904+0.95339%
1.6044
6.267s
COExpander (5=41),=11,,1
1.6407
4 8.36334--11 7.46%%%
0.1246
1,6364
4.00574+0.9356
0.9224
COExpander (S=4,D,=311,=)
2.3567 9981%
1.6148
2.6292-10. 70233%
COExpander (S=...==11===11))+2000
1.5974
2.0943= 8417%
0.391s
1.6046
1.9800=E0.61666
2.484s
COExpander (S=4,,)=331,,5))+2200
1.5882
1,5011 0.80033%
1.5981
1.5681 0-4.4667
6.597s
30

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Table 24, Complete results on individual instances from TSPLIB. "Orig.": solved tour length w.r.t the original distance of each instance.
"Norm.": : tour length calculated normalized distances for clearer comparison.
CONCORDE SOLVER
COEXPANDER
INSTANCE
Length(Orig.)
Length(Norm.))
Used Model
Length(Orig.)
Length(Norm.)
Drop
ei151
428.872
6.701
Uniform- 100
428.872
6.701
0.000%
herlin52
7544.366
4.348
Uniform-
7544.366
4.348
0.000%
st70
677.110
6,839
Uniform-100 100
677.110
6.839
0.000%
ei176
544.369
7.561
Uniform- 100
544.369
7.561
0.000%
pr76
108159.438
5.518
Uniform- 100
108159.438
5,518
0.000%
ra199
1219.244
3.671
Uniform-500
1219.244
5.671
0.000%
kroA100 100
21285,44 443
5,408
Uniform-33 500
21285.443
5,408
0.000%
kroB100 100
22139.075
5.626
Uniform-50X
22303.429
5.668
0. 0.742%
kroC100
20750.763
5,276
Uniform-35 500
20820.370
5,294
0.335%
kraD100
21294.291
5.431
Uniform-500
21294.291
5.431
0.000%
kroE100
22068.759
5,557
Uniform-50l 500
22068.759
5.557
0.000%
rd100
7910.396
8.065
Uniform-500
7910.396
0.000%
eil101
640.212
8.536
Uniform-500 500
640.212
8,536
0.000%
lin105
14382.996
4.756
Uniform-500
14382.996
4.756
0.000%
pr107
44301.68 684
3,778
Uniform-55 500
44346.18 187
3.782
0.100%
pr124
59030.736
5,009
Uniform-500
59492.914
5.048
0.783%
bier127
118293.524
6.106
Uniform-
118293.524
6.106
0.000%
ch130
61 10.722
8.751
Uniform-500
61.0.222
8.751
0.000%
pr136
96770.924
7.767
Uniform-500
27348.263
7,813
0.597%
pr144
282
4.538
Uniform-500
58620.693
4.544
0.146%
ch150 50
6530.903
9.342
Uniform-35 500
6530.903
9,342
0.000%
kroA150
26524.863
6.693
Uniform-500
26761.764
6.753
0.893%
kroB 150
26127.358
6.635
Uniform-55 500
26153.602
6.641
0.100%
pr152
131
5.234
Uniform-500
73824.720
5.244
0.191%
u159
42075.60 670
6,574
Uniform-505
42075.670
6.574
0.000%
rat195
2333.873
7.993
Uniform-500
2343.642
8.026
0.419%
d198
15808.652
3,924
Uniform-500
15885.773
3.944
0.488%
A200
29369.4 407
7.437
Uniform-500
29385.727
7,441
0.056%
kroB200
29440,412
7,467
Uniform-500
29691.071
7,530
0.851
ls22S
126645.00 934
10.554
Uniform-500
128058.222
10.672
1.115%
tsp225
3859.000
7,895
Uniform-555 500
3866.710
7,911
0.200%
pr226
80370.257
5.279
Uniform-500
80813.061
5.308
0.551%
gil262
2385.804
12.050
Uniform-500
2389.772
12.070
0.166%
pr264
49135.00 ,055
6,200
Uniform-500
49135.005
6,200
0.000%
a280
2586.777 770
9.238
Uniform-500
2586.770
9.238
0.000%
pr299
48194.92 920
6.638
Uniform-SS
48823.925
6.725
1.305%
lin318
42042.535
10.170
Uniform-500 500
42053.02 026
10.172
0.025%
rd400
15275.983 985
15.344
Uniform-500
15291.235 1.38
15.359
0.100%
f1417
11914,309
6.286
Uniform-50e
12044.736
6,354
1.095%
pr439
107215.302
8,991
Uniform-She 5500
108096.963
9.065
0.822%
pch442
50783.548
13.364
Uniform-50M
51020.753
13.427
0.467%
d493
35018,526
9.350
Uniform-500
35446.905
9,465
1.223%
us74
36934.771
12.023
Uniform-50k
37320.427
12.149
1.044%
rat575
6795.968
13.619
Uniform-500
6830.574
13.689
0.509%
p654
34646.835
7.196
Uniform-
34894.066
7.247
0.714%
d657
48915,630
12.212
Uniform- 1000
49246.478
12.294
0.676%
u724
41907.728
14.437
Uniform- 1000
42384.083
14.601
1.137%
rat783
8842.995
15.247
Uniform- 1000
8887.347
15.323
0.502%
1r1002
259066.663
16.397
Uniform- 1000
260668.540
16.498
0.618%
8.062
8.095
0.367 %
31

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Table 25. COExpander Previous SOTA: A Summarized Comparison. denotes ultra-large datasets.
PREVIOUS SOTA GUROBI
COEXPANDER
PROBLEM
DATASET
METHOD
TYPE
DROP
TIMEI
DROP]
TIMEL
MIS
RB-SMALL
Fast-T2T (Li et al., 2024)
1.700%
0.860s
1.482%
0.652s
MIS
RB-LARGE
DiffUCO (Sanokowski et al., 2024)
GP
7.944%
25.479s
3.582%
1.298s
ER-700-800
Fast-T2T (Li et al., 2024)
7.169%
1.61s
5,343%
0.703s
SATLIB
DIFUSCO (Sun & Yang, 2023)
0.200%
2.962s
0.160%
1.056s
BR-1400- 1600
Fast-TTT (I.i 2024)
25.417%
4.911%
4.516s
ER-140001610
Gurobi (60s) (Gurobi Optimization, 2023)
19.856%
4.911%
MIS
RB-GIANT
DiffUCO (Sanokowski et al., 2024)
14.352%
339.010s
5.221
14.660s
MIS'
RB-GIANT
Gurobi (60s) (Gurobi Optimization, 2023)
8.806%
56.010s
5.221
14.660s
MCI
RB-SMALL
Meta-ECC RGN (Wang
2023)
8.300%
0.434%
0.362s
RB-LARGE
Meta-RGN (Wang
2023)
0.898%
0,368s
MCI
RB-GIANT
Gurobi (60s) (Gurobi Optimization, 2023)
33.917%
60,248s
-6.424%
1.520s
MVC
RB-SMALL
Meta-BsGN (Wang
2023)
GP
1.563%
6.297s
0.290%
MVC
RB-LARGE
Meta-EGN (Wang 2023)
4.400%
1.025s
0.163%
0.5156
MVC
RB-GIANT
Gurobi (60s) (Gurobi Optimization, 2023)
0.162%
0.149%
8.200s
MCal
BA-SMALL
DifTUCO (Sanokowski al., 2024)
0.061%
0.610s
+0.043%
0,202s
MCat
BA-LARGE
DifTUCO (Samokowski al., 2024)
2.701s
MCa
BA-GIANT
DiffUCO (Sanokowski al., 2024)
-2.358%
10.760s
-2.276%
1.760s
MCar
BA-GIANT
Gurobi (60s) (Gurobi Optimization, 2023)
0.011%
61.228s
-2.276%
1.760s
TSP
TSP-50
Fast-T2T (l. al., 2024)
0.008%
0.256s
0.005%
0.088s
TSP
TSP-50
ACO (SymNCO)
al,, 2024)
0.680%
0.005%
TSP
TSP-100
Fast-T2T (Li al., 2024)
0.017%
0.265s
0.014%
0.180s
TSP
TSP-100
BQ-NCO (Drakulic
2023)
LC
1.44%%
0.901s
0.014%
0.180s
TSP
TSP-500
Fast-T2T (Li et al., 2024)
GP
0.500%
0.469s
0.251
0,656s
TSP
TSP-500
BQ-NCO (Drakulic al., 2023)
LC
1.326%
4.016s
0.251
0,656s
TSP
TSP-IK
Fast-T2T (Li et 2024)
0.740%
1.900s
0.640%
2.430s
TSP
TSP-IK
BQ-NCO (Drukulic
2023)
LC 1,707%
10.336s
0.640%
2.430s
TSP*
TSP-10K
Fast-T2T (Li et al., 2024)
GP 1,595%
40,938s
1.450%
29.495s
STSP"
ATSP-50
7 et 202T)
LC
0.3001
0.037s
O. 0.1709%
0.To
ATSP
ATSP-100
MaiNet (Kwon al., 2021)
LC
1.5823%
0.067s
0.9464%
0.516s
ATSP
ATSP-200
GOAL (Drakulic al., 2024)
LC
2. 2.8627%
4.690s
1.501 1%
1.097s
ATSP
ATSP-500
GOAL (Drakulic al., 2024)
LC
8. 8.1275%
32.239s
1.568155
6.597s
Summary of Main Results
MIS
MAIN
Global Prediction Solvers
GP
4.253%
7.816s
2.642%
0.927s
MCI
MAIN
Global Prediction Solvers
GP
11.894%
0.406s
0.666%
0.365s
MVC
MAIN
Global Prediction Solvers
GP
2.982%
0.661s
0.227%
0.301s
MCut
MAIN
Global Prediction Solvers
GP
0.856%
1.656s
-0.868%
0.283s
TSP
MAIN
Global Prediction Solvers
GP
0.316%
0.729s
0.228%
0.839s
TSP
MAIN
Local Construction Solvers
LC
1.299%
3.856s
0.228%
0.839s
ATSP
MAIN
Local Construction Solvers
LC
4.253%
7.816s
1.047%
2.078s
Average
MAIN
Previous SOTA NCO Solvers
3.807%
33.88is
0.657 %
0.799%
Summary Ultra-I Scale Results
MIS'
Large
Global Prediction Solvers
GP
19.885%
172.986s
5.066%
9,588s
MIS'
Lltre-Large
Gurobi (60s) (Gurobi Optimization, 2023)
OR
14.331%
59.076s
5.066%
9.588s
Ultr--Lage
Gurobi (60s) (Gurobi Optimization. 2023)
OR
33.917%
60.248s
-6.424%
1.520s
MVC
Ultra-Lage
Gurobi (60s) (Gurobi Optimization. 2023)
OR
0.162%
28.121s
0.149%
8.200s
Ultra-Lrrge
Global Prediction Sulvers
-2.358%
-2.276%
Ulrra-Lrre
Gurobi (60s) (Gurobi Optimization, 2023)
OR
0.011%
61.228s
-2.276%
1.760s
TSP*
Ultra- Larre
Global Prediction Salvers
1.595%
40.938s
1.450%
29.495s
32

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
H. Discussion of Limitation
H.1. Limitation of Training Methods and Generalization
COExpander currently relies on supervised learning (SL), which inevitably requires a certain amount of labeled data (details are presented in Appendix E). However, is worth noting that the traditional solvers we re- re-wrapped (Appendix D) support parallel processing CPUs. Therefore, the time required to generate each training dataset ranges from several hours tens of hours, which is an acceptable time cost.
Although we have conducted some generalization experiments across models, sizes, and distributions in Appendix G, there is still lack of generalization experiments on problems such as TSP and ATSP under other distributions (e.g.. gaussian, cluster), as well as on problems such as MIS, MCI, MVC, and MCut under other distributions (e.g., Holme& Kim (HK) (Holme & Kim, 2002), Wtrts& (WS) (Watts & Strogatz, 1998)). In future work, we will complete the experiments and analysis in this regard.
Table 26. Complete Results on CVRP.
CVRP-50
CVRP-100 -YRP-100
METHOD
TYPE
OBi.
DROP
TIMEL
OBI..
DROP]
TIME!
HGS (Vidal et al., 2012)
Heuristics
10.489*
0.000:00.000%
1.005s.
15.563*
0.000=00000%%
20.027s
RL4CO (Sym-NCO (Berto et al., 2024)
LC
10.769
3.891 6.4%%
0.087s
16.220
1.241:11.111
0.166s
RL4CO (Sym NCO) (Berto et al., 2024) + Classic-LS
LC
10.565
1,910 1 1.43%
0.091s
15.933
2.379 1.001 %
0.173s
COExpander (S=I,,,
GP
12,640
21.35=6.5335
0.009s
19.202
23.533:55.135%
0.010s
COExpander (S,1,1,,31,,11)
AE
11,979
15,407=6 898%
0.033s
17.497
12.343+455.400
0.047s
COExpander (S=I,D,=L,,=1)+++ Classic-LS
GP
10.871
4.83611...5525
0.013s
16.294
3.698:13. 1.20%
0.018s
COExpander (S=I,,,=3J,==)+ Classic-LS
AE
10.773
3.903 4-4.05%
0.037s
16.224
4.253++ 1,991 196
0.055s
CVRP-200
CVRP-500
METHOD
TYPE
08r.
DROPI
TIME!
OBI.
DROP]
TIMEI
HGS (Vidal et al. 2012)
Heuristics
19.630"
0.000
60.024s
37.154"
0.000:0.000%
360.376s
RL4CO (Sym-NCO) (Betto al., 2024)
LC
20.662
5.27410..266%
0.320s
40.382
8.723=0.8100
0.769s
RL4CO (Sym NCO) (Berto et al. 2024) Classic-
LC
20.193
1.880:0.85449
0.341s
38.700
4.173 0.660 %
0.883s
COExpander (II,
GP
25.064
27.616-5.095%
0.059s
47.749
28.509 | 2. 2.92%
0.091s
COExpander (S= (S,1,1)
AE
22.402
0.145s
43.901
18. 1991-99--28 834%
0.554s
COExpander (S=1,, + Classic-LS
GP
20.662
5,290 1.71%
0.063s
39.195
0.530=10.93795
0.215s
COExpander (S=1,, + Classic-LSS L.$
AE
20.587
4,893 1: .344%
0.153s
39.121
5.337:10.93899
0.605s
H.2. Limitation of Resolving Complex-Constraint Problems
COExpander is the result of combining AE and CM, so its scope of application is limited by its global predictor, i.g. consistency model. To our best knowledge, before our work, consistency model (Li et al., 2024) has only been applied to two combinatorial optimization problems: TSP and MIS. At present, there is no consistency model (and even from a higher level, no global prediction solvers) that can solve combinatorial optimization problems with relatively complex constraints, such as CVRP (with demand constraints).
We have attempted apply COExpander CVRP-50, CVRP-100, CVRP-200 and CVRP-500. Following GOAL (Drakulic et al., 2024) and NeuOpt-GIRE (Ma et al., 2023), the coordinates of the depot and clients were sampled from uniform distribution over the unit square, consistent with the TSP setting. The demands of clients are randomly generated integers from the interval [1, 10]. and the vehicle capacity is set to 40 / 50/ 80/ 100 for CVRP-50 to CVRP-500, respectively. During the training phase, we use HGS (Vidal et al., 2012) to generate 1, 1,280,000/ / 640,000 / 32,000 / 12,800 samples for CVRP-50 to CVRP-500, respectively, and then each model has been trained with a total of 10 training epochs. In the testing phase, for CVRP-50 and CVRP-100, consistent with NeuOpt-GIRE, each test dataset has 10,000 samples. For CVRP-200 and CVRP-500, we generated 100 samples each as the test set. The results are shown in Table 26.
From the experimental results, although the GP solver, i.g., COExpander (S=1, D,=1, I,=1) has certain advantages in speed, it is far inferior to the LC solver (we take Sym-NCO (Berto et al., 2024) as a representative of the LCC solver) in terms of effectiveness. After we apply Adaptive Expansion to the GP solver for solving CVRP (determining partial complete sub-tours in each determination process to ensure the satisfiability of constraints), the performance has been improved to some extent, but it is still not satisfactory. Furthermore, we consider introducing post-processing. Following previous work (Prins, 2004), we have implemented the local search method (Classic-LS) for CVRP, leading to great performance
33

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
improvements for solvers of the three paradigms. Of course, we believe that solving the CVRP in this manner is far from sufficient. Therefore, will discuss in detail in the next subsection the possibility of using the AE paradigm solve complex-constraint problems such as the CVRP.
H.3. Discussion on How Adaptive Expansion solves Complex-Constrain Problems
Overview. Since the AE paradigm is iterative process where the future state depends only the current state, i.e., satisfying the Markov property, it can naturally be modeled determinations on variables during the intermediate steps, which allows it to handle complex constraints through the determination process. Furthermore, inspired by LwD (Ahn et al., 2020), we plan to employ Proximal Policy Optimization (PPO, Schulman et al. (2017)) for model training, in order to better adapt to the relationship between actions and constraints, thereby extending the capability of AE methods on complex-constrained tasks. Note that a feasible scheme is theoretically described as follows, while the implementation and empirical results have obviously exceeded the scope of this paper, hence reasonably remitted to future researches.
Markov Decision Process (MDP). Also, AE makes
Modeling, An MDP is defined by A, P, R), where E S denotes state in the state space S, A represents an action in the action space A, P(s ar) is the state transition distribution, and R(s,, ax) is the reward function. Given graph data G, cost function c(.:,), -), we modeling the COPs on graph G using AE paradigm VDP(N, k) as follows:
State. Every state S can be represented as a tuple of the current partial solution x and the mask M, i.g. St == (x,
Action, An action a can be divided into two parts: selection m and assignment 2, igg. a == (m,, 22). Selection is to assign values to these decision variables.
determine which decision variables will be fixed, while assignment
Transition. Given two consecutive states St, S and the corresponding action a,, the transition P(s (t, a,) is also divided into two steps below, where V denotes" " logic or "
[
2 x]
if m² 1 if m
Update Partial Solution: x
Update Mask: Mr+1
M, V mi; Mei
Reward. We define the reward function only in the final step, i.g., R(s ax) = { -G, ift i
otherwise
Training Model with PPO. The model f(--)) takes the current state s,, graph data G as inputs, and outputs a policy distribution xg := (a(ayss, [s, G) = ftG,st). And the assignment part 2 of action a sampled from vड via Bernoulli sampling and then set the determined variables as O:
2 if 0
2t (ernoulliTTT):
0 if
The training goal is to maximize the expected cumulative reward over the episode: max Er, Eit R(s a.) 8
=
max E.,, xc-))l To achieve this objective, we use PPO algorithm, which updates the policy parameters @ by minimizing the following loss function:
T Tb 1 1- e,,,,,++e +e c, A }.
T As, clip
(()) = E, min
where Taay is the old policy before the update; e is a hyperparameter that controls the clipping range to prevent large policy updates; A, is the estimated advantage function. In PPO, A. = Q - V,, Given the discount factor y, the action-value function is defined as Q2 -- C(G, and the state-value function is defined as V2- = Eg [-c x 1
The Selection Part of Action. The selection part m of a is the core of controlling constraint satisfaction, and we need to design specifically for the particular problem. We will take CVRP as an example to illustrate how to design m.
Symmetry. The dimensions of m, z, and M can all be reshaped into n X n, where n is the number of nodes including the depot. Note that due the symmetry of the CVRP problem, needs undergo an OR operation with its transpose.
Z5.j if M.M 0,
Pre-assignment. pre-assignmmni
Treeasigmment.pp--aaiiggennn is defined as R.j
Xi.j if Ma,
34

---

COExpander: Adaptive Solution Expansion for Combinatorial Optimization
Check Constraint. To check constraint, we need first construct the vector C [0]" indicate the two constraints that need to be checked in CVRP: the node degree constraint and the vehicle capacity constraint. As for the first constraint, we check sequentially whether the degree of each node is less than equal to 2. And for the capacity constraint, we transform the adjacency matrix & into a partition matrix p, and then we sequentially check whether the sub-put containing each node satisfies the capacity constraint. The whole process can be represented as below, where dj is the normalized demand the j-th node.
C - C2
if -ー Ki. > 2rr Ej=1 Pij d2
otherwise
Actual Assignment. After checking the constraints, we determine the actual assignment 2 based on the indicator vector
0
if C; 1 And we perform the pre-assignment again, X
if Mi,j
and 2, igg. 2.
24,5
otherwise
Xi.J
if M =
{
if 2 otherwise
1 or Σj=1 Xt.j 2
Selection Part. Based on the above operations, we can naturally obtain ma.j
35


Reviews:
[{"review_id": "dfWnn8QpEh", "reviewer": "Reviewer_UKMH", "summary": "This paper introduces COExpander, a method to solve combinatorial optimization problems by diffusion models. Unlike previous neural methods, COExpander is informed by local partial solutions and iteratively improves upon them to obtain a final solution. The authors study 6 graph CO problems and demonstrate good performance in terms of speed and drop compared to SOTA neural approaches.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer UKMH,\n\nThanks for your recognition and valuable questions.\n\n>**Q1: Interpretation of \"adaptive\"**\n\n**A1:** In our work, \"adaptive\" means exactly the fact that *the number of ascertained decision variables within one round of determination is not fixed*. Specifically, it is achieved via the autonomy of the determiantion operator (see Sec.4.2), where one determination round usually ends when the greedy operator yields invalid variable assignments, so the number of decisions per round is random. Note that $D_s$, which caused your confusion, is just a maximum limit for the **rounds**. E.g., $D_s=3$ for a task with 10 variables ensures the problem gets solved within 3 rounds, but **no prior is imposed on how the quantity of decisions is distributed across those rounds** (possibly [2,3,5] or [4,3,3]). For the term \"self-\", we have unified our wording to \"adaptive\" to describe such flexibility to avoid abuse of concepts.\n\n>**Q2: Choice of $\\alpha=0.9$ in Eq.5.**\n\n**A2:** First, the model convergence and solving quality are not sensitive to $\\alpha$. Second, $\\alpha=0.9$ is preferred to ensure the model to be sufficiently (Pr=0.9) trained on cases to solve from scratch, while balancing the training diversity for solving from arbitrary intermediate states (Pr=0.1). Empirical results and detailed analysis are illustrated in the table and figures in [alpha_ablation.png](https://anonymous.4open.science/r/COExpander-ICML-Rebuttal-0246/alpha_ablation.png).\n\n>**Q3: Sinusoidal embedding layer**\n\n**A3:** **Generally**, we follow previous works (GCN4TSP,DIFUSCO,T2T,etc) to employ the sinusoidal embedding. It functions in a way similar to how position encoding works for Transformers. (Exactly as you speculated, it assigns numerical identifiers to nodes and edges for GCN.) **Specifically**, for node-tasks (e.g. MIS), the input graph contains only edge index ($E\\in R^{|\\mathcal{E}|}$), yet the (noised) solution vector pertains to nodes, i.e. $y_t\\in [0,1]^{|\\mathcal{V}|}$. Parallelly, for edge-tasks (e.g. TSP), only node coordinates ($V\\in R^{|\\mathcal{V}|\\times2}$) are provided, while the solution are on the edges, i.e. $y_t\\in [0,1]^{|\\mathcal{E}|}$. Hence, the design rationale is to make up for the lacking part of each task type, i.e. dual initial embeddings for both nodes and edges to feed GCN in either case. Formally, $h_v=S(V),h_e=S(y_t)$ for edge-tasks; $h_v=S(y_t),h_e=S(E)$ for node-tasks. We hope this explanation resolves your confusion, and we'll update our paper with clearer notations.\n\n>**Q4: $I_s$-performance drop in Fig.3**\n\n**A4**: Unlike the multi-sampling or repeated random re-solving tricks, in our case, each inference step marks distinct time points in the denoising process, and the solution vector being denoised is utilized iteratively throughout the entire process. So, a larger $I_s$ merely implies a finer-grained denoising schedule towards the final solution ($\\hat{x_0}$). Intuitively, Fig.3 showns an upward-trended solving quality as $I_s$ grows, however, **there is no hard guarantee of performance gain with greater $I_s$, esp. when $I_s$ is small (e.g. 1-5), since the inferences are sequentially linked rather than parallelly independent for \"best-picking\".**\n\n>**Q5: Applicability to VRP**\n\n**A5:** Please refer to **A3 to Reviewer zhdB**, due to the space limits.\n\n>**Q6: Claim of \"the first good global predictor for ATSP\".**\n\n**A6:** It appears to be a minor misunderstanding. GLOP is indeed a good work, though, as stated in Sec.6.2 of their paper, \"we apply MatNet50 checkpoint as our reviser without retraining\", implying that MatNet (NIPS21), a solver of the **local construction** (LC) type, was used as the backbone. Thus, it doesn't contradict our claim to be the first **global predictor** (GP) with good performance on ATSP. In any case, we've revised our paper with more careful wordings.\n\n> **Q7: Code release**\n\n**A7:** The regulations seem to emphasize that only figures are allowed in anonymous links during rebuttal. So we are more than willing to provide our code yet awaiting your confirmation that it does not violate any of the rules.\n\n> **Q8: Discussion of iSCO.**\n\n**A8:** We've noticed recent sampling methods like iSCO and RLSA(arXiv:2502.00277) and added them in our discussion of related work. Actually, they can be orthogonally performed on top of COExpander as a strong post-processor, where neural models serve to quickly yield high-quality initial solutions in aid of the infeasibility issue that sampling methods often encounter. Supplementary experiments on MIS (shown in the [rlsa.png](https://anonymous.4open.science/r/COExpander-ICML-Rebuttal-0246/rlsa.png)) validate the synergy of COExpander+RLSA.\n\n---\nHopefully our responses alleviate your concerns with satisfaction, and we stay open for any further interactions!\n\nBest regards,\n\nThe Authors", "claims_and_evidence": "The paper performs extensive experiments in several graph CO datasets and the evidence is convincing in terms of drop.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No theoretical claim is present.", "experimental_designs_or_analyses": "Yes, I checked the main text. They are overall sound, although some comparisons were not made (see below).", "relation_to_broader_scientific_literature": "The paper is related to the NCO literature on classical graph CO problems, i.e., problems on the more theoretical side with one constraint. The paper is an improvement over the previous Fast T2T method with some additional iterations for partial solution refinement.", "essential_references_not_discussed": "At least one essential reference is not discussed, iSCO [1]. This paper proposed a sampling method for solving CO problems including most of the ones studied in this paper. iSCO outperforms KaMIS: in ER [700-800], while the proposed COExpander has a more than 5% gap compared to KaMIS, meaning that COExpander should be worse than this paper.\n\n[1] Sun, H., Goshvadi, K., Nova, A., Schuurmans, D., & Dai, H. (2023, July). Revisiting sampling for combinatorial optimization. In International Conference on Machine Learning (pp. 32859-32874). PMLR", "other_strengths_and_weaknesses": "I think the paper is original overall and a good contribution to NCO. Also, the authors made several contributions on the dataset side, including fixing solvers, which is appreciated.\n\nIn terms of weaknesses:\n\n1. I believe the main limitation of this approach is the applicability to CO problems with mostly a single constraint. Similarly to other previous approaches, such as DIFUSCO, I do not see how the approach could benefit more practical problems such as vehicle routing problems and job shop scheduling.\n    \n2. This approach is supervised and requires optimal solutions $x^\\*$ unlike RL, unsupervised learning, or sampling-based approaches as iSCO. This may not be possible for more complex problems which either do not have or whose optimal solutions are hard to obtain.\n    \n3. Writing: I found some parts confusing in the flow. For example: in abstract and intro, (self-) “adaptive/adapted step-sizes” is repeated multiple times, but in the main text (Section 4) this is not clarified. I am still unsure about the meaning (see question).", "other_comments_or_suggestions": "Minor points:\n\n1. About the claim “To address this issue, we abandoned node features and adopted convolutions only on edges. To our best knowledge, this is the first global predictor with good performance for ATSP.”, GLOP (Ye et al. 2024b) already implemented such network.\n    \n2. The release code and datasets are a good contribution. However, at the moment, it is just a promise. I would invite authors to consider submitting the code through a zip file or an anonymized link in the future.", "questions_for_authors": "1. Which part does the “adaptive” in your method stand for exactly? I could not find a single answer to this, as the term is mentioned in the abstract and introduction but not in Section 4. My understanding is that this is the number of determination steps, etc, from the ablation studies, but this is not adaptive and decided a priori. Related to this, what does the \"self\" in \"self-adaptive\" stand for?\n    \n2. How did you choose the $0.9$ in equation 5?\n    \n3. What is the meaning of encoding $y_t$ with a sinusoidal embedding layer? Are the nodes numbered in any way?\n    \n4. In Figure 3, why can more inference steps worsen performance in some problems?\n    \n5. You mentioned solving more general VRPs in future works. How would that work, given that, in my understanding, in such problems the mask may change values multiple times depending on the current tour?", "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": "YXNgHhpNht", "reviewer": "Reviewer_zhdB", "summary": "This paper introduces an adaptive approach for combinatorial optimization, where solution variables are incrementally determined using a dynamically adjusted decision step-size rather than fixed-size decisions. The method integrates global prediction (GP), producing probabilities for all variables at once, and adaptively expands partial solutions in each step. The authors demonstrate the effectiveness of their approach across several benchmarks, showing clear performance gains.\n\nHowever, the core idea appears closely related to the previously introduced 'Learning What to Defer (LwD)' framework [1], which also adaptively adjusts the number of decision steps through deferred actions. To clearly establish the novelty of this paper, a direct experimental comparison against LwD is necessary. Without such comparisons, the originality of the proposed method remains uncertain. For this reason, I currently give a weak rejection and recommend that the authors provide explicit comparisons to related adaptive decision-making methods to better highlight their contribution.\n\n[1] Ahn et al., \"Learning What to Defer for Maximum Independent Sets\", ICML 2020.\n\n---\n**After Rebuttal**: I increased score because authors' rebuttal addressed my concerns.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer zhdB,\n\nWe appreciate your meticulous review and constructive advice. Below we respond to the 3 major points mentioned in your comments.\n\n> **Q1: Comparison with Lwd.**\n\n**A1:** **Firstly**, it was our oversight not to compare LwD initially. Indeed, LwD is a highly relevant counterpart within the AE paradigm employing the RL learning strategy, and it merits a more in-depth discussion in our paper for its gradual \"determination\" of decision variables. **However**, it’s important to note that while LwD focuses predominantly on problems that are \"locally decomposable\" through RL-based policy learning, our COExpander represents a significant extension. It is designed to handle a broader spectrum of tasks, spanning node-selection tasks like MIS (isolated constraints), edge-selection tasks such as TSP (simple global constraints), and even more complex CVRP (detailed in Q3). This enhanced capability is underpinned by the utilization of more advanced backbone model architectures, specifically diffusion and consistency models, in combination with SL learning. We list the results comparing LwD and COExpander in [ae_solvers.png](https://anonymous.4open.science/r/COExpander-ICML-Rebuttal-0246/ae_solvers.png).\n\n**To summarise, we are more than delighted to have incorporated your recommended work into our discussion and experimental comparisons. Our collective efforts, we believe, will contribute to a more systematic establishment of the AE paradigm in the context of NCO problem-solving.**\n\n> **Q2: Suggestions on additional related works (LCP & GFACS).**\n\n**A2:** Thanks for your suggestion. We have carefully studied the works you provided and agree that LCP introduces a reviser mechanism for refining partial solutions and GFACS provides valuable insights into advanced sampling techniques for LC solvers, which are both significant approaches in the NCO community. Therefore, we have followed your advice to cite them in our related work to enhance the paper’s connection to the broader NCO research landscape. \n\n> **Q3: Applicability to more complex problems like CVRP.**\n\n**A3:** Firstly, COExpander can be directly applied to CVRP, as presented in [cvrp.png](https://anonymous.4open.science/r/COExpander-ICML-Rebuttal-0246/cvrp.png), which is the first attempt to demonstrate applicability of heatmap-based methods on VRPs, to our knowledge. To admit, there is limitation of SL methods to tackle complex constraints. Inspired by LwD, we have theoretically conceived to extend the AE paradigm to solve complex problems like VRPs via PPO.\n\n**(i) Overview.** AE paradigm is an iterative process and satisfies the Markov property, thus can be modeled as MDP. We plan to use PPO for model training, in order to better adapt to the relationship between actions and constraints. **Note that a feasible scheme is theoretically described as follows, while the implementation and empirical results have obviously exceeded the scope of this paper, hence reasonably remitted to future researches.**\n\n**(ii) Modeling.** state $s_t:=(x_t,M_t)$; action $a_t:=(m_t,z_t)$ (selection and assignment); transition $P(s_{t+1}|s_t,a_t)$ devided to $x_{t+1}^{i} = \\begin{cases}z_t^i&\\text{if }m_t^i=1 \\\\\\ x_t^i&\\text{else }\\end{cases}$ and $M_{t+1}=M_t\\lor m_t$; reward is only defined in the final step $R(s_t,a_t) := \\begin{cases} -c(G, x_t) & \\text{if } t=k-1,\\\\\\ 0 & \\text{else} \\end{cases}$\n\n**(iii) Training Model with PPO.** Given the model $f(\\cdot, \\cdot)$, $\\pi_\\theta^t := \\pi_\\theta(a_t|s_t, G) = f(G, s_t)$. $z_t$ of $a_t$ is sampled from $\\pi_\\theta^t$ via **Bernoulli sampling** and then set the determined variables as 0. The advantage function: $\\hat{A}\\_t= -\\gamma^{k-1-t} \\cdot c(G,x_{k-1})-\\mathbb{E}\\_\\theta [ -c(G,x_{k-1} | s_t)]$.\n\n**(iv) The Selection Part of Action.** The selection part $m$ of $a$ is the core of controlling constraint satisfaction. Take CVRP as an example.\n- Reshape $m$, $z$, and $M$ to $n\\times n$, where $n$ is the number of nodes including the depot. $z$ needs to undergo an OR operation with its transpose. \n- Make pre-assignment: $\\hat{x}\\_{i,j}=\\begin{cases}z_{i,j}&\\text{if }M_{i,j}=0, \\\\\\ x_{i,j}&\\text{if }M_{i,j}=1\\end{cases}$. \n- Check Constraints: $C_i=\\begin{cases}1&\\text{if }\\sum_{j=1}^{n}\\hat{x}\\_{i, j}>2\\text{ or }\\sum_{j=1}^{n}p_{i,j}\\cdot d_j>1 \\\\\\ C_i&\\text{else}\\end{cases}$\n- Re-Assignment. $\\hat{z}\\_{i,j}=\\begin{cases}1&\\text{if }C_i=1,\\\\\\ z_{i,j}& \\text{else}\\end{cases}$; $\\hat{x}\\_{i,j} = \\begin{cases}\\hat{z}\\_{i,j}&\\text{if }M_{i,j}=0,\\\\\\ x_{i,j}&\\text{else}\\end{cases}$. \n- Selection Part. $m_{i,j}=\\begin{cases}1&\\text{if }\\hat{z}\\_{i,j}=1\\text{ or } \\sum_{j=1}^{n}\\hat{x}\\_{i,j}=2,\\\\\\ 0&\\text{else}\\end{cases}$\n\n---\nWe hope our point-by-point clarificaitons, supplementary experiments, and positive feedbacks on your requests, have satisfactorily addressed your concerns. We remain fully committed to involving further discussions with you towards an elevated evaluation of our work.\n\nBest regards,\n\nThe Authors", "claims_and_evidence": "Their claim that the GP method is not expressive enough and the LC method is not very efficient is valid. Adaptive decision-making appears to be a promising alternative that addresses these limitations.", "methods_and_evaluation_criteria": "Their evaluation criteria are reasonable and clearly justified.", "theoretical_claims": "No theory here.", "experimental_designs_or_analyses": "The experimental design is reasonable, covering several benchmarks and large-scale cases.", "relation_to_broader_scientific_literature": "This strategy is related to decision-making methods in LLMs. Adaptive decision-making could potentially be useful in that context as well.", "essential_references_not_discussed": "One critical missing reference is [1], which presents an almost identical claim and proposes an adaptive decision-making scheme that automatically stretches or shrinks decision steps using deferred actions. A direct comparison with this work is necessary, along with a clear discussion of the differences and contributions.\n\n**[1]** Ahn et al., *\"Learning What to Defer for Maximum Independent Sets,\"* ICML 2020.\n\nAdditionally, for **partial solution generation**, you may refer to prior work related to GLOP:  \n\n- Kim et al., *\"Learning Collaborative Policies to Solve NP-hard Routing Problems,\"* NeurIPS 2021 (which introduces a \"reviser\" to refine partial solutions).\n\nFor **LC solvers**, you may also include the following work in the related works section, as it extends DeepACO:  \n\n- Kim et al., *\"Ant Colony Sampling with GFlowNets for Combinatorial Optimization,\"* AISTATS 2025.", "other_strengths_and_weaknesses": "**Weaknesses:** They only verify their method on simple constrained combinatorial optimization problems. Its effectiveness on more complex constrained problems, such as CVRP, PDP, and JSSP, remains uncertain, especially since hard constraints in these problems are more naturally handled by the LC method.", "other_comments_or_suggestions": "None", "questions_for_authors": "I have one critical question: Can this type of method effectively handle hard-constrained problems? As far as I know, such methods perform well on locally decomposable problems like MIS and simple routing problems such as TSP. However, I have yet to see a non-LC method successfully solve complex routing problems, even relatively simple ones like CVRP, which involve multiple hard constraints. I would like to hear your discussion on this issue and how your algorithm might address these challenges.", "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": "p0U5CG96ta", "reviewer": "Reviewer_CvKY", "summary": "The paper proposes a learning-based approach for solving combinatorial\noptimization problems that combines global and local paradigms to achieve better\nperformance. The authors describe their method and evaluate it empirically.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer CvKY,\n\nWe appreciate your time reviewing and acknowledging the novelty and empirical efforts of our work. There appear to be several misunderstandings, chiefly concerning the claim about the \"reimplementation\" of baseline solvers and existing neural methods. We offer point-by-point clarifications below.\n\n---\n> **Q1-About paper length.**\n\n**A1:** Thank you for your concern. Admittedly, our paper has a relatively long appendix. However, we'd like to explain that: First, each part of the appendix provides supplementary support for the core idea. It includes additional related work for a broader discussion of existing NCO efforts (A), detailes of the 3 paradigms in our proposed taxonomy (B), formal problem definitions (C), introduction of our re-standardized data and re-wrapped tools (D&E), implementation details for reproduction (F), and supplementary results and analysis (G). Second, as far as we know, many works [1,2,3, etc.] have comprehensive content without their contributions being devalued by top conferences, and we've double-checked to ensure no violation of the submission rules. Thus, we believe our paper contains the necessary context to present a complete picture of our proposal, with both narrative and procedural justifications, comparable to precedents of the same tier and area.\n\n---\n> **Q2-Doubts on the claim of reimplementation.**\n> \n**A2:** Thank you for posing this significant question. **Firstly**, we sincerely apologize for any misunderstanding. In fact, we are not \"re-implementing\" the renowned solvers, rather, our work center on enhancing the usability of invoking them through more unified and efficient APIs for future research. This process is more aptly described as re-\"wrapping\"/\"encapsulating\" at the engineering level, without duplicating the underlying algorithms. Hence, the issue of “faithfulness” to the original implementations does not pertain here. Below we provide a sample code how the solvers are accessed within our framework:\n```\nsolver = MISGurobiSolver()\nsolver.from_txt(\"path/to/data\")\nsolver.solve()\n>>> (obj: xx, gt_obj: xx, gap: xx, std: xx)\n```\nWe believe our efforts enables an easy and consistent use of these solvers for future research.\n\n**Regarding the improvement of LKH**, as elucidated in Appendix D.2, it involves an in-depth exploration of the complex built-in settings of the LKH package. We found that the LKH3 package utilizes a parameter named `SPECIAL`, which by default disables the use of 2-/3-opt operators, thus compromising the solving quality on TSP. So, we empirically removed it for enhancing both performance and efficiency, and leave it an open question prompting further investigation into its internal mechanisms.\n\n**In summary**, we regret any confusion caused and hope our clarifications accurately convey the nature of this part in our work—aiming for improved convenience and potential performance gains from an engineering perspective. We'd like to reiterate our primary technical contribution: the proposal of a novel neural paradigm and framework for COPs, supported by comprehensive experiments.\n\n---\n\n> **Q3-Doubts on retraining of existing neural solvers.**\n\n**A3:** Thanks for your comments. Firstly, in the field of NCO research, it is a common and encouraged practice to retrain and re-evaluate existing methods, which facilitates a fairer comparison, as directly using results from previous works can lead to discrepancies of hardware, datasets, and testing pipelines. Retraining demands significant effort. **Regarding the data, our benchmark datasets have covered the vast majority of publicly available datasets, such as TSP(Uniform), MIS(RB-SMALL) and MIS(ER-700-800)**. In cases where consistent data is currently lacking, like for ATSP, MCl, MVC, MCut, etc., we synthesize new instances **following the same generating algorithm as previous works**. Our intention is to help establish standardized benchmarks for these problems, similar to the well-established TSP benchmark. It's worth noting that the results obtained from our retrained neural approaches generally match or even surpass those reported in the original papers (see the table below). Rest assured that we shall release the code and data as soon as the conference permits via anonymous links, in any case.\n\n|Data|Method|Ori. Gap(%)|ReImpl. Gap(%)|\n|-|-|-|-|\n|MIS-SMALL|DIFUCO|4.29|3.46|\n|MVC-SMALL|Meta-EGN|2.80|1.56|\n|MCl-SMALL|Meta-EGN|7.00|8.30|\n|MCut-SMALL|DIFUCO|0.48|0.06|\n|MCut-LARGE|DIFUCO|-0.11|-1.77|\n|TSP-100|GCN|1.39|0.26|\n|TSP-100|SYM-NCO|2.88|1.75|\n|ATSP-100|MatNet|3.24|3.26|\n\n---\n## References\n\n[1] UDC, NeurIPS 2024 (45 pages)\n\n[2] UniCO, ICLR 2025 (41 pages)\n\n[3] UCOM2, ICML 2024 (34 pages)\n\n---\nWe hope our clarifications adequately address your concerns. We'd be rather grateful if, through your meticulous reconsideration, stronger consensus could be reached on a more favorable assessment of our work. We remain positive to further discussions!\n\nBest regards,\n\nThe Authors", "claims_and_evidence": "The claim to have reimplemented a range of state-of-the-art solvers is not credible.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "n/a", "experimental_designs_or_analyses": "Yes, as far as possible based on the description provided.", "relation_to_broader_scientific_literature": "Adequate.", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "Potentially a very novel way to approach CO.", "other_comments_or_suggestions": "The approach is novel to the best of my knowledge and seems to work well in\npractice. However, the paper is too long for a conference format in my opinion\n(the appendices are 18 pages compared to 11 pages for the main paper including\nreferences).\n\nThe authors claim to have reimplemented the solvers Gurobi, KaMIS, LKH, GA-EAX,\nand Concorde -- really? Are you seriously claiming to have reimplemented all of\nthese solvers, including the closed-source Gurobi, that are the result of\ndecades of implementation efforts? How did you verify that your\nreimplementations are faithful to the originals? Appendix D seems to suggest\nthat your reimplementations are in fact faster than the originals, which would\nbe a huge advance in itself. Please clarify this important point.\n\nThis issue unfortunately casts doubt on the empirical results, in particular the\nimprovements of the proposed method over the baselines. Similar to the classical\nsolvers, the neural approaches were retrained in at least some cases, but it is\nunclear whether the training process reflects what was used to train those\napproaches originally. Thus, it is unclear to what extent improvements are due\nto the proposed approach. In addition, a custom set of benchmarks is used,\nmaking comparison with published figures difficult.", "questions_for_authors": "Please clarify what you implemented and where you used existing implementations.", "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": "uiEfVCdg8p", "reviewer": "Reviewer_F5eW", "summary": "This article proposes an Adaptive Expansion (AE) paradigm for COPs, demonstrating its advantages in a series of experiments on COP problems.\n\n## update after rebuttal\n\nThanks for your detailed response. All of my concerns are clearly resolved so I have raised my score to 4.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer F5eW,\n\nWe are more than grateful for your time and recognition of our contributions. We sincerely present our point-to-point clarification to your questions below.\n\n> **Q0-Comparing with UDC.**\n\n**A0:** First, we have cited the UDC method and explained our exclusion of further comparison in Sec.1 (line 25-26, right). Second, we provide a brief performance comparison below, showing that COExpander generally outperform UDC (reported in original paper with the *best* settings) in terms of both optimality gap and per-instance efficiency.\n|Task|Gap(UDC,%↓)|Time(UDC,s↓)|Gap(Ours,%↓)|Time(Ours,s↓)|\n|-|-|-|-|-|\n|TSP500|1.58|1.88|**0.25**|**0.66**|\n|TSP1K|1.78|3.75|**0.64**|**2.43**|\n|TSP10K|4.03|60.00|**1.45**|**29.50**|\n\n> **Q1-Sensitivity to specific strategies for determining operations.** \n\n**A1:** In fact, to mitigate the overreliance on ad-hoc designs, the decisive operators in our work are based on the simplest greedy heuristics. Take MIS for instance, as detailed in Sec. 4.2.2, we sort the predicted heatmap in descending order and sequentially (greedily) attempt to add nodes to the independent set. Once the \"independence\" constraint is breached, the process halts and the next round of model inference commences. **Thus, the version we propose can essentially be regarded as a baseline strategy, while future efforts on more complex determining operations are encouraged and may necessitate ablations against ours.** We will also explicitly address this point in the paper to prevent misunderstandings. Thanks for your question!\n\n> **Q2-Sensitivity to the mask probability in Eq(5).** \n\n**A2:** Please refer to our **response A2 to Reviewer UKMH**, where the effects of $\\alpha$ is systematically evaluated though supplementary experiments.\n\n> **Q3-Disclosure of the code implementation.** \n\n**A3:** Sure. Rest assured that the code and datasets of this work will be fully open-sourced as soon as the conference permits. At the moment, due to the regulation that \"links may only be used for figures (including tables) and captions that describe the figure (no additional text)\", we are more than willing to provide our code via anonymous links once we have your confirmation that it does not violate any of the rules.\n\n> **Q4-Explanation of model input containing optimal solution $x^{*}$.** \n\n**A4:** Recall the process of diffusion mechanism, in the training stage, $x^*$ serves as the starting point to generate the noising trajectory, i.e., $x_{0:T}=x_0,x_1,\\cdots,x_T$ where $x_0=x^*$, and the noised representation $x_T$ is fed to the model to learn the denoising mapping. At inference, the noised vector $x_T$ is generated by random Gaussian noise without ground truth label. We note the description in Line 273 slightly inaccurate and have updated it accordingly to mark the difference of model input for training and testing phases. Thank you for the critical point!\n\n> **Q5-Acquisition of $M$ in the testing phase.** \n\n**A5:** First of all, we'd clarify that the mask $M$ is a Boolean matrix with the same shape as the solution $x$. Its purpose is straightforward: to mark whether an edge or node has been determined (assigned 0 or 1). Hence, $M$ is initialized as a zero matrix (vector) at the beginning of tests, and there is no requirement for the optimal solution $x^*$. We've updated our scripts in Algorithm 1 to explicitly show the initial setting of the mask.\n\n> **Q6-Request for a simple and clear description of the method.** \n\n**A6:** In this paper, we put forward a novel paradigm for the neural decisive process, aiming to harness the strengths of both global prediction and local construction methods. Briefly, the process of determining the solution for a problem instance is adaptively divided into multiple rounds. During each round, the model generates a heatmap that forecasts the probability of each node/edge being chosen. Subsequently, the solution is greedily constructed in descending order of the heatmap values until the constraints are breached. All the selected nodes/edges are then marked as 1 and, together with the partial solution, fed back into the model to initiate a new round of inference. This cycle continues, with more nodes or edges being determined in each successive round, until every decision variable has been taken into account and assigned a value of either 0 or 1 in the final solution. The modek is trained with randomly generated intermediate states (e.g. 10 out of 50 nodes have been decided in MIS) to learn better predictions for the solving stage.\n\n---\nWe hope our explanations adequately address your concerns. We are more than willing to provide further clarifications if any question remains, while we'd be rather grateful if, through your valuable reconsideration, our technical  contributions merit an improved assessment overall.\n\nBest regards,\n\nThe Authors", "claims_and_evidence": "Generally clear and convincing.", "methods_and_evaluation_criteria": "Yes, make sense.", "theoretical_claims": "There are no theoretical claims in this paper.", "experimental_designs_or_analyses": "I notice that similar to this article, a recent D&C method, UDC, also uses GNN for initial tour construction (which does not seem entirely as described in Figure 4).  Considering that your proposed COExpander requires an optimal solution as the label, can COExpander demonstrate outstanding performance compared to UDC under a similar runtime?", "relation_to_broader_scientific_literature": "1. This article proposes an Adaptive Expansion (AE) paradigm which bridges the global prediction (GP) and local construction (LC) paradigms through the utilization of a partial state prompted solution generator.\n2. This paper presents a series of benchmarks, which is beneficial for future research.", "essential_references_not_discussed": "Generally okay.", "other_strengths_and_weaknesses": "**Strength:**\n\n1. The experimental volume and workload of this article are large, and the literature review is relatively complete\n2. COExpander can demonstrate good results\n\n**Weakness:**\n\n1. I think I have tried my best to understand, but I still cannot fully comprehend the methods proposed in this article. This article lacks a simple and clear description of the method design and intuition (e.g., what effects have been made after predicting mask and using partial construction for MIS or TSP). I will ask some of my doubts in the Question part.", "other_comments_or_suggestions": "See Questions.", "questions_for_authors": "1. Is COExpander sensitive to specific strategies for determining operations for cop, and are there any relevant ablation experiments?\n2. Is COExpander sensitive to the parameters in Eq (5), and what is the design concept of Eq (5)?\n3. Will you plan to publish the code implementation?\n\nFor Weakness1:\n\n4. In Line 273, what does it mean that the model input contains optimal solution $x^*$.\n5. In Algorithm 1, you mentioned Model Inference with M. The acquisition of M seems to require the optimal solution. How was this step implemented during testing?\n6. Can you provide a simple and clear description of the method design and introduction?", "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:

Meta-review: The authors provided an excellent rebuttal and effectively addressed the reviewers' concerns. This work combines global prediction with local construction methods to tackle various combinatorial optimization problems. While its applicability to more complex problems warrants further investigation, the authors presented preliminary results on CVRP during the rebuttal and demonstrated the potential of their approach. The more labeling effort required for supervised learning compared to reinforcement learning methods such as UDC could be better clarified in the updated version. All reviewers lean toward accepting this work.
Decision: Accept (poster)