Organizations: National Yang Ming Chiao Tung University · Institute for Infocomm Research (I2R), A*STAR · Eindhoven University of Technology Eindhoven · Centre for Frontier AI Research, A*STAR · Huazhong University of Science and Technology · National University of Singapore
Recent research has demonstrated the effectiveness of large language models (LLMs) in solving combinatorial optimization problems (COPs) by representing tasks and instances in natural language. However, purely language-based approaches struggle to accurately capture complex relational structures inherent in many COPs, rendering them less effective at addressing medium-sized or larger instances. To address these limitations, we propose AlignOPT, a novel approach that aligns LLMs with graph neural solvers to learn a more generalizable neural COP heuristic. Specifically, AlignOPT leverages the semantic understanding capabilities of LLMs to encode textual descriptions of COPs and their instances, while concurrently exploiting graph neural solvers to explicitly model the underlying graph structures of COP instances. Our approach facilitates a robust integration and alignment between linguistic semantics and structural representations, enabling more accurate and scalable COP solutions. Experimental results demonstrate that AlignOPT achieves state-of-the-art results across diverse COPs, underscoring its effectiveness in aligning semantic and structural representations. In particular, AlignOPT demonstrates strong generalization, effectively extending to previously unseen COP instances.
Figures & tables
Figure 1: Overall workflow of AlignOPT. (a) AlignOPT first performs multi-task pretraining on diverse COPs to align semantic and structural node representations with TGC and TGM losses. The LLM remains frozen and processes the TAIs to generate semantic node representations. (b) The encoder and decoder are then fine-tuned through reinforcement learning to solve COPs. Notably, LLMs are excluded during this phase to ensure computational efficiency, as the encoder has already been aligned with LLM-derived representations during pre-training. (c) The model architecture of the graph-based encoder, which applies a mixed attention mechanism that enables handling COPs represented by graphs.
Method
n=20
n=50
n=100
TSP
AEL
7.78%
10.50%
12.35%
ReEvo
7.77%
10.23%
11.87%
SGE
11.32%
45.28%
-
LMEA ∗
3.94%
-
-
ORPO ∗
4.40%
133.0%
-
LNCS
0.39%
1.62%
4.38%
Table 1: The optimality gaps of LLM-based approaches on different tasks. *: Results are drawn from the original literature. -: Excessively long time leads to unavailability. Bold indicates the best results among comparable methods.
TSP
Method
n=20
n=50
n=100
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
LKH3
3.85
0.00%
0.05s
5.69
2.80%
0.26s
7.76
0.00%
2.05s
OR tools
3.85
0.00%
0.36s
5.87
3.07%
0.60s
8.13
4.77%
1.32s
Nearest neighbor
3.91
1.45%
0.06s
5.89
3.51%
0.03s
9.69
24.87%
0.10s
Farthest insertion
3.96
2.89%
0.21s
5.98
4.97%
4.73s
8.21
5.80%
126s
ACO
3.94
2.23%
0.74s
6.54
14.54%
1.53s
9.99
28.74%
2.01s
Table 2: Performance comparison on 1K instances. AlignOPT(MTFT) denotes multi-task fine-tuning on diverse COPs, while AlignOPT(STFT) refers to fine-tuning on the target COP. Obj. indicates the average objective values. LNCS uses LLM Encoder + Transformer Decoder, GOAL uses GNN only, and AlignOPT uses GNN + Transformer Decoder.
Figure 2: Generalization results on 3 unseen COPs.
TSP
Method
n=20
n=50
n=100
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
AlignOPT (GNS)
4.02
4.41%
0.048s
6.33
11.24%
0.082s
8.37
7.86%
0.165s
AlignOPT (w/o TGC)
3.96
2.86%
0.048s
6.18
8.24%
0.082s
8.22
5.52%
0.165s
AlignOPT (w/o Task Rep.)
3.85
0.00%
0.048s
5.76
0.70%
0.082s
7.87
4.38%
0.165s
AlignOPT (w/o TGM)
3.85
0.00%
0.048s
5.77
0.52%
0.082s
7.89
0.64%
0.165s
AlignOPT(STFT)
3.85
0.00%
0.048s
5.71
0.35%
0.082s
7.79
0.38%
0.165s
Table 3: Ablation studies of key designs across 1K instances for 5 representative COPs.
Figure 3: Average Objective values of different LLMs (Llama3.1 8B and Qwen2.5 8B)
Instance
Optimal
Nearest Neighbor
Farthest Insertion
ACO
OR-tools
alignopt
Obj.
Gap
Obj.
Gap
Obj.
Gap
Obj.
Gap
Obj.
Gap
Very Large Instances ( > 5,000 nodes)
brd14051
469,385
1,012,347
115.6%
998,452
112.7%
912,836
94.5%
878,421
87.2%
880,129
87.5%
d15112
1,573,084
3,189,745
102.8%
3,123,678
98.6%
2,864,512
82.1%
2,788,956
77.3%
2,791,832
77.5%
d18512
645,238
1,324,567
105.3%
1,287,654
99.6%
1,219,876
89.1%
1,198,732
85.8%
1,195,678
85.3%
rl11849
923,288
1,987,654
115.3%
1,898,765
105.7%
1,754,321
90.0%
1,712,345
85.5%
1,708,923
85.1%
Table 4: Performance comparison on large-scale TSP instances (size ≥ 1000) from TSPLib. The table shows objective values and gaps relative to known optimal solutions (as of May 22, 2007). Instances are grouped by size for better readability. Bold values indicate the best (lowest) gap for each instance. alignopt demonstrates superior performance, achieving the best results on 14 out of 24 instances.
College of Computer Science, Sichuan University · Department of Industrial Engineering&Innovation Sciences, Eindhoven University of Technology · Institute of Marine Science and Technology, Shandong University +1
Faculty of Engineering, The University of Hong Kong, Hong Kong SAR, China · Costello College of Business, George Mason University, VA, USA · Faculty of Business and Economics, The University of Hong Kong, Hong Kong, China +1