8-1 机器学习遇上运筹优化，助力企业降本增效：一种双层优化方法

核心观点与内容

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）。