OPTFM: A Scalable Multi-View Graph Transformer for Hierarchical Pre-Training in Combinatorial Optimization
Authors: Hao Yuan
Wenli Ouyang
Changwen Zhang
Congrui Li
Yong Sun
Venue: NeurIPS 2025 spotlight ()
Keywords: combinatorial optimization
foundation model
graph transformer
hierarchical pre-training
Primary area: optimization

Abstract: Foundation Models (FMs) have demonstrated remarkable success in fields like computer vision and natural language processing, yet their application to combinatorial optimization remains underexplored. Optimization problems, often modeled as graphs, pose unique challenges due to their diverse structures, varying distributions, and NP-hard complexity. To address these challenges, we propose OPTFM, the first graph foundation model for general combinatorial optimization. OPTFM introduces a scalable multi-view graph transformer with hybrid self-attention and cross-attention to model large-scale heterogeneous graphs in $O(N)$ time complexity while maintaining semantic consistency throughout the attention computation. A Dual-level pre-training framework integrates node-level graph reconstruction and instance-level contrastive learning, enabling robust and adaptable representations at multiple levels. Experimental results across diverse optimization tasks show that models trained on OPTFM embeddings without fine-tuning consistently outperform task-specific approaches, establishing a new benchmark for solving combinatorial optimization problems.

OPTFM: A Scalable Multi-View Graph Transformer for Hierarchical Pre-Training in Combinatorial Optimization
Hao Yuan
Wenli Ouyang"
Lenovo Research
Lenovo Research
yuanhao4@lenovo.co com
ouyangvl1@leeovo..com
Changwen Zhang Lenovo Research zhangcw5elenovo.
Congrui Li Lenovo Research 1i licr8@eenovo.com
Yong Sun
Lenovo Research
sunyong4@lenovo.com
Abstract
Foundation Models (FMs) have demonstrated remarkable success in fields like computer vision and natural language processing, yet their application to combina- torial optimization remains underexplored. Optimization problems, often modeled as graphs, pose unique challenges due to their diverse structures, varying distribu- tions, and NP-hard complexity. To address these challenges, we propose OPTEM, the first graph foundation model for general combinatorial optimization. OPTEM introduces a scalable multi-view graph transformer with hybrid self-attention and cross-attention to model large-scale heterogeneous graphs in O(N) time complex- ity while maintaining semantic consistency throughout the attention computation. A dual-level pre- rre-training framework integrates node-level graph reconstruction and instance-level contrastive learning, enabling robust and adaptable represen- tations at multiple levels. Experimental results across diverse optimization tasks show that models trained on OPTFM embeddings without fine-tuning consistently outperform task-specific approaches, establishing a new benchmark for solving combinatorial optimization problems.
Introduction
Foundation Models (FMs) [1] have achieved remarkable success in various domains such computer vision [2, 3] and natural language processing [4, 5]. By leveraging large-scale pre-training on diverse datasets, these models exhibit superior versatility and effectiveness compared task-specific, end-to- end trained models [6. 7]. The success has sparked interest in extending FMs to other areas, including graph-based tasks. where Graph Neural Networks (GNNs) [8, 9] and graph transformers [10, 11] have shown significant promise.
Meanwhile, Machine Learning for Combinatorial Optimization (ML4CO) has gained significant traction recently due to the NP-hard nature of the optimization problems. Researchers have encoded the problems as graphs, such bipartite [12] and tripartite [13] structures, and enhanced solving performance through techniques like large neighborhood search [14, 15], branching variable selection
"Corresponding author.
'Combinatorial optimization a subfield mathematical optimization that deals with problems where solution space consists of discrete configurations, and the goal is to find an optimal solution from finite (but often exponentially large) set of feasible solutions under given constraints.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

