范长俊- 数智驱动的图上组合优化问题学习型求解技术.pdf

1、数智驱动的图上组合优化问题学习型求解技术范长俊国防科技大学目录图上的组合优化问题人工智能求解框架开源框架设计目录图上的组合优化问题人工智能求解框架开源框架设计min().()0f xstg xxD组合优化（combinatorial optimization，CO)是通过对数学方法的研究，寻找离散事件的最优编排、分组、次序或筛选，所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等领域。该问题可用数学模型描述为：其中D表示有限个点组成的集合（定义域），f为目标函数，F=x|xD,g(x)0为可行域引自王建江，大规模组合优化问题求解方法与应用，智慧调度网络公益系列讲座图上的组合优化

2、问题图上的组合优化（graph combinatorial optimization，GCO)：离散事件是点和边的集合，选择最优的节点集合或边的集合最优化任务目标。图上的组合优化问题最小节点覆盖问题：找到最少的节点覆盖全部的边.,1,1,0,2,1,2|2,1|,1,1,1,1.min,11jinjixnSnSSxnjxnixtsxdijSjiijniijnjijnjiijij目标函数约束条件1.旅行商问题（TSP）例子一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为，如何选择一条道路使得商人每个城市正好走一遍后回到起点且所走路径最短。图上的组合优化问题(,)u vE(,)GV E2

3、.最小节点覆盖问题（MVC）给定无向图，顶点集为V，边集为E，它的一个最小节点覆盖V是顶点集V的一个子集，使得若，则或uVvV.1,(,)0,1,jj Vijjminxst xxi jExjV 例子目标函数约束条件图上的组合优化问题3.最大割问题（Max-Cut）给定带权图，找到节点子集，使得割集中的边的权重之和最大，其中割集C 中的边满足(,)GV E W(,)max(2)().1,0,1,ijijiji jEijiwxxxxstxxi jVxiV SVCE(,)u v,uS vS例子目标函数约束条件图上的组合优化问题4.图着色问题5.最大独立集问题6.影响力最大化问题7.最大公共子图问题8

4、.图匹配问题例子 大部分图上组合优化问题都是NP-hard的 很多其他问题都可以转化为图上的组合优化问题图上的组合优化问题军事资源部署配置火力-目标分配军事物资装载优化侦察卫星任务规划无人机航迹规划军事应用解是可数的，可行域（解）是有限的最优解一定存在可行方案非常多，枚举法不可行，NP-hard问题特征引自王建江，大规模组合优化问题求解方法与应用，智慧调度网络公益系列讲座图上的组合优化问题数学优化算法-精确算法（指数时间）分支定界，分支定价，分支-切割，割平面、拉格朗日松弛启发式算法（多项式时间）近似算法、贪婪算法，基于规则的构造算法，元启发式算法（多项式时间）遗传算法，蚁群算法，禁忌搜索，模

5、拟退火机器学习方法（多项式时间）监督学习、强化学习、图神经网络图上的组合优化问题组合优化求解器商用求解器Gurobi,CPLEX,Matlab,Lingo，CMIP，COPT开源求解器 HiGHS，SCIP,LP_Solve,CBC,GLPK,MOSEK图上的组合优化问题图上的组合优化问题人工智能求解框架开源框架开发目录组合优化问题的机器学习求解范式端到端求解自回归/非自回归Learning Heuristics局部改进求解ML+传统运筹算法Improving OR Solverse.g.B&B via Learning人工智能求解框架图表示学习模型节点/边的表示向量基 于 表 示向 量 的

6、学习模型每 个 时 间步t的预测概率组 合 优 化问题的解一次性给出全部预测组 合 优 化问题的解每个时间步t的部分解结果启发式搜索规则，如波束搜索（beam search）每个时间步t的部分解结果基于基准解的损失函数或强化学习的奖励函数基于基准解的损失函数输入图端到端求解一般性框架阶段一：图表示学习阶段二：利用表示向量求解组合优化问题人工智能求解框架图表示学习模型节点/边的表示向量基 于 表 示向 量 的 学习模型每 个 时 间步t的预测概率组 合 优 化问题的解一次性给出全部预测组 合 优 化问题的解每个时间步t的部分解结果启发式搜索规则，如波束搜索（beam search）每个时间步t的