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

数智驱动的图上组合优化问题学习型求解技术范长俊国防科技大学fanchangjun@nudt.edu.cn目录图上的组合优化问题人工智能求解框架开源框架设计目录图上的组合优化问题人工智能求解框架开源框架设计min()..()0fxstgxxD组合优化（combinatorialoptimization，CO)是通过对数学方法的研究，寻找离散事件的最优编排、分组、次序或筛选，所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等领域。该问题可用数学模型描述为：其中D表示有限个点组成的集合（定义域），f为目标函数，F={x|x∈D,g(x)≥0}为可行域引自《王建江，大规模组合优化问题求解方法与应用，智慧调度网络公益系列讲座》图上的组合优化问题图上的组合优化（graphcombinatorialoptimization，GCO)：离散事件是点和边的集合，选择最优的节点集合或边的集合最优化任务目标。图上的组合优化问题最小节点覆盖问题：找到最少的节点覆盖全部的边.,,,1,},1,0{},,2,1{,2||2,1||,,1,1,,1,1..min,11jinjixnSnSSxnjxnixtsxdijSjiijniijnjijnjiijij目标函数约束条件1. 旅行商问题（TSP）例子一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为𝑑𝑖𝑗，如何选择一条道路使得商人每个城市正好走一遍后回到起点且所走路径最短。图上的组合优化问题(,)uvE(,)GVE2. 最小节点覆盖问题（MVC）给定无向图，顶点集为V，边集为E，它的一个最小节点覆盖V′是顶点集V的一个子集，使得若，则或'uV'vV'..1,(,){0,1},jjVijjminxstxxijExjV例子目标函数约束条件图上的组合优化问题3. 最大割问题（Max-Cut）给定带权图，找到节点子集，使得割集中的边的权重之和最大，其中割集C 中的边满足(,,)GVEW(,)max(2)().. 1,, {0,1},ijijijijEijiwxxxxstxxijVxiVSVCE(,)uv,uSvS例子目标函数约束条件图上的组合优化问题4.图着色问题5.最大独立集问题6.影响力最