核心观点与内容
1. 优化问题概述
- 优化定义：优化是指充分利用资源或情况，使其达到最佳效果（牛津英语词典）。
- 凸优化：具有强通用求解器，许多问题可多项式时间解决。
- 非凸优化：无通用求解器，通常指数时间复杂度。
- 组合优化：在离散变量上最小化目标函数，满足约束条件，如0/1背包问题、路径规划等。
2. 研究问题
- 研究问题：解决图上的组合优化问题，包括图编辑距离、哈密顿回路、DAG调度等。
- 问题特点：组合优化问题具有指数级最坏复杂度（NP完全或NP难），但实际中类似问题重复出现，数据驱动方法具有吸引力。
3. 现有方法与挑战
- 单层优化方法：通过强化学习（RL）解决，但存在动作序列过长、稀疏奖励、模型容量需求高等问题。
- 改进思路：通过修改问题结构（如添加边）辅助求解，但需手动设计模型，工程难度大。
4. 双层优化方法
- 双层优化框架：引入上层优化（优化图结构）和下层优化（传统方法求解）。
- 具体实现：上层通过RL优化图结构，下层通过经典方法求解，无需扩大可行域。
- 优势：模型容量需求低，通用框架适用于多种问题，收敛性更好，工程难度更低。
5. 实验结果
- 实验问题：DAG调度、图编辑距离、哈密顿回路。
- 结果：双层方法优于无学习基线和学习基线，可泛化至不同训练/测试规模。
- 对比：单层方法需更高模型容量、手动设计、收敛困难，双层方法更高效。
6. 应用案例
- 计算机视觉：图像关键点匹配（Pascal VOC）。
- 隐私机器学习：联邦学习中的神经网络对齐（CIFAR10）。
- 金融：联合资产价格预测与投资组合优化（标普500）。
7. 未来方向
- 开放问题：如何优化亿规模图？如何构建联合预测与优化的通用框架？如何从样本中优化？
8. 代码与资源
- 代码：PPO-BiHyb（https://github.com/Thinklab-SJTU/PPO-BiHyb）。
- 论文集合：机器学习与组合优化论文（https://github.com/Thinklab-SJTU/awesome-ml4co）。
- 深度图匹配模型：ThinkMatch（https://github.com/Thinklab-SJTU/ThinkMatch）。
- 图匹配工具：pygmtools（支持PyTorch和NumPy）。
