基于图神经网络的组合优化与推理（JML 2023）（未完）
文章目录
- Abstract
- 1. Introduction
- 1.1机器学习面临哪些挑战？
- 1.2 GNN如何应对这些挑战？
- 1.3超越经典算法
- 1.4 本文工作
- 1.5 相关工作
- 1.6 大纲
- 2. Preliminaries
- 2.1 符号表示
- 2.2 组合优化
- 2.3 通用优化框架：整数线性规划（ILPs）、可满足性问题（SAT）和约束问题
- 2.3.1 整数线性规划和混合整数规划
- 2.3.2 SAT
- 2.3.3约束满足和约束优化问题
- 2.3.4解决CO问题
- 2.4 机器学习
- 2.5 图神经网络
- 3.GNNs 在组合优化中的应用：最新进展
- 3.1 在主要方面：寻找可行解
- 3.1.1 监督学习
- 3.1.2 无监督学习
- 3.1.3 强化学习在迭代解决方案构建中的应用
- 3.1.4 总结
- 3.2 在对偶方面：证明最优性
- 3.2.1 整数规划
- 3.2.2 逻辑求解
- 3.2.3 约束编程
- 3.2.4决策图
- 3.2.5总结
- 3.3逻辑推理
- 3.3.1 算法对齐
- 3.3.2前景和展望
Abstract
组合优化是运筹学和计算机科学中一项成熟的研究领域。迄今为止，其方法主要集中于单独解决问题实例，而忽略了这些问题在实际中往往源自相关的数据分布。然而，近年来，利用机器学习，尤其是图神经网络（GNN），已成为解决组合优化任务的关键手段，既可以直接作为求解器使用，也可以辅助精确求解器。GNN的归纳偏置能有效地编码组合和关系输入，得益于其对置换的不变性以及对输入稀疏性的敏感性。本文对该新兴领域的最新关键进展进行了概念性回顾，旨在为优化和机器学习研究者提供指导。
1. Introduction
组合优化（CO）已发展为一个跨学科领域，涵盖优化、运筹学、离散数学和计算机科学，并在诸如车辆路径规划或调度等实际应用中起着关键作用（参见Korte和Vygen，2012的概述）。直观上，组合优化处理的问题包括通过从有限集合中选择一个子集来优化成本（或目标）函数，这一过程在解空间中编码了约束。尽管由于其离散、非凸的特性，使组合优化问题在复杂性理论上通常较难