预训练和微调:图组合优化问题的统一求解方法
DOI:
作者:
作者单位:

1.国防科技大学;2.空军军医大学空军特色医学中心

作者简介:

通讯作者:

中图分类号:

TP18

基金项目:

国家自然科学基金创新研究群体项目(72421002)、国家自然科学基金青年项目(62206303)、湖南省科技创新计划资助(2023RC3009)、重庆市教委科学技术研究重点项目(KJZD-K202200904)以及国防科技大学基石基金项目(JS24-05)


Pre-training and Fine-tuning: A unified approach for solving graph combinatorial optimization problems
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献()
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    图组合优化问题广泛存在于现实场景,但由于其非确定性多项式时间困难(Non-deterministic Polynomial-time hard, NP-hard)特性,传统精确算法难以应对大规模实例,而现有机器学习方法通常依赖问题特定的模型设计,限制了算法的通用性。为此,该研究提出一种基于预训练-微调范式的统一求解框架,旨在提升模型在多种图组合优化任务上的泛化能力与求解效率。该框架首先将不同组合优化问题规约至统一形式,构建一致的表征空间;随后设计跨问题预训练机制,从多样化问题中学习共性知识;在此基础上,引入多种微调策略,使模型能够快速适应测试阶段的不同问题分布。实验结果表明,所提方法在保持单一模型架构的前提下,在多个经典组合优化任务上均取得了优越的泛化性能和稳定的求解效率,为构建通用的组合优化求解器提供了可行路径。

    Abstract:

    Graph combinatorial optimization problems are widely found in real-world applications. However, due to their NP-hard nature, traditional exact algorithms struggle with large-scale instances, while existing machine learning approaches often rely on problem-specific model designs, limiting their general applicability. To address this, a unified solving framework based on a pre-training and fine-tuning paradigm is proposed, aiming to enhance generalization capability and solving efficiency across diverse graph combinatorial optimization tasks. The framework first reduced different combinatorial optimization problems into a unified form, constructing a consistent representation space. A cross-problem pre-training mechanism was then designed to learn common knowledge from diverse problem instances. Furthermore, multiple fine-tuning strategies were introduced to enable the model to quickly adapt to various problem distributions during testing. Experimental results demonstrate that the proposed method achieves superior generalization performance and stable solving efficiency across multiple classic combinatorial optimization tasks while maintaining a single model architecture, offering a feasible path toward a general-purpose combinatorial optimization solver.

    参考文献
    相似文献
    引证文献
引用本文
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2025-04-15
  • 最后修改日期:2025-11-29
  • 录用日期:2025-12-05
  • 在线发布日期:
  • 出版日期:
文章二维码