正线性约束组合优化问题的非自回归学习求解  

Learning to solve combinatorial optimization under positive linear constraints via non-autoregressive neural networks

作　　者：汪润中 郦洋 严骏驰[3,1,2] 杨小康 Runzhong WANG;Yang LI;Junchi YAN;Xiaokang YANG(Department of Computer Science and Engineering,Shanghai Jiao Tong University,Shanghai 200240,China;Key Laboratory of Artificial Intelligence,Ministry of Education,Shanghai Jiao Tong University,Shanghai 200240,China;School of Artificial Intelligence,Shanghai Jiao Tong University,Shanghai 200030,China)

机构地区：[1]上海交通大学计算机科学与工程系,上海200240 [2]上海交通大学人工智能教育部重点实验室,上海200240 [3]上海交通大学人工智能学院,上海200030

出　　处：《中国科学：信息科学》2024年第10期2368-2384,共17页Scientia Sinica(Informationis)

基　　金：国家自然科学基金委重大研究计划重点项目(批准号:92370201)、国家自然科学基金委优秀青年基金项目(批准号:62222607);国家自然科学基金委专项项目(批准号:72342023);上海市市级科技重大专项项目(批准号:2021SHZDZX0102)资助。

摘　　要：组合优化问题的求解是计算机科学、应用数学等学科共同研究的基础性问题.其固有的计算复杂性为精确求解带来了挑战.而采用深度神经网络进行求解已经成为一个前沿的研究方向.本文设计了一种能够求解正线性约束组合优化问题的非自回归式神经网络.本文方法的优势在于,正线性约束代表了一大类组合优化问题,突破了现有非自回归网络的通用性瓶颈;与目前常用的自回归网络相比,非自回归网络具有高效性、排列不变性等优势;在神经网络框架中,本文采用的离线无监督学习对标注的需求低,无需求解最优解进行监督训练;本文提出的在线可微分搜索方法显著提升了神经网络求解器的泛化能力.本文在设施布局、最大集合覆盖、旅行商问题等代表性的组合优化问题中验证了非自回归求解器的有效性.特别是在综合考虑求解效率和求解效果时,非自回归网络求解器持平甚至超越了SCIP,Gurobi等开源或者商用的主流传统求解软件.Combinatorial optimization(CO)is the fundamental problem at the intersection of computer science,applied mathematics,etc.The inherent hardness in CO problems brings up a challenge for solving CO exactly,making deep-neural-network-based solvers a research frontier.In this paper,we design a family of nonautoregressive neural networks to solve CO problems under positive linear constraints with the following merits.First,the positive linear constraint covers a wide range of CO problems,indicating that our approach breaks the generality bottleneck of existing non-autoregressive networks.Second,compared to existing autoregressive neural network solvers,our non-autoregressive networks have the advantages of higher efficiency and preserving permutation invariance.Third,our offline unsupervised learning has a lower demand on high-quality labels,getting rid of the demand of optimal labels in supervised learning.Fourth,our online differentiable search method significantly improves the generalizability of our neural network solver to unseen problems.We validate the effectiveness of this framework in solving representative CO problems including facility location,max-set covering,and traveling salesman problem.Our non-autoregressive neural solvers are competitive and can be even superior to state-of-the-art solvers such as SCIP and Gurobi,especially when both efficiency and efficacy are considered.

关 键 词：组合优化 深度学习 非自回归网络 图神经网络 梯度优化 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]