[12, 16], predicting feasible solutions [17. 18), cut selection [19, 20], and so on. However, these models are often tailored specific tasks, limiting their generalizability to real-world scenarios.
Based on these insights, there is a critical need for a general-purpose pre-training framework that can generate robust representations for variables, constraints, and entire instances in wide range of optimization scenarios. While initial attempts like Li et al. [21] have explored pre-training for optimization tasks, primarily dives into sample generation improve policy transferability across datasets in a specific problem domain, falling short of establishing a comprehensive foundation model. Developing such versatile model faces significant challenges due to the variability in problem structures, distributions, and the complexity introduced by large-scale real-world applications.
To tackle the challenges above, propose OPTFM, the first general Optimization Foundation Model. OPTEM introduces a scalable multi-view graph transformer architecture to handle large-scale optimization problems with arbitrary scale (NN time complexity. It utilizes hybrid self-attention within variables/constraintts and cross-attention between them, ensuring semantic consistency while capturing complex node-wise correlations. Building on this architecture, we design dual-Ievel pre-training framework that includes node-level graph reconstruction and instance-level contrastive learning. This hierarchical structure ensures efficient pre-training at both node and graph levels, enhancing performance across various downstream tasks.
In nutshell, this paper can be characterized by the following key highlights:
We introduce OPTEM, the first graph foundation model for general combinatorial optimization, enabling robust learning of repre- sentations for variables, constraints, and entire problem instances.
First General Optimization Foundation Model:
Efficient Multi- Attention: OPTFM features scalable multi-view graph transformer that handles large-scale problems with ((N) time complexity, capturing correlations and ensuring semantic consistency between heterogeneous nodes.
Hierarchical Pre- Training Framework: We propose dual-level pre- pre-training framework combining node-level graph reconstruction and instance-level contrastive learning, ensuring efficient and flexible pre-training.
Strong Downstream Performance: Models trained on generated embeddings from OPTFM without further fine-tuning consistently outperform end-to-ent task-specific approaches. showcasing superior performance in solving general combinatorial optimization problems across multiple downstream tasks.
2 Related work
Self-Supervised Graph Pretraining, Self-supervised pretraining allows models to learn universal representations from large unlabeled datasets, improving performance on downstream tasks [22]. These methods are typically divided into contrastive and predictive paradigms. Contrastive learning aims to train encoders such that embeddings of similar graphs are close while those of dissimilar graphs are distant. Methods like InfoGraph [23] and SCGDN [24] leverage self-contrastive strategies to learn graph-level representations. Other approaches may compare different views [25] or encoding structures [26, 27] of the same graph. Additionally, maximizing agreement between different augmentations of nodes or graphs is also common practice [28-30]. In contrast, predictive methods train encoders using self-generated labels, such as link (or motif) prediction for graph reconstruction [31, 32] and node/edge/position attribute reconstruction on masked graphs [10, 33-36). this paper, we propose dual-level pre-training framework that combines both contrastive and predictive views, along with a novel training pipeline tailored for efficient training on extremely large graphs.
Graph Transformer. Transformers have recently emerged as powerful graph encoders due to their expressive capabilities [10, 27, 37-40J. They leverage all-pair attention mechanisms aggregate information from global perspective, capturing long-range interactions and unobserved potential links. However, complexity posed a significant bottleneck. As noted by Wu et al. [41], smaller or even ultra-small versions of Graphormer [37] and GraphTrans [42] can lead to out-of oft-of-memory issues and are limited to graphs with only a few thousand nodes. To address this challenge, recent efforts tried to sample node subset [43] or group neighboring nodes [26, 44, 45] for attention, which may sacrifice expressivity. Another direction was to simplify attention mechanisms [46]. Recently, Wu et al. [41] removed the softmax function in attention computations, achieving O(N) complexity for

---

Graph-level Contrastive Learning
Vars (V
Cons
Self-attention
Nuth-veww Graph Transformet
Partitio
graphs
Moan Pooling
contrastive learning
Partitio
Self-attention
Muti-viow Graph Transforer
Cone (4)
Sub-graph sequences
Muti-view Graph Transformer
Node-level Graph Reconstruction
global constroint node
Vars
Maskked edges
Seif attention (C)
Cross- atoss-attention (V-C)
Cons
EdgesSpatial Encoding
Self (V)
Proes-attention..co
MLP
global vartable
We introduce a novel multi-view graph transformer that captures all-pair node correlations with O(N) complexity. It integrates self-attention for variables and constraints and cross-attention between them, ensuring semantic alignment. Additionally, we design hierarchical pretraining framework: the lower layer focuses subgraph reconstruction, while the upper layer leverages contrastive learning to capture global representations using embeddings from the lower layer pre-trained models.
Figure I: Overview of OPTFM:
all-pair attention without any approximation. In this paper, we propose an efficient multi-view graph transformer architecture for potentially large-scale heterogeneous graphs, aiming to capture complex node-wise correlations with semantic alignment while maintaining computational efficiency.
Machine Learning for Combinatorial Optimization. Learning to solve combinatorial optimization problems has emerged as promising research direction, where graph-based representation learning, in particular, has demonstrated superior performance across diverse tasks, including large neighbor- hood search [14, 15, 47, 48], learning to branch [12, 49, 50], learning to cut [19, 20, 51], and solution prediction [17, 18, 52-54]. However, they are designed for specific tasks or problem types, limiting their transferability. Recent efforts have explored strategies for improving generalization, such as leveraging multi-task learning to extract shared knowledge across tasks [55-57], or investigating adaptability within specific problems [58-60]. A recent attempt by Li et al. [21], although termed a 'foundation model', centers on enhancing policy transfer within specific problems by sample generation, without addressing general-purposs representation challenges. contrast, our OPTFM tends to establish general foundation model for combinatorial optimization, enabling reasonable representations of variables, constraints, and instances across problems, without any fine-tuning.
Preliminary
Combinatorial Optimization Problem. In practice, most combinatorial optimization problems can be formulated as mixed-integer linear programs (MILPs) [12], with the form
arg minf c xx/AAx= < b.1 u, Z R*-"}
(1)
where _ the objective coefficient vector, A mx the constraint coefficient matrix, E 2 the constraint right-hand-side vector. x is the decision variables of total size n. denotes the number of integer variables, and the remaining n p variables are continuous.
Bipartite Graph Representation. As introduced by Gasse et al. [12], we encode the input opti- mization problem bipartite graph G (C, V, E). where the nodes are partitioned into two sets: one for constraints C e pmxe and one for variables V gx An edge (i.j) E E connects

---

constraint node and a variable node j if the variable is involved in the constraint, i.e., As,s F 0. Detailed features are described in Table. 6 in the appendix.
Methodology
Fig. depicts the framework of OPTEM. its core is an efficient multi-view graph transformer architecture, which leverages adaptive graph partitioning, simplified attention computation mechanism and multi-view learning pipeline to capture all-pair node correlations in large-scale heterogencous graphs at ((N) time complexity. Based on this scalable architecture, we design dual-level pre-training framework: the lower level focuses on sub-graph reconstruction to learn node and edge representations, while the upper level constructs sub-graph embedding sequences and applies contrastive learning to learn robust graph-level representations. Furthermore, we introduce an efficient decoupled training pipeline tailored for this hierarchical framework, enabling stable and scalable training on potentially extremely large graphs.
4.1 Multi-view graph transformer
Graph Neural Networks (GNNs) have been widely used to model combinatorial optimization problems on graphs [12, 48, 50-54]. However, recent advancements show that graph transformers [41, 45] excel capturing long-range interactions and mitigating issues like over-smoothing [61] and over- squashing [62] in GNNs. Despite their promise, applying graph transformers to optimization problems faces two main challenges: i) ensuring computational efficiency on large-scale graphs and ii) handling heterogeneous graphs where variables and constraints come from different feature spaces, requiring distinct attention mechanisms to align semantic information across different types of nodes.
To address the efficiency issues, some researchers attempted to simplify attention computations. Wu al. [41] removed the softmax function, reducing the complexity of attention calculations to (NV). However, it completely ignores structural information during node pair attention computations, necessitating an additional GNN to collaboratively model the graph data. This separated multi-model framework may not be ideal, as it only integrates the outputs without fully incorporating graph structure information into each attention layer. To create unified graph transformer architecture that effectively combines global-view attention with local graph structures (e.g., edges) while maintaining manageable model complexity, we propose the attention backbone as Fig. 2.
Specifically, the linear attention function is defined as:
Q = fQ(Q
Q
||lل
fk(K())), K
|
V-fv(Vi0)
(2)
D diag(1 + QQKTT 1), QG =D= D-1 V V [Q(*V)
(3)
N N (N QN NV, Qo BSo( Qvl) + 31
(4)
fK. fv are all linear fera-forward lay- ers, 1 denotes the Frobenius norm, and 3 is hyper- parameter for residual link. Qo denotes the left-half com- putation results from Fig. 2 of all-pair attentions with O(N) complexity Eq. (2)-(3), following the logic from Wu et al. [41], while differing in that we directly incorpo- rate the adjacency matrix (O) E N into the attention computation. Each element of this matrix records the edge attribute if it exists, stored as sparse matrices to efficiently capture the influence of neighboring nodes on the cur- rent node at each attention layer, as computed in Eq. (4), By integrating the adjacency matrix in this manner, struc- tural information is consistently utilized throughout the attention computation. Finally, we concatenate the graph structure guidance with the all-pair node correlations, fol- lowed by a linear transformation and residual connection, to produce the updated node embeddings in Eq. (4).
where fo. fq.
Soake/Nommal owtion
Malhul
Malkuul
Nommlizzaion
Nommllizatio
k]
Linear
Quary
Kay
Edge Matii: (Sparse)
Figure Attention Backbone.

---

We clarify that our structured attention mechanism pechanism-comppriinng separate self- alff-attention and cross attention-explicilyy respects the inherent bipartite structure and semantic asymmetry of combina- torial optimization (CO) problems, without increasing computational complexity. This design can be interpreted as semantically informed decomposition of the full attention matrix, guided by the problem's is structural prior. Specifically, intra-type self-attention enables more expressive and focused representations of interactions among variables and among constraints, respectively, while cross- attention precisely captures the directional influence between variables and constraints- critical capability for maintaining feasibility in complex optimization landscapes. By embedding a strong inductive bias aligned with the bipartite nature of mixed-integer programming (MIP) formulations, our architecture enhances semantic coherence and improves generalization across problem scales and distributions, which is essential for real- wolld applicability, as validated in our experiments.
To address the challenges of heterogeneous graphs, we propose an innovative multi-view attention framework, illustrated in Fig. 1 (bottom left), which integrates self-attention within variable and constraint sets, and cross-attention between them, using the backbone structure in Fig. For self-attention, all-pair attention is performed on the isolated constraint (C) and variable (V) nodes, eliminating edge encoding and reducing complexity. Two half cross-attentions are then conducted: one with variables as Q and constraints as K and V. and vice versa. Node representations are updated as Fig. 2, leveraging the sparse adjacency matrix A as structural features. Inspired by traditional GCNs [12], the cross-attention mechanism decomposes correlations into two interleaved processes C' - and V + C, executed sequentially from the perspectives of variables and constraints, respectively. Each step refines node representations based counterpart relevance. This multi-view attention framework enhances heterogeneous graph representations without sacrificing computational efficiency, expanding all-node-pair attention semantically.
Expressivity and Scalability: Similar to Wu et al. [41], our OPTFM can scale linearly with graph sizes, supporting effi- cient training and potentially larger graphs (details in Sec. 5.5). While key distinc- tions include integrating the Graph Net- work (GN) functionality directly into the attention layer, enabling simultaneous all- pair attention and structural embedding within each layer, rather than fusing at the output stage. Additionally, we split all-pair attention into multi-view attention, captur- ing finer-grained structural information and aligning semantic details, which theoreti- cally suits bipartite graph structures better and enhances representational power, as demonstrated in Table. 1,2 and 3.
Algorithm 1 Node-level Pre- Pre-training
Input: bipartite graph set {G,li 3...3 Maximum graph size: Jrize:
Masked edge ratio: a;
Output: Pre-trained Transformer x r()) while stopping criteria not meet do for j = to do
if |GJ| >
Jaize then
Number of sub-graphs S |G,|
Brsse
Graph partition into G.), Gr.... G
for k = to S do
Add global node, mask a% edges for G); Train (0) with on G cross-entropy loss; end for
else
Add global node, mask a% edges for Gy; Train (0) on Gj with cross-entropy loss;
4.2 Dual-level pretraining task
end end for end while
Building on the proposed graph trans- former, we introduce novel dual-level sequential pre-training framework to learn robust representations for variables, constraints, and the entire graph. It can effectively handle large-scale optimization problems within acceptable computational bounds.
Node-level Graph Reconstruction. In bipartite graphs, the structural information stems from variable-constraie correlations, as there are no edges within each side the nodes. Capturing this requires accurate recognition and prediction of inter-side connections by the model. Therefore, we propose a maask-based graph reconstruction task to learn the node-level representations.
At the input stage, we perform balanced random graph partitioning that ensures the ratio of variable to constraint nodes in different subgraphs closely matching that of the original graph, with details described in Appendix. A.2. It limits the input graph sizes to no larger than predefined Gaize for memory and computational efficiency, enabling support for arbitrary-sized problems. Within each sub-graph, proportion a% of edges are randomly masked. The masked graph, along with its edge
5

---

encodings, is fed into the graph transformer to capture complex dependencies. As shown in Fig. 1, we then extract embeddings of variables and constraints, concatenate them pairwise, and predict whether variable is part of specific constraint. Labels are derived from the adjacency matrix A before masking. Cross-entropy loss is used to minimize the difference between predictions and labels, reconstructing the original graph structure.
Please note that support subsequent graph-level pre-training tasks, as shown in Fig. 1, we add two artificial global nodes in each sub-graph. These nodes connect to all non-virtual nodes on the opposite side, denoting the global variable and constraint representations.
Instance-level Contrastive Learning. While node-level pre- training effectively captures representa- tions for variables and constraints, aggregating information across sub-graphs to obtain graph-level representations remains challenging. Previous studies [8, 63, 64] have attempted unified frameworks for simultaneous alternate learning of multi-level representations. However, joint training across sub-graphs is especially difficult in large-scale optimization problems. To address this, we propose a hierarchical training pipeline that builds on the node-Ievel pre-trained network. It independently learns a mapping from sub-graph to full graph representations, ensuring efficient and scalable learning.
As shown in Fig. 1, we construct a token sequence from the global representations of sub- graphs. where each token concate- nates the global variable and constraint vec- tors. To capture correlations among sub- graphs, we use the self-attention module from Fig. 2 without additional matrix en- coding, ignoring complex inter-subgraph structures. Then mean pooling was ap- plied to obtain graph-level representations. Building on this architecture, we propose a contrastive learning- based pre- pre- training task learn discriminative representations. Specifically, for each instance, we generate M token sequences through random graph partitions. Sequences from the same instance are treated as positive pairs, while others are negative pairs. We employ Proxy AnchorLosss [65] as the loss function to ensure that embeddings of positive pairs are close, while those of negative pairs are separated, with implementation details and hlper-parameter settings adopted from Ye et al. [17].
Algorithm 2 Graph-level Pre-training
Input: Token sequences [7, = 1,,, 1,2, ...
Token sequence labels {4, = 1,2.3...44
Output: Pre-trained Transformer Tgraph (0)
// Token sequence T; is a sub-graph global vector sequence collected by pretrained (())
Let D = (T) 1,2, ..., K}.
while stopping criteria not meet do Randomly select a batch of instances De from D; Optimize 0 by minimizing ProxyAnchorl.oss;
end while
In summary, we treat different graph partition results as multiple representatives of the same instance, leveraging contrastive learning to distinguish between instances and learn comprehensive graph representations. Since it independent from the node-level pre- pre-training. the complexity determined solely by the length of the sub-graph sequences, making it possible to efficiently extract reasonable graph-level representations for extremely large problems.
Intuition behind the design. Our decoupled two-stage architecture offers significant advantages over conventional joint multi-view graph learning approaches, particularly in scalability and efficiency. By first learning node representations on small, independently sampled subgraphs, memory consumption is bounded by subgraph size rather than the full graph, enabling training on graphs with tens of millions of nodes. In the second stage, with the node encoder frozen, global structural information is distilled into a compact token sequence, upon which transformer-based contrastive learning is applied preserving expressiveness while maintaining computational tractability. This sequential design not only avoids the prohibitive memory and compute costs of end-to-end joint optimization on massive graphs, but also enables per-instance pretraining in minutes, making large-scale graph representation learning practical and accessible.
4.3 Overall training pipeline
Our hierarchical pre-training framework follows sequential pipeline, detailed in Alg. 1 and In the first stage, we perform the node-level graph reconstruction task, training individually on each graph with adaptive partitioning for extremely large graphs, which produces pre-trained model that serves as the foundation for the next phase. In the subsequent stage, using this pre-trained model, we generate multiple token (sub-graph) sequences for each instance by applying different random partitions. Each sequence is labeled with its corresponding instance. The training objective is to bring

---

Table 1: Performace downstream task I (CA & MIS (Maximize, and MVC & SC (Minimize)) )
Methods
(x
CA3(X
MIS2
MIS3
MVC2
MVC3
SC2
SC3
SCIP
11285,2
1151178
18541.5
9086.6
31451.6
491084.8
25259.6
252199.6
13593.6
137035.9
22288.5
224295.2
27419.8
276235.0
17181.2
225725.9
LIGHT-MILPOPT [18]
13825.7
137529.5
22601.5
227198.4
27268.2
272941.2
17010.0
165973.1
GOAL [56]
13415.7
I3947L.5
22301.8
223126.1
27532.6
274472.8
175014
261195.3
MTL [57]
13389.3
139842.2
22284.2
224109.5
27498.5
275612.7
17443.7
258974.6
PCe
13022.5
136988.3
22075.9
221518.5
27965.4
279978.5
17765.9
273987.5
Pretrain:SFoomer
13787.5
140512.4
22457.6
226535.8
27398.5
275539.6
17223.5
220913.8
14129.8
139863.5
22897.1
229614.9
27094.7
270123.5
16812.3
192945,4
PPPM WGNN
14275.6
140233.1
22935.4
228975.4
27118.4
269993.1
16793.5
181739.7
PPPF
14412.0
141529.7
23057_3
231528.1
26891.8
267974.5
16158.6
165972.6
Time
2000s
30000s
2000s
8000s
2000s
8000s
2000s
12000s
representations of different partition sequences (views) from the same instance closer while pushing those from different instances apart.
Experiments
5.1 Pre-training settings
Datasets: To develop a foundation model for general optimization problems, we pre-trained on the MIPLIB 2017 collection set, well-established benchmark for MIP solvers. This dataset, curated by Hans Mittelmann, comprises 1,065 instances from real-world mixed integer programs, featuring diverse sources and complexities, with variable counts ranging from 3 to 38,868, 107 and constraint counts from to 19,912, 11. To augment the training set and ensure balanced splits, we applied five random perturbations to each instance, resulting in expanded dataset D, with details described in Appendix. A.3. We divided D into 80% for training and 20% for validation, while retaining the original dataset Do as the test set for performance evaluation, provided in Appendix. A.5.
Setup and Hyperparameters: All experiments were conducted on server equipped with NVIDIA A A00 PCIE 40GB GPUs. Each instance is input as a bipartite graph, with features detailed in Appendix. A. To manage efficiency, graphs are partitioned to ensure each sub- sub-graph contains no more than Osize 20, 000 nodes empirically from Appendix. A.6. The attention uses single-layer, single-head structure as in Wu et al. [41], with a hidden vector size of 64 and residual link 3 = 0.5. Variable and constraint features pre-training, concatenated embeddings pass through a two-layer MLP (128-) >128~> with a learning rate of 0.001. In graph-level pre-training, each instance generates M 20 sequences, batched with size of 128, sampling from 10 random instances per batch to ensure sufficient positive and negative pairs for contrastive learning. All the approaches were evaluated with three different seeds, and the average performance was reported (see detailed stability analysis in Appendix A.7).
mapped to 64 dimensions before self- olff-attention. For node-level
Baselines: We compare model against two categories of baselines: pre-training models and statc-of-the-art (SOTA) end-to-end models for each downstream task. For pre-training models, compare against: SGFormer [41], main competitor matching OPTFM's hyperparameters: and GCN [12]. initially proposed for encoding optimization problems and recently widely used [47, 49, 66, 67], two up-to-date multi-task learning frameworks, GOAL [56] and MTL [57], and some degraded versions of OPTFM: OPTFM-Nocross, which replaces cross-attention with GCN; OPTFM-WGN: which removes edge matrix input and adopts structure similar to Wu et al. [41], using GCN for graph structures and averaging at the outputs; and OPTFM-Single, which removes the graph-level pre-training and uses mean pooling of sub- aub-graphs represent the instance.
5.2 Downstream task solution prediction
Predicting solution values for integer variables MILPs is challenging due to its considerably extensive range. Given that most models primarily consist of binary variables [13], it allows framing the prediction as a binary classification task. Recent studics have explored end-to-end methods [13, 17, 18, 52], but capturing implicit correlations among decision variables remains difficult. To address this, local search methods are used to post-process the predictions.
hhtps://mipliibzib.de/
7

---

Table 2: Performance Comparison on Integer Programming (IP) of the Downstream Task II.
Methods
Covering (SC)
Independent Set (MIS)
Combinatonnal
(CA)
(MC)
Gap%
P1
Gap%
PT
Gap%
(x
Gap%
Pr
SCIP
3.23
0.25
312.55
4.7
RL-LNS [14]
1.29
17623
0.07
182.3
2.36
2276
4.25
65.38
Branching [68]
183.44
3.09
CL-LNS [15]
0.92
17025
0.07
182.99
2,05
2198.5
3.03
3883.5
Fast-T2T [69]
0.13
241.72
AnySCP [70]
3.89
4981
OCc
195
18893
237.52
2507.8
8125
SGooren
1.21
17633
0.05
181.97
2.59
2622.8 8
4.29
6601
PictaunnOPTFFM-Nocco0
L.07
0.06
182.44
2.35
2337.5
4856
Pretrain
1.13
17506
0.05
181.95
2.19
2198.6
3,55
4901
Pretrain
0.93
16782
0.05
178.55
1.93
3.02
3845
Gurobi
0.75
16796
173.15
1.44
2075.4
0.62
842
Table 3: Generalization to large-scale instances using the trained policies from small problems.
Set Covering (SC2)
Maximal Independent Set (MIS2)
Combinatorial Auction (CN2)
Maximum Cut (MC2)
Mothods
GupS:
Pl
Gap%
Pl
Gap%
Pl(x10")
Gup
Pl
SCIP
4.11
14953
3:55
9542.1
17.87
12312
8.38
30039
RL-LNS [14]
1.66
13007
0.51
1524.7
4.13
5933.4
3,20
8449.6
Branching [68]
1.53
3.19
CL-LNS [15]
1.41
12914
0.41
1298.5
3.51
5621.7
2,83
7184.1
Fas-T2T [69]
0.49
1482.5
AnySCP [70]
3,51
10327
Prefainn:CC.
2403
13983
0.79
2681.9
5.15
709888
3.65
10112
PeetrainSSGoommg
1.85
13425
1772.5
6716.9
3.17
8502.7
OFtrain:OPTFM-NN
1.49
13112
0.29
1210.0
2.95
5529.3
2.33
$521.9
PP WGNN
1.66
13309
0.24
1004,8
3.58
6439.7
2.33
$539.0
OPTTa
1.03
12699
0.15
872.16
2.19
5027.3
1.95
4339.4
Ourobi
0.71
12528
0.01
495.88
3.60
3723.5
1.01
2195.6
Methods
Set Covering (SC4)
Maximal Independent Ser (MIS4)
Combinatorial
Auction (CX4)
Maxinum Cut (MC4)
GapSk
PT
Gap%
PT
Gap%
Plcx10P)
Gap
P1
15524
25275
8.71
78510
RICINS
3.73
14866
0.57
5365.1
3.52
13572
3,76
39645
Branching
3.39
14689
13349
4.21
42718
CL-LNS [15]
3.39
14325
0.45
4533.4
2.99
13025
3.29
37384
Fast-T2T [69]
0.63
5472.9
AnySCP [70]
4.29
38975
PrCtrannOOC
3.69
14895
0.92
8033.0
5.02
14789
3.98
41235
Pretrain:SGFommer
2.68
14098
0.55
5319.7
2.92
12997
3,95
41167
OFTM
1.55
13722
0.42
4937.3
2.25
12019
2.67
31397
OrrrainOPTFM--WOCC
1.70
13815
0.41
4912.9
2.19
12173
2,45
30936
OPTPM
1.09
13385
1.99
Gurbii
1.22
13793
0.04
2215.7
12.61
21939
5.38
51298
In this task, applied the node-level pre-trained model to generate variable embeddings four large-scale Integer Programming (IP) problems, and Gradient Boosting Decision Tree (GBDT) was then utilized predict feasible solutions by learning the mapping from variable embeddings to solutions. All GBDT training and testing settings follow [17] for a fair comparison, and detailed implementations, configurations, datasets and task descriptions are provided in the Appendix. A.4.1.
Baselines: In addition to the pretraining baselines listed in Sec. 5.1, we compare our performace with two up-to-date end-to-end trained baselines: GNN-GBDT [17] and LIGHT-MILPOPT [18], and open-source MILP solver, SCIP [71].
Table summarizes the objective values of solutions produced by different methods within fixed time limit, listed in the last row, consistent with [17] and [18]. Our OPTFM significantly outperforms all competing baselines, including end-to-end trained methods and multi-task learning approaches, across all datasets, illustrating the robust performance of our framework even on unseen data distributions. Comparing other pre-trained models, SGFormer clearly surpasses GCN, highlighting the necessity of transformer architectures for capturing latent correlations between unconnected nodes. Moreover, degraded versions of OPTFM, such as OPTFM--Nocron and OPTEM-W GNNN, consistently perform weaker, further underscoring the superiority of our multi-view graph transformer architecture.
5.3 Downstream task II: large neighborhood search
Large Neighborhood Search (LNS) is type of improvement heuristic designed to explore better solutions within a predefined neighborhood. Recent studies have successfully employed model-based neighborhood functions [14, 15, 47, 68), achieving significant improvements.

---

Table 4: Performance comparison on MIPLIB2017
benchmark set.
SCIP
RL-LNN
PreIrain:GCN
Prerrain:SGFormr
Pretrain:OPTFM
Gurobi
Gap% Wins
15.15
8.07
8.95
5.19
2.92 171/240
1.98
96/240
114/240
99/240
121/240
203/2400
In this task, we extend the approach from Wu et al. [14], which uses GCN to capture graph structures along with dynamic variable features and trains using Reinforcement Learning (RL). In our imple- mentation, the state redefined include only the variable embeddings generated by node-level pre-trained model and the same dynamic variable features in the baseline. We model the actions directly using a simple MLP, replacing the GCN, Apart from these differences, all other training and testing settings, including datasets, remain consistent with the baseline to ensure a fair comparison, with further details in Appendix. A.4.2.
We compare with three end-to-end trained baselines: RL-LNS [14], Branching [68]. CL-LNS [15], and open-source solver, SCIP [71]. and leading commercial solver, Gurobi on all the problems. In addition, on the Maximum Independent Set (MIS) problems and Maximum Cut (MC) problem, we also incorporated some task-specific baselines, Fast-T2T [69] and AnyCSP [70]. representing the best known neural baselines.
Baselines:
Evaluation Metric: We calculate the average primal gap [67] and Primal Integral (PI, [72]) to evaluate the overall performance. Details are described in Appendix. A.4.2.
Table. 2 and present the average primal gap and primal integral for solutions generated by different methods within a 200s time limit. Our OPTFM consistently outperforms SCIP and all learning- based upproaches, and even surpasses Gurobi on some groups. These results highlight the robust performance of OPTEM across various tasks and data distributions, underscoring its effectiveness.
To evaluate the performance real-world data, we further tested on the MIPLIB2017 benchmark set. CL-LNS and Branching do not support heterogeneous datasets, and RL-LNS was tested with active search [14]. All methods were run for 300 seconds. As shown in Table. 4, OPTFM significantly outperforms RL-LNS and other pre-trained models, demonstrating substantial potential in real-world applications. Notably, OPTFM matches or exceeds Gurobi's 's performance on 71 % of instances and produces better feasible solutions on 10% of instances.
5.4 Downstream task III: solver configuration
To evaluate the instance-level pre-trained model, we focus on the solver configuration task. MILP solvers have many tunable parameters, and default settings often yield suboptimal solutions. Brute- force optimization is time-consuming. Thus, efficiently predicting configurations for unseen problems a promising research direction. Recent work MILPTune [73] utilized deep metric learning with GCN to capture MILP similarities. At inference, new instances are projected into the learned metric space, and configurations are predicted with K-NcarestNeiighbor (KNN) in this space.
In this task, we leverage the instance-leved pre-trained model to generate instance embeddings, replacing the metric learning approach while keeping all other aspects identical to [73] for fair comparison. We evaluate the methods on three datasets from the MLACO competition:" Item Placement (ITEM), Load Balancing (LOAD)) and Anonymous (ANONY), with 100, 100, and test instances, respectively. All methods use SCIP for configuration and run for 15 minutes.
Table. 5 presents the average improvement(%) of the objective value over default SCIP and the number of instances where each method achieves the best solution (Wins). Our OPTFM consistently outperforms all the baselines, highlighting the superior instance representation power of our OPTFM. In contrast, the degraded OPTFM-Single performs significantly weaker, underscoring the necessity of the dual-level framework for capturing correlations between subgraphs.
5.5 Complexity analysis
Efficiency is the critical concern for transformer-based methods. In our implementation, theoretically, the all-pair attention mechanism has O(N) [41] complexity. By incorporating an additional edge matrix as input each attention layer and leveraging sparse matrix multiplication, the complexity for

---

Table 5; Performance comparison on Downstream Task III.
Item
Load
Anony
Method
Avg. Imp.% %
Wins
Avg.
Imp.5
Wins
Avg.
Imp. %
Wins
SCIP
MILPTune
0.40
3
0.04
3
0.27
Pretrain:GCN
0,56
3
0.04
2
0.24
Pretrain:SCForma
2.55
18
0.33
20
1.09
OPetrain:OPTPMMSSiI
0.05
2
0.29
OPTT
3.24
74
0.58
70
1.41
12
handling edges becomes approximately OEE), where E is the number of edges. Consequently. the overall computational complexity is O(N E). This ensures linear scalability with respect to graph sizes, given that typically < N We now proceed to accurately assess the complexity OPTFM.
Training Efficiency: We mainly fo- cused on the training time and mem- ory consumption, and generated a new set of 500 set covering instances [12] with controlled nodes (1,000, 2,000, 5,000, 10,000, 20,000, and 50,000), rather than utilizing the MIPLIB2017 collection set due its varying scales. For each instance group, measured the time required to train one epoch and the corresponding memory usage. Results in Fig. indicate that wansformer-based architectures exhibit higher computational complexity compared to GCN models. The results underscores the necessity of graph partitioning. As the graph size grows, both training complexity and memory usage increase almost linearly. Training on multiple graphs with millions of nodes becomes impractical without partitioning.
The par per (haz)
30
GCS SGFarazr OFTEM
Menors
Nedle 6226
10
Nixda stice
Figure 3: Training time and memory analysis.
Inference Efficiency: We evaluated all downstream tasks' performance within fixed computation time, including pre-trained models' inference times for fairness. As indicated in Table. 1-5, even with the additional complexity, transformer -aaseerrrr--aeedd models maintain consistently superior performance, demonstrating their potential for real-world applications.
6 Conclusion and discussion
This paper introduces OPTFM, the first graph foundation model for combinatorial optimization. OPTFM features two key highlights: (1) an efficient multi-view graph transformer architecture with O(N) time complexity that captures graph structure while ensuring efficient training and inference; and (2) a dual-level pre-training framework that separately yet cohesively learns node-level and instance-leved representations. Without any fine-tuning. embeddings generated from OPTFM significantly outperform oftte-of-thearr end-to-end models across diverse downstream tasks on unseen datasets, demonstrating OPTFM's substantial potential in solving general optimization problems.
Limitations and Outlook: This work represents an initial step towards foundation models for combinatorial optimization. We mainly focus on MILP in this study, which plays central role in both theoretical research and real-world applications, and has seen growing interest in learning-bane methods, as reviewed in Sec. 2. Our experiments demonstrate that general, task and dataset-agnostic foundation model is achievable, offering a flexible tool for MILP and setting a foundation for future work broader CO challenges. To make it further, our future directions will focus on designing more effective pre-trane pre-training tasks, and extending the framework wider range of combinatorial optimization problems, ultimately aiming at truly versatile foundation model.
10

---

References
[1] Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportunities and risks of foundation models. arXiv preprint arXiv:2108, 07258, 2021.
[2] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning. pages 8748 8763. PMLR, 2021.
[3] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yen Lo, et al. Segment anything. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4015-4026, 2023.
[4] Jacob Devlin Ming-Wo Chang Kenton and Lee Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of naacL-HLLT, volume 1, page Minneapolis, Minnesota, 2019.
[5] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
[6] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 13:1877-1901, 2020.
[7] Xu Han, Zhengyan Zhang, Ning Ding, Yuxian Gu, Xiao Liu, Yuqi Huo, Jiezhong Qiu, Yuan Yao, Ao Zhang, Liang Zhang, et al. Pre-trained models: Past, present and future. Al Open, 2: 225-250, 2021.
[8] Pengwei Yan, Kaisong Song. Zhuoren Jiang, Yangyang Kang, Tianqianjin Lin, Changlong Sun, and Xiaozhong Liu. Empowering dual-level graph self-supervised pretraining with motif discovery. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pages 9223 9231, 2024.
[9] Yuhao Yang, Lianghao Xia, Da Luo, Kangyi Lin, and Chao Huang. Graphpro: Graph pre- training and prompt learning for recommendation. Proceedings of the ACM on Web Confer- ence 2024, pages 3690-3699, 2024.
[10] Gengmo Zhou, Zhifeng Gao, Qiankun Ding, Hang Zheng, Hongteng Xu, Zhewei Wei, Linfeng Zhang, and Guolin Ke. Uni-mol: A universal 3d molecular representation learning framework. In The Eleventh International Conference on Learning Representations, 2023.
[11] Hao Liu, Jiarui Feng. Lecheng Kong, Ningyue Liang. Dacheng Tao, Yixin Chen, and Muhan Zhang. One for all: Towards training one graph model for all classification tasks. In The Twelfth International Conference on Learning Representations, 2024. URL https://openrevvie. net/forume 4IT2gg9...
[12] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019.
[13] Jian- Ya Ding, Chao Zhang, Lei Shen, Shengyin Li, Bing Wang, Yinghui Xu, and Le Song. Accelerating primal solution findings for mixed integer programs based on solution prediction. In Proceedings of the aaui conference on artificial intelligence, volume 34, pages 1452-1459, 2020.
[14] Yaoxin WO, Wen Song, Zhiguang Cao, and Jie Zhang. Learning large neighborhood search policy for integer programming. Advances Neural Information Processing Systems, 34: 30075-30087, 2021.

---

[15] Taoan Huang, Aaron M Ferber, Yuandong Tian, Bistra Dilkina, and Benoit Steiner. Searching large neighborhoods for integer linear programs with contrastive learning. In International Conference Machine Learning, pages 13869-13890. PMLR, 2023.
[16] Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing branch-and- search trees to learn branching policies. In AAAI, pages 3931-3939, 2021.
[17] Huigen Ye, Hua Xu, Hongyan Wang, Chengming Wang, and Yu Jiang. Gnn&ggdt-guideer fast optimizing framework for large-scale integer programming. In International Conference on PMLR, 2023.
Machine Learning, pages
[18] Huigen Ye, Hua Xu, and Hongyan Wang. Light-min rightmmllpot:: Solving large-scale mixed integer linear programs with lightweight optimizer and small-scale training dataset. In The Twelfth International Conference on Learning Representations, 2024.
[19] Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer program- ming: Learning cut. In ICML, pages 3367-9376, PMLR, 2020.
[20] Max B. Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris J. Maddison. Learning cut by looking ahead: Cutting plane selection via imitation learning, In ICML, 2022.
[21] Sirui Li, Janardhan Kulkarni, Ishai Menache, Cathy Wu, and Beibin Li. Towards foundation models for mixed integer linear programming. In The Thirteenth International Conference on Learning Representations, 2025. URL https: / /oppreeeeeerreeeeeeeeeeeeeeeeeee net/ f frrmmid 2
[22] Barret Zoph, Golnaz Ghiasi, Tsung-Y Yi Lin, Yin Cui, Hanxiao Liu, Ekin Dogus Cubuk, and Quoc Le. Rethinking pre-training and self-training. Advances in neural information processing systems, 33:3833-383 3845, 2020.
[23] Fun-Yun Sun, Jordan Hoffman, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. In International Conference on Learning Representations, 2019.
[24] Yixuan Ma and Kun Zhan. Self-contrastive graph diffusion network. In Proceedings of the 31st ACM International Conference on Multimedia, pages 3857-3865, 2023.
[25] Kavch Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International conference machine learning, pages 4116-4126. PMLR, 2020.
[26] Yundong Sun, Dongjie Zhu, Yansong Wang, Yansheng Fu, and Zhaoshuo Tian. Gtc: Gnn- transformer co-contrastive learning for self-supervised heterogencous graph representation. Neural Networks, 181: 181:106645, 2025.
[27] Jinhua Zhu, Yingce Xia, Lijun Wu, Shufang Xie, Wengang Zhou, Tao Qin, Houqiang Li, and Yan Liu. Dual-view molecular pre-training. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 3615-3627, 2023.
[28] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in neural information processing systems, 33:5812-5823, 2020.
[29] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of the web conference 2021, pages 1069-2080, 2021.
[30] Dongki Kim, Jinheon Back, and Sung Ju Hwang. Graph self-supervised learning with accurate discrepancy learning- Advances in Neural Information Processing Systems, 15:15005-14099 2022.
[31] Chun Wang, Shirui Pan, Guodong Long, Xingquan Zhu, and Jing Jiang. Mgae: Marginalized graph autoencoder for graph clustering. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pages 889-898, 2017.
12

---

[32] Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. supe-super graph transformer on large-scale molecular data. Advances in neural information processing systems, 13:1959912551, 2020.
[33] Zhenyu Hou, Yufei Hc, Yukuo Cen, Xiao Liu, Yuxiao Dong, Evgeny Kharlamov, and Jie Tang. Graphmae2: A decoding-enhanee masked self-supervised graph learner. In Proceedings of the ACM web conference 2023, pages 737-746, 2023.
[34] Haihong Zhao, Aochuan Chen, Xiangguo Sun, Hong Cheng, and Jia Li. All in one and one for all: A simple yet effective method towards cross-domain graph pretraining, In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4443 4454, 2024.
[35] Zijian Dong, Ruilin Li, Yilei Wu, Thuan Tinh Nguyen, Joanna Su Xian Chong, Fang Ji, Nathanael Ren Jie Tong. Christopher Li Hsian Chen, and Juan Helen Zhou. Brain-jepa: Brain dynamics foundation model with gradient positioning and spatiotemporal masking. NeurIPS 2024, 2024.
[36] Pengwei Yan, Kaisong Song. Zhuoren Jiang, Yangyang Kang, Tianqianjin Lin, Changlong Sun, and Xiaozhong Liu. Empowering dual-level graph self-supervvsed pretraining with motif discovery. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 9231,, 2024.
[37] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34:28877-28888. 2021.
[38] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létournaau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances Neural Information Pro- cessing Systems, 34:21618-2166 2021.
[39] Dexiong Chen, Leslie O' BrBay, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In International Conference Machine Learning, pages 3469-3489. PMLR, 2022.
[40] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35:14501-14511 2022.
[41] Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan. Simplifying and empowering transformers for large-graph representations. Advances in Neural Information Processing Systems, 36, 2024.
[42] Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, 34:13266-13279, 2021.
[43] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[44] Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Renkun Ni, C Bayan Bruss, and Tom Goldstein. Goat: A global transformer on large-scale graphs. In International Conference Machine Learning, pages 77375-17300. PMLR, 2023.
[45] Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. NAGphormer: A tokenized graph transformer for node classification in large graphs. In The Eleventh International Conference on Learning Representations, 2023. URL https: https:///opo http///pppe/eeeeeeee//ee/eeeeeee ew net. wtt.r//.w.....totraaaaaaaeeeeeee 7
[46] Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems. 35:27387-27401, 2022.
13

---

[47] Shufeng Kong, Caihua Liu, and Carla P Gomes. Ilp-former: Solving integer linear programming with sequence multi-labe learning. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024.
[48] Hao Yuan, Wenli Ouyang, Changwen Zhang, Yong Sun, Liming Gong, and Junchi Yan. Btbs-Ins: Sanarized-tightening branch and search on learning Ins policies for mip. The Thirteenth International Conference on Learning Representations, 2025.
[49] Lara Scavuzzo, Feng Chen, Didier Chételat, Maxime Gasse, Andrea Lodi, Neil Yorke- and Karen Aardal. Learning to branch with tree mdps. Advances in neural information processing systems, 35:18514-18855 18526, 2022.
[50] Changwen Zhang, Wenli Ouyang. Hao Yuan, Liming Gong, Yong Sun, Ziao Guo, Zhichen Dong, and Junchi Yan. Towards imitation learning to branch for mip: A hybrid reinforcement learning based sample augmentation approach. In The Twelfth International Conference on Learning Representations, 2024.
[51] Zhihai Wang, Xijun Li, Jie Wang, Yufei Kuang, Mingxuan Yuan, Jía Zeng. Yongdong Zhang, and Feng Wu. Learning cut selection for mixed-integer linear programming via hierarchical sequence model. In The Eleventh International Conference on Learning Representations, 2023,
[52] Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang. Ruoyu Sun, and Xiaodong Luo. A GNN-guided predict-and-search framework for mixed-integer linear programming. In The Eleventh International Conference on Learning Representations, 2023. net htt///ormmmm/ htt////oommmmmddlplpmeeaaae 1dpp...
URL
[53] Haoyang Liu, Jie Wang, Zijie Geng, Xijun Li, Yuxuan Zong, Fangzhou Zhu, Jianye HAO, and Feng Wu. Apollo-MILP: An alternating prediction-correction neural solving framework for mixed-integer linear programming. In The Thirteenth International Conference on Learning Representations, 2025. URL https: pettps://ppeneeiiee .nt/ orum? POtDPWY
[54] Zijie Geng, Jie Wang, Xijun Li, Fangzhou Zhu, Jianye HAO, Bin Li, and Feng Wu. Differen- tiable integer linear programming. In The Thirteenth International Conference on Learning Representations, 2025. URL https: /ttp///pppeeeeeeeeeeeeeeeeeeeeee nnt.ffttffeeeee wtl.:fommmmmimfiommmmmm dd=FFECUJTTCnnn.
[55] Chenguang Wang and Tianshu Yu. Efficient training of multi-task neural solver with multi- armed bandits. CoRR, abs/2305.06361, 2023. URL 0606.66361.
008/00.4850////////// 48w.0..88///... arrviv..
[56] Darko Drakulic, Sofia Michel, and Jean-Marc Andreoli. GOAL: A generalist combinatorial opti- mization agent learner. In The Thirteenth International Confereen on Learning Representations, 2025. URL https: /ppp/reveeeeeeeee/////eeee
net/foorumiid=z2zeenit
[57] Junyang Cai, Taoan Huang, and Bistra Dilkina. Multi-task representation learning for mixed integer linear programming. arXiv preprint xxXv:2441.114409, 2024.
[58] Jianan Zhou, Zhiguang Cao, Yaoxin Wu, Wen Song. Yining Ma, Jie Zhang, and Xu Chi. MVMoe: Multi-task vehicle routing solver with mixture-of-experts. In Forty-first Interna- tional Conference on Machine Learning, 2024. URL https: http://oppp/eveeeeeeee www.urvieewnne/fforeeee wwt/feernurn id Ld=1sQnneVaBp.
[59] Federico Berto, Chuanbo Hua, Nayeli Gast Zepeda, André Hottung, Niels Wouda, Leon Lan, Kevin Tierney, and Jinkyoo Park. Routefinder: Towards foundation models for vehicle routing problems. In ICML 2024 Workshop on Foundation Models in the Wild, 2024. URL httpp:://pperrevies. net/
[60] Wenzheng Pan, Hao Xiong, Jiale Ma, Wentao Zhao, Yang Li, and Junchi Yan. UniCO: On unified combinatorial optimization via problem reduction to matrix-encoded general TSP. In The Thirteenth International Conference on Learning Representations, 2025. URL https:
// //oenreview
[61] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
14

---

[62] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021. URL https:
// //openreview.
[63] Zhihan Gao, Xingjian Shi, Hao Wang. Yi Zhu, Yuyang Bernie Wang, Mu Li, and Dit- Yan Yeung. Earthformer: Exploring space-time transformers for earth system forecasting. Advances in Neural Information Processing Systems, 0-253900224000 2022.
[64] Zaixi Zhang, Qi Liu, Qingyong Hu, and Chee-Kong Lee. Hierarchical graph transformer with adaptive node sampling. Advances in Neural Information Processing Systems, 35:21171-21183, 2022.
[65] Sungyeon Kim, Dongwon Kim, Minsu Cho, and Suha Kwak. Proxy anchor loss for deep metric learning. In Proceedings of the IEEE/CVP conference on computer vision and pattern recognition, pages 3238 3247, 2020.
[66] Christopher WF Parsonson, Alexandre Laterre, and Thomas Barrett. Reinforcement learning for branch-and-bound optimisation using retrospective trajectories. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 4061-4069, 2023.
[67] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv preprint vrXiv:2012.13345 2020.
[68] Nicolas Sonnerat, Pengming Wang, Ira Ktena, Sergey Bartunov, and Vinod Nair. Learn- ing a large neighborhood search algorithm for mixed integer programs. arXiv preprint arXiv:2107.10201 2021.
[69] Yang Li, Jinpei Guo, Runzhong Wang, Hongyuan Zha, and Junchi Yan. Fast 12t: Optimization consistency speeds up diffusion-based wraining-to-testingg solving for combinatorial optimization. Advances in Neural Information Processing Systems, 37:30179-30200 2024.
[70] Jan Tönshoff, Berke Kisin, Jakob Lindner, and Martin Grohe. One model, any esp: graph neural networks as fast global search heuristics for constraint satisfaction. In Proceedings of the Thirty-Second International Joint Conference Artificial Intelligence, pages
2023.
[71] Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner Leona Gottwald, Katrin Halbig, et al. The scip optimization suite 7.0. 2020.
[72] Tobias Achterberg, Timo Berthold, and Gregor Hendel. Rounding and propagation heuristics for mixed integer programming. In Operations Research Proceeding, pages 71-76. Springer, 2012.
[73] AbdeIrahman Hosny and Sherief Reda. Automatic milp solver configuration by learning problem similarities. Annals of Operations Research, 339(1)999--936, 2024.
[74] Antoine Prouvost, Justin Dumouchelle, Lara Scavuzzo, Maxime Gasse, Didier Chételat, and Andrea Lodi. Ecole: A gym-like library for machine learning in combinatorial optimization solvers. arXiv preprint arXiv:201 I. 1.06669, 2020.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our main claims are summarized in Sec. 1. Sec, 4 and 5 provide detailed explanations and empirical evidence.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The main limitations of the work, well as future directions that might address some of these limitations, are layed out in Sec.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
16

---

Answer:
[NA]
Justification:
This is not theoretical paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We explained our settings and hyperparameters in Sec. and Appendix A.4.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
17

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The codes and data used for the experiments have been included in the supplementary materials, together with a concise user guide.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (uttps://nips.. cc/
wtt.g/ieeeeeeeeuuuiiisssssssssse cnsiiinnooilyyy for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips. //ips.cc/publii.e wwtppblcc/aaceeccccccccccccc cebolic/guidese gwwdge/ddeeeeee /eddeSSSee ssionPolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Pretraining details are summarized in Sec. 5.1, and the details for down- stream tasks are described in Sec. 5.2-5.4 and Appendix. A.4. We also provide code in the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
The paper reports the standard deviation of our OPTFM across multiple random seeds Appendix A.7, which reflects its consistency and robustness. Additionally, on several challenging and heterogeneous problem instances presented in Table and Table 5, we report the number of wins, demonstrating that OPTFM outperforms all competing basclines on the majority of instances.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
18

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The computational resources utilized in experiments are described in
Sec. 5.1, and a comprehensive complexity analysis is provided Sec. 5.5.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the htcp/pblic/Ethicsuuieeeee
NeurIPS Code of Ethics https:
Answer: [Yes]
Justification: To the best of our knowledge, our work does not pose any harmful conse- quences, in accordance with the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
19

---

Justification: Our work focuses on developing a foundation model for combinatorial op- timization problems, which is primarily foundational research and not tied to specific real-world applications or deployments. As such, we do not foresee any direct societal impacts that arise from this work when used as intended.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No such models or datasets are involved.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All the code and datasets employed in our research were sourced from open repositories and appropriately cited within our manuscript.
Guidelines:
The answer NA means that the paper does not use existing assets.
20

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We will release our code base, pre-trained model and datasets with included readme files.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This work does not involve crowdsourcing research with human subjects.
21

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM policy (https: pectps://neee /ttp///erss..//e/ee theuurpps.cc/Cooereeeeeeee for what should or should not be described.
22

---

A Technical Appendices
A.1 Bipartite graph representation
In this paper, we represent all the optimization problems as bipartite graphs [12), with the features summarized in Table. 6. To extract features from the bipartite graphs, utilize Ecole [74], library of Extensible Combinatorial Optimization Learning Environments. Note that we retain only those features related the static structure of the problem.
Table 6: Description of the bipartite graph features.
Tensor
Feature Description
variable type (binary, integer, continuous).
objective coefficient.
lower and upper bound.
reduced cost.
cosine similarity with objective. bias value, normalized with constraint coefficients
C
V-C
constraint coefficient per variable.
A.2 Graph partition
Both [41] and [46] employed random mini-batch partitioning approach to deal with extremely large- scale graphs. However, in the context solving combinatorial optimization problems represented by bipartite graphs, completely random partitioning may lead to highly imbalanced distributions of variable and constraint nodes. This imbalance can result sub-graphs that significantly deviate from the original graph structure.
To address this issue, we extend the random partitioning approach by ensuring that connections between variable and constraint nodes are preserved much as possible while balancing the number of variables and constraints across different sub-graphs. The details are outlined in Alg. 3. Specifically, it takes input the variables, constraints, and edges of the problem that need to be partitioned. Under constraint maximum subgraph size Jeizer it outputs set of node collections P, in which each element represents the node set of sub-graph, including both variable and constraint nodes, which can still characterized as a bipartite graph.
Algorithm 3 Adaptive Random Graph Partition
Input: Variable node set = f 2 n}
Constraint node set C {c/i 1, 1,,,3...,m.
Edge set between variables and constraints: E
E E vi n.j $ m):
Maximum sub-graph size Jsizei
Output: Partitioned Node set P;
|V++C|
Number of partitions
Seine
Random partition V into S disjoint set V1, 1/,,.., Vss PI, .2...., Ps- V/1 Ve,..,, Vs for i = to S do
Select nodes from C that have edges connected to V,, denoted as C,; if IC.l 2 Jaize - VV then
Random select (gsize VVD nodes from C., denoted as C;; (C.) C.remove C.)
else
random select (gsize
|V| - |Ca)) nodes from C - C.. denoted as C,; (..add(C, + C.), C.remove C. + C.)
end if end for
23

---

A.3 Data for pre-training
In the main text, we briefly introduced the sources the pre-training data. In addition utilizing the MIPLIB2017 collection set with 1065 instances, we further performed five random perturbations on each instance to augment the dataset and ensure balanced splits for the training. validation, and test sets. Specifically, for each instance, we randomly deleted some variables and constraints, and modified coefficients and RHS values to generate modified problem, with details described in Alg. 4:
Algorithm 4 Pipeline to generate modified problem
Input: Original problem;
Output: Modified problem in .mps format;
Randomize modification ratios: changeColRatio (00,0.01), changeRow Rato (0, 0.01)
Initialize lists: LileteComsList + [.. arssiteVasLList f- for each constraint in problem.ccnnsrraiie do
r ~ 1),
if < changeRou Row Ratio then
Add constraint to deleteConsList
end if
end for
for each variable in problem.variables do
r r 1)
if changeCol Rotio then
Add variable to deleteV V ars
end if
for each coefficient in variable.cocfffciient do
r ~~ U()
ifr < &changeCol Ratio then
Random adjust the coefficient end if end for end for
for each RHS problem. SH
r 10, RhangeRRoWaate then
Random adjust the RHS value end if end for
delete the constraints and variables deleteConsList, deleteV LisList Write the modified MPS file from the modified data Test the generated MPS with MILP solver.
A.4 Implementation details for downstream tasks
A.4.1 Downstream task solution prediction
The goal the solution prediction task is to predict feasible or even optimal values for the variables in combinatorial optimization problem. This approach offers the potential to directly obtain high-quality feasible solutions based on the prediction results. Even if the predictions do not satisfy all constraints, they serve starting point for further refinement through simple neighborhood search methods. Recent studies [13, 17, 18, 52] have predominantly adopted the "predict-then then-optimize"" paradigm, leveraging machine learning models generate initial predictions that are subsequently refined to ensure all problem constraints are met.
Task Description:
Experimental Setup: In our experiments, we primarily draw upon the approach described in [17]. Specifically, their method first employed multi-task GCN to learn embeddings for variables, minimizing the distance between variables with the same values in the optimal solution while

---

maximizing the distance for those with different values. Following this embedding phase, GBDT is used to predict the optimal solution based on the generated embeddings. In the post-processing stage. the predictions are refined through a neighborhood search using SCIP, which solves constrained sub-problems within specified neighhorhood size to iteratively improve the solution quality.
In our implementation. We replace the multi-task GCN learning for generating variable embeddings with our node-level pre-trained model. In other words, the embedding generation does not utilize any solution information, thus diverging from the end-to-end training approach. The GBDT training and post-processing stages, including the repair mechanism and neighborhood search using SCIP, remain consistent with [17], allowing us to isolate and evaluate our model's ability to capture problem structure without relying on tpsk-ipe training data.
In terms of hyperparameters, we limit the neighborhood size to 30% of the original problem scale during the post-processing stage, ensuring balance between search complexity and computational feasibility. All other hyperparameters are kept identical to those in [17] to ensure a fair comparison.
Multi-task Learning Based Competing Baselines: We compared our OPTFM against two multi- task learning approaches [56, 57], using their open-sourced code with datasct-specific fine-tuning. Our focus was on the solution prediction task, consistent with their original implementations. The comparison results presented in Table show that our OPTFM significantly outperforms these baselines, further demonstrating its robust performance. It is worth noting that we did not include comparison with Li et al. [21], as it employs different model structures for different tasks and has not been evaluated on the same tasks as ours, making fair comparison challenging.
Dataset: To evaluate the performance across different approaches, we utilize four unseen large- NP-hard benchmark Integer Programs (IPs) that do not appear in the pre-training data: Combinatorial Auction (CA), Maximum Independent Set (MIS), Minimum Vertex Covering (MVC), and Set Covering (SC). For each dataset, we generate instances at three different scales, with 50 instances per scale (e.g., CAI, CA2, CA3). The smallest set of instances, such as CAI, is used to train the GBDT. Labels for these training instances are obtained by solving them using SCIP for a two-hour time limit. This setup ensures that the labels represent high-quality solutions while maintaining computational feasibility. The specific scales for each dataset are detailed in Table. 7.
Table 7: Description of the problem sizes on downstream task I
Problem
Scale
Number of Variables
Number of constraints
CA1
1000
1000
CA(Maxinize)
CA2
100000
100000
CA3
1000000
1000000
MIST
1000
3000
MIS(Maximize)
MIS2
100000
300000
MIS3
1000000
3000000
MVCI
1000
3000
MVC(Minimize)
MVC2
100000
300000
MVC3
1000000
3000000
SCT
2000
2000
SC(Minimize)
SC2
200000
200000
SC3
2000000
2000000
A.4.2 Downstream task II: large neighborhood search
Task Description: Unlike the previous task, the goal of Large Neighborhood Search (LNS) is to enhance the quality of an initial feasible solution through iterative neighborhood exploration, aiming to rapidly obtain high-quality solutions, which is crucial in many real-world scenarios where the efficiency of finding such solutions is strictly required. In this respect, learning- methods primarily assist in selecting neighborhoods, determining which variables to explore further and which to fix at their current values at each iteration [14, 15, 47, 68).
Experimental Setup: In this task, our experimental setup draws inspiration from [14], which models the neighborhood selection at each step as a Markov Decision Process (MDP), defined as follows:
State: = (Vstatic, Vaynamics C, E), encompassing static variable features derived from structural information, dynamic variable features based on solution values and their statistical characteristics at each step, static constraints, and edge features.
25

---

Action: A binary action for each variable, determining whether to fix the variable at its current value or re-optimize it the next iteration.
Transition: Execution of the current action involves invoking the solver to resolve the new subproblem, leading to the next state with updated dynamic variable features.
Reward: Objective improvement at each step
In general, [14] employs GCN to model the states and generate action outputs, training the model via reinforcement learning. Building on this, we redefine the state at each step to include only the variable embeddings generated by our node-level pre-trained model, concatenated with the dynamic variable features. We model actions directly using an MLP, capturing graph structure information entirely through pre-trained model rather than end-to-end training. It allows us evaluate the effectiveness of our pre-trained model in guiding the neighborhood selection process.
All other aspects of training and inference, including hyperparameter choices, remain consistent with [14] to ensure a fair comparison.
Dataset:
We generate instances four different benchmark IP problems: Set Covering (SC), Maximum Independent Set (MIS), Combinatorial Auction (CA), Maximum Cut (MC), with the same procedure in [14]. For each problem, we generate 100 training, 20 validation, and 50 testing instances. Additionally, we double and quadruple the number of variables to create 50 larger and even larger instances for each problem, respectively, verifying generalization performance. Instance groups and their average sizes are summarized Table. 8, also evaluated on the MIPLIB2017 benchmark set to evaluate the performance real-world problems, which are described in the main text.
Table Average variable/constraints of instances
Training
Generalization
SC
MIS
CA
MC
SC2
MIS2
CA2
MC2
SC4
MIS4
CA4
MC4
Variahles
1000
1500
4000
2975
2000
3000
8000
5975
4000
6000
16000
11975
Constraints
5000
5939
2674
4950
5000
11933
5344
9950
5000
23905
10717
19950
Evaluation Metric:
We calculate the average primal gap [67] measure the gap between the current solution x and the best-known solution x", within a fixed time limit To:
c x; c. x;"1
gap
(5)
[cc x1 c x
We also calculate average Primal Integral (PI, [72]) to evaluate the anytime performance:
1 N
To JT
PT
Σ
c xidt Toc x;
(6)
where xf denotes the best solution within / for instance i.
A.5 Pre-training performance analysis
In this section, we provide detailed analysis of the performance of the node-level pre-trrined model on the test set. As described in the main text, our model was trained and validated on synthetic data, while testing was conducted the original MIPLIB2017 collection set. For evaluation, adopted the Fl score as our metric, which is particularly effective for scenarios with imbalanced class distributions.
Fig. 4(left) illustrates the performance of three pre-training proposed OPTFM-on the test set across each training epoch. Our OPTFM, leveraging multi-view graph transformer architecture, demonstrates superior capability in capturing intrinsic structures within bipartite graphs, resulting in enhanced training outcomes compared to its counterparts.
SGFORMER, and our
Concurrently, Fig. 4(right) presents the probability distribution of Fl scores achieved by our OPTFM on individual instances within the test set. It reveals that the majority of instances achieve an F1 score exceeding 0.7, underscoring effective structure capture. Nevertheless, a small number of test cases exhibit lower performance, with Fl scores below 0.5. Addressing these underperforming cases represents a critical future research direction to potentially bolster the representational efficayy of our pre-training framework in real-world applications.
26

---

6CN St
Aroige 20me
0.3
Traning
Figure 4: Left: Average testing accuracy among different methods on the test set. Right: Per-
instance performance of our OPTFM.
A.6 Influence of hyperparameters
A.6.1 Maximum sub-graph sizes
Considering training efficiency and memory usage, graph partitioning is essential for training on extremely large graphs. However, intuitively, each subgraph may fail to capture the full information of the original graph, and increasing the number of partitions could potentially degrade the performance of pre-trre pre-training models. To investigate this, we conducted detailed analysis by liriiting the maximum subgraph size Jsise 1000, 2000, 5000, 10000, 20000, 30000, and 50000 nodes, respectively. For each setting, we trained the model and selected the one with the best performance on the validation set evaluate performance on the test set using the FI score the metric. The results are presented in Fig. 5.
The results indicate that when Jsize is less than 10, 000, increasing the subgraph size significantly improves the average Fl score on the test set. This suggests that overly fine-grained partitioning can severely disrupt the structural features of the original graph. However, the subgraph size increases beyond 20,000 nodes, the impact on model performance becomes minimal. Therefore, balancing training complexity and performance, we opted for Jsise of 20, 000 throughout this study.
60-
01
Figure 5: Influence of the Maximum sub-graph sizes on the test set with OPTFM.
A.6.2 Different training epochs
We previously evaluated the performance the node-level pre-trained models different training epochs on the test set, specifically for the graph reconstruction task. This raises the question: is the performance on the pre-training task directly correlated with performance on downstream tasks? To investigate this, we conducted detailed experiment using pre-trained models from epochs 1,3, 5, 8, 10, 12, 15, 18, 20, and These models were evaluated on the downstream task II, large neighborhood search (LNS), using the Maximum Cut (MC) dataset. Specifically, performed
27

---

RL-based training with these models and assessed their performance on the test set using the Gap% metric. The results are shown Fig. 6.
The findings indicate a clear correlation between pre-training performance and downstream task performance. Generally, better pre-training performance corresponds to enhanced representation capabilities and improved downstream task outcomes. This underscores the effectiveness of the pre-training task in extracting meaningful node-level representations, which contribute superior performance in downstream applications.
Figure 6: Performance of our OPTEM on different training epoch.
A.7 Stability analysis
To make fair comparison between different competing approaches, all the experiments in Sec. 5 were conducted with three different seeds and the average performance was reported in Table. 1-Table. The average standard deviations for our proposed OPTEM different problems gathered in Table. 9. As can be seen, it is fairly robust to different seeds, with average standard deviations lower than 3% even on hard and heterogeneous problems, like the MIPLIB2017 benchmark set, illustrating its reliable and competitive performance.
Table 9: Standard deviations across different downstream tasks and datasets of our OPTEM
Task
Standard Deviation on Each Dataset
CA2
MIS2
MVC2
SC2
Solution Prediction (Obj value Std.)
2.35%
1.97%
2.73%
0.88%
CA3
MIS3
MVC3
SC3
1.88%
2.21%
1.55%
1.82%
SC
MIS
CA
MC
2.56%
2.33%
2.88%
1.39%
Large Neighborhood Search (Gap Std.)
SC2
MIS2
CA2
MC2
2.11 1%
1.99%
2.09%
1.31%
SC4
MIS4
CA4
MC4
2.56%
1.63%
1.97%
1.88&
The whole MIPLIB2017 benchmark set
2.89%
Solver Configuration (Avg. Imp. Std.)
Item
Load
Anony
2.89%
2.01 %
3.05%
28


Reviews:
[{"review_id": "Ka69ZqUShI", "reviewer": "Reviewer_Ww5t", "summary": "The paper proposes a foundation model for combinatorial optimization with a focus on mixed integer programming. Specifically, the model is trained on the factor (bipartite) graph representation of MIPs. The paper uses a novel efficient transformer architecture. The pretraining has two phases. In the first, the graph is partitioned into subgraphs and the model learns to predict which constraints each variable is connected to. In the second, the model is trained in contrastive fashion to distinguish between pairs of subgraphs that belong to the same instance vs pairs that belong to different instances. Finally, once the variables have been embedded those embeddings are used for several different downstream tasks. The method shows strong empirical results on solving combinatorial optimization instances and on solver configuration tasks.", "questions": "see above", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n- The method is tested on several combinatorial problems and the performance is solid across the board.\n- Ablated versions of the model are included in the tables.\n- Based on the complexity analysis the scalability of the approach looks promising.\n\n## Weaknesses\n- I would've preferred if there was also a more targeted experimental comparison on one problem against the best known neural baselines. For example comparisons on maximum independent set against fast t2t [1] or maxcut comparisons against state of the art RL algorithms [2]. \n Alternatively, for problems like independenent set you can look at LWD and t2t or for problems like maxcut you could compare to strong RL methods like anycsp. I think seeing how far those learned representations can go when combined with RL would be interesting.\n- I think it would be useful to include a greedy algorithm baseline in the table to give a sense for how strong the results are compared to a simple efficient algorithm.\n- I would've liked to see on a given problem how the performance will vary if you also vary the data distribution for a given problem. So for example in the maxcut problem, it would be interesting to see results on the GSET benchmark instances or on several other datasets (see e.g., table 3,4, etc. on [3].\n\nOverall, this looks like an interesting direction for a general foundation model for CO and the experiments look promising(modulo some of the issues I brought up). I lean towards accepting this.\n\n1. Li, Yang, et al. \"Fast t2t: Optimization consistency speeds up diffusion-based training-to-testing solving for combinatorial optimization.\" Advances in Neural Information Processing Systems 37 (2024): 30179-30206.\n2. Tönshoff, Jan, et al. \"One model, any CSP: graph neural networks as fast global search heuristics for constraint satisfaction.\" Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence. 2023.\n3. Yau, Morris, et al. \"Are graph neural networks optimal approximation algorithms?.\" Advances in Neural Information Processing Systems 37 (2024): 73124-73181.", "was_revised": true, "final_justification": "After the additional results provided  by the authors, the empirical contribution appears quite strong. The results for max-cut are state of the art and it's the first transformer model I've seen that achieve this kind of performance.", "rebuttal": "Thank you for your constructive and insightful review. We sincerely appreciate the time and effort you have invested in providing detailed and thoughtful feedback on our manuscript.\n\nIn response to your valuable suggestions regarding the experimental evaluation, we have included some additional results in this rebuttal due to time constraints. We will try to incorporate the suggested baselines and benchmark tests in the final version of the paper to provide a more comprehensive evaluation.\n\n\n> **Q1**: I would've preferred if there were also a more targeted experimental comparison on one problem against the best known neural baselines. For example, comparisons on maximum independent set against fast t2t [1] or maxcut comparisons against state-of-the-art RL algorithms [2]. I think seeing how far those learned representations can go when combined with RL would be interesting.\n\n\nWe sincerely appreciate your valuable and constructive feedback. We agree that including comparisons with state-of-the-art, problem-specific algorithms would further highlight the strengths of our proposed framework. Given the time constraints of the rebuttal period, we have conducted additional experiments on the two representative problems you suggested — Maximum Independent Set (MIS) and MaxCut — comparing our method against Fast T2T [1] and AnyCSP [2], respectively.\n\nFor Fast T2T, we trained the model using the publicly available code on the same training set as in Table 2 and 3. To better match the original setup, we further expanded the training set (by generating additional instances using the same setup) to $5000$ instances. The training procedure was kept identical to the original implementation. We evaluated on the same test sets as in the main paper. Since the $T_s$ and $T_g$ parameters in Fast T2T can not precisely control the actual execution time, we selected the parameters with the closest time from 200s to ensure a fair comparison. The results are summarized below:\n\n#### **Maximum Independent Set (MIS)**\n\n|| Gap (%) | Average Time (s) |\n|:--:|:--:|:--:|\n| Fast T2T ($T_s=2, T_g=3$) | 0.13    | 175.4 |\n| Fast T2T ($T_s=3, T_g=3$) | 0.11    | 246.7 |\n| OPTFM (Ours) | **0.05** | 200 |\n\n#### **Maximum Independent Set (MIS2)**\n\n| | Gap (%) | Average Time (s) |\n|:-------------------:|:-------:|:----------------:|\n| Fast T2T ($T_s=1, T_g=1$) | 0.49    | 203.4            |\n| Fast T2T ($T_s=2, T_g=2$) | 0.36    | 238.5            |\n| OPTFM (Ours)        | **0.15** | 200                |\n\n#### **Maximum Independent Set (MIS4)**\n\n|                     | Gap (%) | Average Time (s) |\n|:-------------------:|:-------:|:----------------:|\n| Fast T2T ($T_s=1, T_g=1$) | 0.63    | 253.5            |\n| Fast T2T ($T_s=2, T_g=2$) | 0.45    | 292.9            |\n| OPTFM (Ours)        | **0.04** | 200                |\n\nAs shown, OPTFM consistently outperforms Fast T2T across different problem scales, even when the latter is specifically designed for MIS. Notably, the performance gap widens as the problem size increases.\n\nFor AnyCSP [2], we followed the training and evaluation procedures exactly as described in the original paper, using the same training set as in Table 2 and 3. We used the hyperparameters recommended by the authors without further tuning. During inference, we limited the solving time to 200s and evaluated under the same hardware and software configuration as OPTFM. The results are as follows:\n\n#### **Maximum Cut (MC)**\n\n||Gap (%)| Primal Integral (PI) |\n|:--:|:--:|:--:|\n|AnyCSP| 3.89    | 4981|\n|OPTFM (Ours)| **3.02**| **3845**|\n\n#### **Maximum Cut (MC2)**\n\n|| Gap (%) | Primal Integral (PI) |\n|:--:|:--:|:--:|\n| AnyCSP| 3.51| 10327 |\n| OPTFM (Ours)| **1.95**| **4339.4** |\n\n#### **Maximum Cut (MC4)**\n\n|| Gap (%) | Primal Integral (PI) |\n|:--:|:--:|:--:|\n| AnyCSP      | 4.29    | 38975 |\n| OPTFM (Ours)| **1.99**| **25213** |\n\nThese results demonstrate that OPTFM consistently outperforms AnyCSP, further validating its effectiveness as a general foundation representation model for combinatorial optimization. The performance advantage is particularly evident on larger problem instances.\n\nIn addition, we agree that exploring how far the learned representations can go when combined with RL is highly valuable.  Indeed, in Downstream Task II, we have already evaluated such integration: as shown in Table 2 and Table 3, our learned embeddings achieve even better performance than end-to-end GNN-based modeling.  This suggests strong potential for use in RL frameworks.  In fact, models like AnySCP could potentially replace their GNN encoder with our more general and structurally expressive representations.  We plan to explore such combinations in future work to highlight further the utility and transferability of our learned graph representations.  Thank you again for this inspiring suggestion.\n\n\n\n> **Q2**: I think it would be useful to include a greedy algorithm baseline in the table to give a sense for how strong the results are compared to a simple but efficient algorithm.\n\n\nWe sincerely appreciate your insightful suggestion. To address this, we have implemented a standard greedy algorithm for MaxCut based on the setup in AnyCSP [2], and report the comparison results on our datasets as follows:\n\n\n| Dataset | Greedy Algorithm (Gap%) | OPTFM (Gap%) |\n|:-------:|:-----------------------:|:------------:|\n| MC | 15.25 | **3.02**     |\n| MC2 | 17.33 | **1.95**     |\n| MC4 | 12.08 | **1.99**     |\n\nAs shown in the results, OPTFM significantly outperforms the classical greedy algorithm in solution quality on different Maxcut problems. We agree that comparisons with greedy baselines on other combinatorial problems would be insightful, and we will include them in the final version to further enrich the evaluation.\n\n\n\n\n> **Q3**: I would've liked to see on a given problem how the performance will vary if you also vary the data distribution for a given problem. So for example in the maxcut problem, it would be interesting to see results on the GSET benchmark instances or on several other datasets (see e.g., table 3,4, etc. on [3].\n\nThank you for your insightful suggestion. We agree that evaluating under distribution shifts is important for simulating real-world scenarios. In fact, in Table 4, we have already reported results on the MIPLIB 2017 dataset, which is a cross-distribution benchmark consisting of diverse problem instances from various real-world applications. Our method demonstrates strong performance across changing problem classes, further validating the generalization capability of our foundation representation model.\n\nTo further address your concern, we conducted additional experiments on the GSET benchmark without retraining. Following [2] and [3], we report the mean deviation from the best-known cuts obtained by [4], under the same 200s time limit used in our paper. The results are summarized below:\n\n|| $V=800$ | $V=1K$ | $V=2K$ | $V \\geq 3K$ |\n|:-------------:|:-------:|:------:|:------:|:-----------:|\n| ANYCSP | 1.22 | **2.44** | 13.05  | 49.75  |\n|OPTFM (Ours)|**1.18**|**2.44**|**10.95**|**41.6**|\n\nAs shown, OPTFM consistently outperforms ANYCSP across different graph sizes, even under distribution shifts, further demonstrating its strong generalization and representation learning capability. We will include more benchmark comparisons in the final version of the paper to further enrich the evaluation. Thanks again for your suggestions.\n\n\n**References**:\n\n[1] Fast t2t: Optimization consistency speeds up diffusion-based training-to-testing solving for combinatorial optimization. NIPS 2024.\n\n[2] One model, any CSP: graph neural networks as fast global search heuristics for constraint satisfaction. IJCAI 2023.\n\n[3] Are graph neural networks optimal approximation algorithms?. NIPS 2024.\n\n[4] Breakout Local Search for the Max-Cut problem. Engineering Applications of Artificial Intelligence."}, {"review_id": "djoTmj3h9O", "reviewer": "Reviewer_AChR", "summary": "This paper proposes OPTFM, the first graph foundation model designed for general combinatorial optimization tasks. OPTFM introduces a scalable multi-view graph transformer with hybrid attention mechanisms that efficiently model large-scale heterogeneous graphs. The model employs a dual-level pre-training approach combining node-level graph reconstruction and instance-level contrastive learning. Experiments demonstrate that models using OPTFM embeddings outperform task-specific methods across various combinatorial optimization tasks.", "questions": "1. How many epochs are used in each level of pre-training?\n2. Some terms are not clearly defined in the context of this paper, such as “combinatorial optimization” and “semantic consistency”.\n3. There are minor typos, like “A Dual-level” in line 10, “’foundation model’” in line 92, and “1,2” in line 167.", "limitations": "This paper has discussed its limitations.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1. The paper proposes a pre-trained graph foundation model for general combinatorial optimization tasks.\n2. The paper proposes an efficient multi-view attention mechanism and a dual-level pre-training framework.\n3. OPTFM achieves superior performance across multiple downstream combinatorial optimization tasks.\n\nWeaknesses:\n\n1. The motivation of the attention design is unclear, such as Eq. (4).\n2. It lacks the analyses of the introduced hyperparameters.\n3. This paper claims to propose a graph foundation model for general combinatorial optimization tasks, and mentions that edge matrices are sparse. However, some classic combinatorial optimization problems, such as the traveling salesman problem and vehicle routing problem, are defined on a complete graph, which should be discussed.\n4. Some details are unclear (See Questions).", "was_revised": true, "final_justification": "I maintain my score.", "rebuttal": "We thank the reviewer for your time, your recognition of our work, and your thoughtful suggestions. Below, we provide clarifications on your concerns.\n\n> **Q1**: The motivation of the attention design is unclear, such as Eq. (4).\n\nWe thank the reviewer for the comments. Eq.(4) shows how OPTFM integrates graph structure into the attention computation, addressing the limitation of standard all-pair attention, which ignores structural information and may harm performance. While prior work (e.g., [1]) uses a separate GNN to model structure and fuses it with transformer outputs, such a multi-stage fusion only combines final representations without incorporating graph structure into each attention layer. To achieve tighter integration, we propose a unified architecture where, after all-pair attention, we compute $Q_N = NV$ using the adjacency matrix $N$ to capture local neighborhood relevance.\n\nThe resulting $Q_N$ is concatenated with the global attention output $Q_G$, enabling each layer to jointly model long-range dependencies and local structural information. As shown in Tables 1–3, our method significantly outperforms the ablated variant OPTFM-WGNN (which follows the separate GNN+fusion approach of [1]), demonstrating the effectiveness of this unified, structure-aware attention design.\n\n\n\n\n> **Q2**: It lacks the analysis of the introduced hyperparameters.\n\n\nWe sincerely thank the reviewer for the insightful comments. The complete hyperparameter settings used in our experiments are detailed in Section 5.1 and Appendix A.4, including: (1) graph partitioning parameters (e.g., maximum subgraph size), (2) model architecture and training details (e.g., learning rate, number of training epochs), and (3) evaluation parameters for the three downstream tasks. Specifically:\n\n+ The maximum subgraph size is a core hyperparameter of our method. As analyzed in Appendix A.6.1, overly fine-grained partitioning can severely disrupt the structural features of the original graph. Based on empirical analysis, we set $g_{\\text{size}} = 20,000$ as the default value.\n\n+ For model architecture and training details, we ablate the number of training epochs in Appendix A.6.2. We find that performance plateaus after 30 epochs, with no significant improvement beyond that point. Thus, we train for 30 epochs. We will include further analysis of other parameters in the final version to enhance the paper's completeness.\n\n+ For downstream task evaluation, unless otherwise specified, the parameters follow standard implementations from the baselines for fair comparison and were not specifically tuned.\n\n\n> **Q3**: This paper claims to propose a graph foundation model for general combinatorial optimization tasks, and mentions that edge matrices are sparse. However, some classic combinatorial optimization problems, such as the traveling salesman problem and vehicle routing problem, are defined on a complete graph, which should be discussed.\n\n\nWe sincerely thank the reviewer for the comments. Regarding sparsity, we would like to clarify that it refers not to the sparsity of the original problem graph, but to the bipartite graph representation constructed from the mixed integer programming (MIP) formulation of the problem. In the bipartite graph, the two sets of nodes represent variables and constraints, respectively, and an edge exists if a variable appears in a constraint. The sparsity $s$ is defined as the ratio of the number of actual connections between variables and constraints to the maximum possible connections. Even for problems like TSP, which are defined on complete graphs, this sparsity is typically around 10%, depending on the modeling approach.\n\nTo better understand the sparsity characteristics of real-world problems and their impact on our method, we analyze the MIPLIB2017 benchmark set, which contains 240 diverse, real-world instances from various domains. As shown in Table 4, we have conducted extensive experiments on this dataset. We group the 240 instances by sparsity level and report model performance within each group:\n\n**Distribution of instances across sparsity levels (out of 240):**\n\n|| $s < 0.001$ | $0.001 \\leq s < 0.01$ | $0.01 \\leq s < 0.1$ | $s \\geq 0.1$ |\n|:--:|:--:|:--:|:--:|:--:|\n| Instance count | 102 | 81 | 39 | 18 |\n\n**Performance (Gap %) across sparsity levels:**\n\n| Gap% | $s < 0.001$ | $0.001 \\leq s < 0.01$ | $0.01 \\leq s < 0.1$ | $s \\geq 0.1$ |\n|:--:|:--:|:--:|:--:|:--:|\n| **SCIP** | 13.78 | 14.95 | 16.69 | 20.47 |\n| **RL-LNS** | 5.98 | 8.33 | 10.95 | 12.50 |\n| **SGFormer**  | 3.48 | 5.14 | 7.95 | 9.13 |\n| **OPTFM (Ours)** | **2.15** | **3.01** | **3.45** | **5.73** |\n\nAs shown, over **76%** of the instances have sparsity below 1%, and over **92%** below 10%, confirming that most real-world MIPs are indeed sparse in their bipartite graph representation. Furthermore, even in relatively dense regimes — which often correlate with higher problem complexity — OPTFM consistently outperforms all baselines. This demonstrates the robustness of our method, enabled by the structure-preserving adaptive graph partitioning.\n\n\n\n\n> **Q4**: How many epochs are used in each level of pre-training?\n\n\nThe number of training epochs for our dual-level pretraining framework is set as follows:\n\n+ For the node-level graph reconstruction task, we train for 30 epochs. As shown in Figure 6 of Appendix A.6.2, performance stabilizes after 30 epochs, with no significant further improvement observed.\n\n+ For the graph-level contrastive learning task, we train for 15 epochs, determined empirically. Specifically, we evaluate on the validation set every epoch using the metric Intra-Class Variance / Inter-Class Variance. We observe that this metric stabilizes after 15 epochs; therefore, we select the model from the 15th epoch as the final model.\n\n\n> **Q5**: Some terms are not clearly defined in the context of this paper, such as “combinatorial optimization” and “semantic consistency”.\n\nWe thank the reviewer for the insightful feedback. We will include the following clarifying details in the final version of the paper:\n\n+ Combinatorial optimization [2] is a subfield of mathematical optimization that deals with problems where the solution space consists of discrete configurations, and the goal is to find an optimal solution from a finite (but often exponentially large) set of feasible solutions under given constraints.\n\n+ Semantic consistency refers to preserving meaningful feature alignment in the bipartite graph structure, where variable and constraint nodes have fundamentally different semantic meanings and feature spaces, as illustrated in Table 6. Standard transformer attention computes interactions across all nodes jointly, which can mix heterogeneous features and lead to semantically misaligned representations. To address this, our model employs three separate attention streams: self-attention among variables, self-attention among constraints, and cross-attention between variables and constraints. This design ensures that feature interactions occur only within coherent semantic roles or across well-defined cross-node relationships, thereby maintaining semantic consistency and avoiding unintended feature mixing.\n\n\n\n> **Q6**: There are minor typos, like “A Dual-level” in line 10, “’foundation model’” in line 92, and “1,2” in line 167.\n\n\nWe thank the reviewer for the careful reading and valuable suggestions. We have corrected the identified typos and thoroughly proofread the manuscript to ensure such issues are fully addressed in the final version.\n\n\n**References**:\n\n[1] SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations. NeurIPS 2023\n\n[2] Combinatorial optimization[J]. Handbook of combinatorics, 1995."}, {"review_id": "Y6PCviMvwn", "reviewer": "Reviewer_tBdE", "summary": "This paper introduces OPTFM, a scalable graph foundation model for combinatorial optimization based on a multi-view transformer architecture that separately models variables and constraints using hybrid self- and cross-attention mechanisms. It uses two pre-training objectives at two different scales. The model is benchmarked across multiple mixed-integer linear problems (MILP).", "questions": "**Q1.** Can the authors include an ablation of each of the pre-training losses?\n\n**Q2.** How sensitive is the model to the graph partitioning used during training?\n\n**Q3.** Why use ProxyAnchorLoss instead of more common graph contrastive losses (e.g., InfoNCE)?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "*Strengths*\n\n**S1.** This work tackles an important question: how to build models that generalizes to multiple combinatorial optimization problems.\n\n**S2.** The results are strong and demonstrate strong generalization across multiple datasets and downstream tasks.\n\n**S3.** The method that is introduced is novel and addresses many of the key challenges in this domain\n\n*Weaknesses*\n\n**W1.** The model applies self-attention on variable nodes, then on constraint nodes, followed by cross-attention from variables to constraints and from constraints to variables. This design is not empirically validated. Why not just use a single linear attention pass across all nodes with type embeddings to distinguish variables vs. constraints? Aren't the computational gains marginal?\n\n**W2.** The dual-level pretraining setup is interesting, but why not apply existing hierarchical contrastive learning methods? The motivation for using two SSL objectives of different types is not clear: masking and reconstruction for instance-level learning, and contrastive learning for subgraph-level. This adds complexity to the entire architecture. \n\n**W3.** Despite aiming for a foundation model, the datasets are limited to MILPs. Some of the assumptions made in this paper (like the heterogeneous bipartite graph) might not hold in other optimization problems.", "was_revised": true, "final_justification": "The authors propose a novel approach for foundation models to solve combinatorial optimization problems. The results (including the additional results presented during the rebuttal phase) are very strong. For these reasons, I recommend the acceptance of this paper.", "rebuttal": "Thanks for the insightful comments. Below, we provide detailed clarifications to address your concerns.\n\n> **Q1**: The attention design is not empirically validated. Why not just use a single linear attention pass across all nodes with type embeddings?\n\nThanks for the suggestion. Indeed, an alternative approach could treat variable and constraint nodes as a flat sequence and use type embeddings to distinguish their roles within a linear transformer.\n\nHowever, we argue that our structured attention mechanism—comprising separate self-attention and cross-attention—offers key advantages by explicitly respecting the inherent bipartite structure and semantic asymmetry of CO problems, without increasing computational complexity. The design can be viewed as a *semantically aware decomposition* of the full attention matrix, guided by the problem’s structural prior.\n\n+ **Preservation of semantic coherence**: By isolating self-attention within node types, our model learns more expressive and focused representations for how variables and constraints interact among themselves. Cross-attention then precisely models the influence of constraints on relevant variables (and vice versa), which is critical in optimization settings where variable-constraint relations are complex and feasibility must be maintained.\n\n+ **Stronger inductive bias and better generalization**: Our architecture embeds a strong inductive bias aligned with the bipartite nature of MIP formulations. This structural prior helps the model generalize across problem scales and distributions, which is particularly important in real-world settings.\n\nTo validate this, we implemented **OPTFM-Flat**, an ablation that removes structured attention and applies standard all-pair attention over the node sequence. Additional type embeddings (0 for variables, 1 for constraints) are mapped to 64D and added to the node features. All other settings remain identical for a fair comparison. We firstly focus on the Maximum Cut (MC) and its scaled-up variants (MC2, MC4) on downstream task II (Table 2, 3). The results are as follows:\n\n**MC**\n\n||Gap (%)|Primal Integral (PI)|\n|:--:|:--:|:--:|\n|OPTFM-Flat|3.35|4517 |\n|OPTFM (Ours)|**3.02**|**3845**|\n\n**MC2**\n\n||Gap (%)|Primal Integral (PI)|\n|:--:|:--:|:--:|\n|OPTFM-Flat| 3.57| 9531|\n|OPTFM (Ours)|**1.95**|**4339.4**|\n\n**MC4**\n\n|| Gap (%) | Primal Integral (PI) |\n|:--:|:--:|:--:|\n|OPTFM-Flat|3.71| 37839|\n|OPTFM (Ours)|**1.99**|**25213**|\n\nAs shown, OPTFM performs consistently better, demonstrating that our structure-aware design offers superior scalability and robustness—critical for practical optimization. We will include additional comparisons in the final paper version.\n\n> **Q2**: Why not apply existing hierarchical contrastive learning methods? The motivation for using two SSL objectives of different types is not clear.\n\nThanks for the thoughtful comment. We fully appreciate the well-established works on hierarchical contrastive learning [1–4]. However, our dual-level pretraining framework is specifically designed to address the challenges of **ultra-large graphs in CO**. We respectfully clarify that our design does not introduce unnecessary complexity, but rather *reduces* computational and memory overhead through a **sequential, decoupled pretraining paradigm**—a key distinction from existing joint hierarchical training methods.\n\n>> Q2.1 Why two different SSL objectives? \n\nThe goals at each level are semantically distinct. At the subgraph level, the objective is to learn fine-grained, structure-preserving node representations. Masking and reconstruction forces the model to capture local topology. While at the instance level, the goal shifts to learning view-invariant global representations, where contrastive learning is reasonable to deal with. These two objectives are *complementary*.\n\n>> Q2.2 Why not utilize existing hierarchical contrastive methods?\n\nExisting methods typically use **joint optimization** over multiple graph views, which becomes prohibitively expensive in memory and computation for million-node graphs (our largest exceed 10M).\n\nIn contrast, our **decoupled two-stage design** reduces training cost significantly:\n- *Node-level*: train on small, independently sampled subgraphs ($<20$k); memory scales with subgraph size.\n- *Graph-level*: with the first stage frozen, extract global tokens into a short sequence ($<500$) and apply transformer-based contrastive learning—ensuring high efficiency.\n\nThis sequential pipeline enables per-instance pretraining in **minutes**, even for graphs with ~10M nodes.\n\n\n> **Q3**: Datasets are limited to MILPs. Some of the assumptions made in this paper might not hold in other problems.\n\nThank you for the comment. Indeed, we discuss the limitations in the paper. Our current work mainly focuses on MILPs, rather than a full spectrum of CO. MILP is a fundamental and canonical class in CO, widely recognized for its theoretical significance and broad real-world applicability. It has also become a foundational‌ testbed for extensive learning-based methods **[5–14]**. Despite this attention, most approaches are tailored to specific tasks or datasets, lacking generalization.\n\nOur work demonstrates that a task- and dataset-agnostic foundation model is achievable within the MILP domain, providing a unified representation that generalizes across instances and downstream tasks. By focusing on MILP, we present a principled step toward foundation models in CO, with potential to inspire broader generalizations. And we are also actively exploring extensions of OPTFM to support a wider range of CO.\n\n> **Q4**: Can the authors include an ablation of each of the pre-training losses?\n\nThanks for the suggestion. In OPTFM, the two pretraining stages use different losses: cross-entropy for node-level graph reconstruction, and ProxyAnchorLoss for graph-level contrastive learning.\n\n+ **Cross-Entropy Loss:** We conduct ablation studies with Focal Loss [15] and MSE (Mean Squared Error). Due to the limited rebuttal period, experiments are performed on Downstream Task II using the Maximum Cut (MC) problem and its scaled variants (MC2, MC4). The following results show that Focal Loss performs slightly worse than cross-entropy, while MSE yields significantly inferior performance:\n\n||MC Gap (%)|MC2 Gap (%)|MC4 Gap (%)|\n|:--:|:--:|:--:|:--:|\n|OPTFM-MSE|3.65|2.43 |2.57|\n|OPTFM-Focal|3.11|**1.95**|2.07|\n|OPTFM (Ours)|**3.02**|**1.95**|**1.99**|\n\n+ **ProxyAnchorLoss:** We conduct an ablation study against InfoNCE. It is identical to our OPTFM except for the loss function. We compare both models on downstream Task III, and summarize the results below by counting the number of instances where each method achieves better performance (wins) on each dataset:\n\n||Item|Load|Anony|\n|:--:|:--:|:--:|:--:|\n|OPTFM-InfoNCE|39/100|45/100|8/20|\n|OPTFM (Ours)|**61/100**|**55/100**|**8/20**|\n\nAs shown, OPTFM with ProxyAnchorLoss achieves slightly better discriminative power in learning graph representations.\n\n> **Q5**: How sensitive is the model to the graph partitioning used during training?\n\nIn Appendix A.6.1, we analyze the impact of maximum subgraph size and find that overly fine-grained partitioning disrupts graph structure, while the effect diminishes beyond 20,000 nodes—likely because subgraphs of this size preserve sufficient local structure. To further evaluate the effects, similar to Sec 5.5, we constructed a set of set covering instances with 50,000 nodes each. We compared three configurations:\n- **Config 1**: Full graph training/testing.\n- **Config 2**: Each graph is divided into 2 subgraphs.\n- **Config 3**: Each graph is divided into 5 subgraphs.\n\nThe experiments were conducted on downstream Task II (Table 2), with all settings identical to OPTFM except for the dataset. The results are as follows:\n\n|Configuration|Gap %|Primal Integral (PI)|\n|:--:|:--:|:--:|\n|Config 1|0.69|14521|\n|Config 2|0.75|14936|\n|Config 3|0.79|15792|\n|SCIP|2.74| 21238|\n|Gurobi|**0.61**|**13998**|\n\nPerformance gradually declines with smaller subgraphs, but remains significantly better than SCIP and comparable to Gurobi. This indicates that the model is robust to graph partitioning when subgraphs are sufficiently large.\n\n> **Q6**: Why use ProxyAnchorLoss instead of InfoNCE?\n\nWe empirically found that ProxyAnchorLoss achieves more stable and slightly better performance compared to InfoNCE (see our response to Q4).\n\n\n**References**:\n\n[1] GTC: GNN-transformer co-contrastive learning for self-supervised heterogeneous graph representation. Neural Networks, 2025.\n\n[2] Keywords and Instances: A Hierarchical Contrastive Learning Framework Unifying Hybrid Granularities for Text Generation. ACL 2022.\n\n[3] Omniseg3d: Omniversal 3d segmentation via hierarchical contrastive learning. CVPR 2024.\n\n[4] Wang K, Zhu Y, Zang T, et al. Enhanced hierarchical contrastive learning for recommendation. AAAI 2024.\n\n[5] Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning, ICML 2023.\n\n[6] BTBS-LNS: Binarized-Tightening, Branch and Search on Learning LNS Policies for MIP, ICLR 2025.\n\n[7] Learning to branch with tree mdps, NeurIPS 2022.\n\n[8] Towards Imitation Learning to Branch for MIP: A Hybrid Reinforcement Learning based Sample Augmentation Approach, ICLR 2024.\n\n[9] Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical, ICLR 2023.\n\n[10] GNN&GBDT-Guided Fast Optimizing Framework for Large-scale Integer Programming, ICML 2023.\n\n[11] Light-milpopt: Solving large-scale mixed integer linear programs with lightweight optimizer and small-scale training dataset, ICLR 2024.\n\n[12] A gnn-guided predict-and-search framework for mixed-integer linear programming, ICLR 2023.\n\n[13] Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming, ICLR 2025\n\n[14] Differentiable Integer Linear Programming, ICLR 2025.\n\n[15] Focal Loss for Dense Object Detection. ICCV 2017."}, {"review_id": "crtGKX2uBq", "reviewer": "Reviewer_bYNu", "summary": "In response to the prevalent limitations of \"task-specific and model-exclusive\" approaches in existing machine learning for combinatorial optimization, this paper proposes the first \"graph foundation model\" for general combinatorial optimization problems, OPTFM. The authors designed:\n\n1. A scalable multi-perspective graph Transformer with O(N) time and space complexity: It employs self-attention within variables/constraints and cross-attention between the two types of nodes, supplemented by sparse adjacency matrix encoding to balance global correlations and local structural consistency.\n\n2. A two-tier self-supervised pre-training framework of \"node-instance\": The lower tier learns node and edge representations through masked graph reconstruction, while the upper tier serializes subgraph global vectors and aggregates them into instance-level representations via contrastive learning.\n\nWithout fine-tuning, the model outperforms multiple end-to-end or multi-task baselines on MIPLIB2017 and four types of NP-hard downstream tasks (solution value prediction, LNS, solver configuration, etc.), and approaches or even surpasses the Gurobi commercial solver in some scenarios.", "questions": "1. OPTFM relies solely on static features. Will adding dynamic features (such as the state of branch - and - bound pruning) undermine the \"zero - fine - tuning\" advantage? Experimental results or discussions are expected.\n\n2. How much does the cross - attention and multi - perspective design enhance the expressive ability? It is recommended to conduct more fine - grained ablation studies (such as removing self - attention and keeping only cross - attention, etc.).\n\n3. Can the training time/energy consumption be further reduced through more efficient sub - graph sampling or parameter sharing? It would be great to provide a resource - performance trade - off curve.\n\n4. The paper claims that it can handle graphs with tens of millions of nodes, but the experimental verification is mainly based on sub - graph partitioning. Please report the largest graph scale that can be directly trained without partitioning and the corresponding performance degradation.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- Innovation: For the first time, the concept of \"foundation model\" is systematically introduced into combinatorial optimization, and a new paradigm combining multi - perspective attention with hierarchical pre - training is proposed. \n\nWeaknesses\n- Scope of experiments: The experiments only cover MILP (especially datasets dominated by binary variables), and the applicability to broader CO problems with nonlinear or dynamic constraints remains unvalidated.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments and constructive feedback on our paper. We sincerely appreciate your thoughtful evaluation. In response to your concerns, we would like to provide the following clarifications.\n\n> **Q1**: The experiments only cover MILP, and the applicability to broader CO problems with nonlinear or dynamic constraints remains unvalidated.\n\nThank you for your insightful comment. We acknowledge that our work focuses on mixed-integer linear programming (MILP), not the full range of combinatorial optimization (CO) problems. MILP is a fundamental and widely applicable CO class, with significant theoretical and practical impact across domains such as logistics, scheduling, and resource allocation. It is a primary modeling framework in both industry and academia, and has become a foundational‌ testbed for learning-based optimization methods **[1-10]**.\n\nDespite growing interest, most existing methods are task or dataset-specific. Our work shows that a task- and dataset-agnostic foundation model is feasible within the MILP domain, offering unified, generalizable representations. By focusing on this well-established subclass, we present a principled step toward foundation models in CO, with potential to inspire broader extensions.\n\nWe agree on the importance of wider applicability and are actively exploring generalizations of OPTFM to other CO problems.\n\n\n> **Q2**: OPTFM relies solely on static features. Will adding dynamic features undermine the \"zero finetuning\" advantage? Experimental results or discussions are expected.\n \nWe acknowledge that OPTFM currently relies solely on static features. This is by design—our goal is to build a lightweight, general-purpose pre-training framework that is easy to adopt across diverse downstream tasks. While dynamic features offer runtime insights, their use introduces critical limitations:\n \n+ **Solver Dependency & Overhead**: Extracting dynamic features requires partial or full solver execution and often depends on solver-specific implementations or instrumentation, leading to high overhead and reduced portability.\n+ **Loss of Plug-and-Play Usability**: These features tie model representations to solver execution traces, forcing users to re-run solvers during inference—undermining the framework’s plug-and-play capability.\n \nBy focusing on static features, OPTFM ensures broad compatibility and seamless deployment across solvers and environments. The inclusion of dynamic features in pre-training introduces overhead and is somewhat unnecessary-since they are task-specific and better suited for downstream use. Indeed, in Downstream Task II (see Appendix A.4.2 for details), we successfully integrate dynamic features to boost performance (shown in Table 2 and 3), demonstrating that such enhancements can be effectively applied when and where needed.\n \n\n> **Q3**: How much does the cross-attention and multi-perspective design enhance the expressive ability? It is recommended to conduct more fine-grained ablation studies (such as removing self-attention and keeping only cross-attention, etc.).\n\nThank you for your insightful suggestion. During the rebuttal phase, we implemented an ablated variant, OPTFM-OnlyCross, which removes self-attention within variables and constraints and retains only the cross-attention. All other settings remain identical to OPTFM, ensuring a fair comparison. Due to time constraints, we evaluated this variant only on downstream Task II on the Maximum Cut (MC) problem and its scaled versions MC2 and MC4, under the same experimental setup as in Tables 2 and 3. The results are as follows:\n\n**Maximum Cut (MC)**\n|Model|Gap (%)|Primal Integral (PI)|\n|:--:|:--:|:--:|\n|OPTFM-OnlyCross| 3.63    | 5006                  |\n|OPTFM (Ours)| **3.02**| **3845**              |\n\n**MC2**\n|Model|Gap (%)|Primal Integral (PI)|\n|:--:|:--:|:--:|\n|OPTFM-OnlyCross|2.47|5738.5 |\n|OPTFM (Ours)| **1.95**| **4339.4**            |\n\n**MC4**\n| Model             | Gap (%) | Primal Integral (PI) |\n|:-------------------:|:---------:|:--:|\n| OPTFM-OnlyCross   | 2.59    | 31971                 |\n| OPTFM (Ours)      | **1.99**| **25213**             |\n\nThe results show a clear performance drop when self-attention within variables and constraints is removed, demonstrating that modeling intra-group dependencies is crucial for capturing structural information in combinatorial optimization problems. Combined with the results in Tables 2 and 3, we conclude that both **self-attention** and **cross-attention** play essential roles in building powerful and generalizable representations for CO.\n\n\n> **Q4**: Can the training time/energy consumption be further reduced through more efficient sub-graph sampling or parameter sharing? It would be great to provide a resource-performance trade-off curve.\n\nThank you for this insightful and valuable suggestion. We fully agree that understanding the resource-performance trade-off is crucial for practical foundation models.\n\nIn our current implementation, we use graph partitioning with parameter sharing across subgraphs to efficiently handle large-scale CO instances. While further reducing subgraph size (i.e., more efficient sampling) could improve efficiency, it risks disrupting structural information—potentially harming performance.\n\nWe have already analyzed key aspects of this trade-off:\n- **Resource cost**: Section 5.5 (Fig. 3) shows that training time and memory grow nearly linearly with subgraph size. Our current resources (2 A100 GPUs) limit us to subgraphs of up to 50K nodes.\n- **Performance trend**: Appendix A.6.1 (Fig. 5) shows training performance vs. subgraph size. Performance continues to improve with larger subgraphs, but the marginal gains become less pronounced beyond ~20K nodes.\n\nBalancing both sides, we set the default maximum subgraph size to 20K. To further support this choice, we include additional downstream results in our response to Q5.\n\nIn the final version, we will add a dedicated **resource-performance trade-off curve** to clearly summarize this analysis, as you recommended. We apologize that, due to rebuttal requirements, we are unable to include the vision curve here.\n\n\n> **Q5**: The paper claims that it can handle graphs with tens of millions of nodes, but the experimental verification is mainly based on sub-graph partitioning. Please report the largest graph scale that can be directly trained without partitioning and the corresponding performance degradation.\n\n\n\n\nThank you for your detailed comments. Under our current hardware configuration—two NVIDIA A100 PCIe 40GB GPUs—the system can handle single graphs of up to 100,000 nodes for inference. However, for training, we find multiple graphs with up to 50,000 nodes each are more practical due to memory and computational efficiency.\n\nRegarding potential performance degradation from graph partitioning, we provide an analysis in Appendix A.6.1 on the impact of different maximum subgraph sizes. We observe that overly fine-grained partitioning can severely disrupt the original graph’s structural features. However, when subgraph sizes exceed 20,000 nodes, performance degradation becomes less pronounced—likely because such subgraphs are large enough to preserve meaningful local structure.\n\nTo further evaluate this, we follow the setup of Section 5.5 and construct a set of 50,000-node set covering instances, split into 70% training, 20% validation, and 10% test sets. We compare three configurations:\n- **Config 1**: Full-graph training and inference.\n- **Config 2**: Each graph is partitioned into 2 subgraphs.\n- **Config 3**: Each graph is partitioned into 5 subgraphs.\n\nAll models are evaluated on downstream Task II (as in Table 2), with identical settings to OPTFM except for the data. Results are summarized below:\n\n| Configuration | Gap (%) | Primal Integral (PI) |\n|:-------------:|:-------:|:--------------------:|\n| Config 1      | 0.69    | 14,521               |\n| Config 2      | 0.75    | 14,936               |\n| Config 3      | 0.85    | 15,792               |\n| SCIP          | 2.74    | 21,238               |\n| Gurobi        | **0.61**| **13,998**           |\n\nAs shown, performance gradually decreases with finer partitioning, but remains significantly better than SCIP and competitive with Gurobi. This demonstrates that **appropriate graph partitioning effectively balances computational efficiency and model performance**, without substantially compromising solution quality.\n\n\n**References**:\n\n[1] Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning, ICML 2023.\n\n[2] BTBS-LNS: Binarized-Tightening, Branch and Search on Learning LNS Policies for MIP, ICLR 2025.\n\n[3] Learning to branch with tree mdps, NeurIPS 2022.\n\n[4] Towards Imitation Learning to Branch for MIP: A Hybrid Reinforcement Learning based Sample Augmentation Approach, ICLR 2024.\n\n[5] Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical, ICLR 2023.\n\n[6] GNN&GBDT-Guided Fast Optimizing Framework for Large-scale Integer Programming, ICML 2023.\n\n[7] Light-milpopt: Solving large-scale mixed integer linear programs with lightweight optimizer and small-scale training dataset, ICLR 2024.\n\n[8] A gnn-guided predict-and-search framework for mixed-integer linear programming, ICLR 2023.\n\n[9] Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming, ICLR 2025\n\n[10] Differentiable Integer Linear Programming, ICLR 2025."}]

Author rebuttal:

Meta-review: In this paper, the authors study foundation models for graph-based combinatorial optimization problems. Specifically, the proposed method adopts a multi-view graph transformer to model heterogeneous graphs and a dual-level pre-training framework to enable robust and adaptable representation. Experiments across diverse optimization show the effectiveness of the proposed method. 

Reviewers agree that the work is novel, timely, and addresses the important research question of how to design models that generalize across diverse combinatorial optimization tasks. Some concerns were raised about the limited experimental scope and certain discussions, but these are largely addressed in the rebuttal. All things considered, the paper makes a significant contribution by introducing the foundation model paradigm to combinatorial optimization, with a novel architecture and strong empirical results that demonstrate generalization potential. I recommend accepting the paper.
Decision: Accept (spotlight)