@article{Pu2026, 
author = {Tianle Pu and Bingxu Zhang and Li Zeng and Chao Chen and Guangquan Cheng and Xingchen Hu and Xin Lü and Changjun Fan},
title = {Pre-training and fine-tuning: a unified approach for solving graph combinatorial optimization problems},
year = {2026},
journal = {Journal of National University of Defense Technology},
volume = {48},
number = {4},
pages = {128-138},
keywords = {graph combinatorial optimization problem, model pre-training, model fine-tuning, unified solving},
url = {https://www.sciopen.com/article/10.11887/j.issn.1001-2486.25040026},
doi = {10.11887/j.issn.1001-2486.25040026},
abstract = {ObjectiveTo overcome computational inefficiency and generalization limitations in graph combinatorial optimization (GCOP) by establishing a unified framework (GCOP-PREMA) that leverages pre-training and fine-tuning to achieve state-of-the-art performance across multiple NP-hard problems (MVC, MIS, MC, MaxCut).MethodsThe proposed framework employed a three-stage methodology: First, diverse GCOPs were reduced to Quadratic Unconstrained Binary Optimization (QUBO) representations. Second, a custom QUBO Former model—integrating graph transformers with message-passing networks and positional encoding—was pre-trained on mixed QUBO datasets using Deep Q-Networks and adaptive penalty adjustment. Third, five fine-tuning strategies (e.g., decoder-specific updates) adapted the model to downstream tasks with minimal computational overhead.ResultsFine-tuning boosts MIS performance by 56.67% and MaxCut by 28.44% versus pre-trained baselines. The Centrality Encoding variant achieves solutions within 5% of Gurobi′s optimality across problems and outperforms specialized algorithms. Runtime analysis confirms stable efficiency, particularly on large-scale graphs.ConclusionsGCOP-PREMA bridges specialized solvers and general-purpose AI by unifying problem reformulation, pre-training, and adaptive fine-tuning. It significantly advances cross-problem generalization while maintaining architectural consistency, with future work targeting optimization imbalance and diffusion-model enhancements.}
}