常见组合优化问题与求解方法简单介绍

Towers of Hanoi 、Integer Programming、Minimum Dominating Set (MDS)、Maximum Common Subgraph (MCS) 、Maximum Weight Matching (MWM)、Boolean Satisfiability (SAT)、Graph Coloring、Maximum Clique (MC)、Maximum Independent Set (MIS)、Minimum Vertex Cover (MVC)、Maximum Cut(MaxCut) Traveling Salesman Problem(TSP)、Knapsack Problem、Bin Packing Problem(BPP)、Job Scheduling Problem (JSP)、Vehicle Routing Problem (VRP)、Global Routing、Highest Safe Rung (HSR)……

（《Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time》）

欲快速了解 TSP 问题求解的来龙去脉，请研读https://arxiv.org/pdf/1906.01227.pdf中的相关工作。

（关于TSP问题，网友的其他评论：

“我去年做的就是车间调度，老实说感觉没太大意思了，都在尝试改进一些搜索机制，领域结构，编解码等，没有什么特别大的创新，最多是在以个位数的优势刷新下界，求得两三个新下界就可以发篇paper。最近组内开始有把强化学习，深度强化学习和启发式算法结合起来，但是只能说在方法有些创新，对于刷新下界的效果一般。而且强化学习也就用在初始阶段选参数选规则，真正参与到搜索过程中没有。”

评论2：

“tsp问题中启发式算法我要推LKH，比已知所有算法好很多，只是无法保证是最优解，以后发展趋势是启发式与精确式结合，另一个比较成功的算法是mtsp问题下的文化基因算法，这些算法讨论的规模都上千了”

来源：现在研究强化学习+组合优化的paper不少了（几十篇+），但方法似乎就这么几种，对此您怎么看？））

? 精确方法

精确方法主要是分枝定界法。精确方法能找到全局最优解但由于不是多项式时间的求解方法，故而往往在大 规模实例上不可行。

? 近似方法

参考自【学界】整数规划精确算法/近似算法/(元)启发算法/神经网络反向传播等算法的区别与关联 - 留德华叫兽的文章 - 知乎 https://zhuanlan.zhihu.com/p/30140008

其次求解组合优化问题时，近似算法也经常用到，它们本质上通常是贪心算法，而且通常都是多项式时间的 算法。

与一般的贪心算法不同，它们通过巧妙的算法设计，所求解可被严格证明比全局最优解差 A 倍（A 被称为近 似系数）。

? 启发式方法

发式算法通常是以问题为导向的，也就是说，没有一个通用的框架，每个不同的问题通常设计一个不同的 启发式算法，启发式算法通常被用来解组合优化问题。

启发式算法具有如下特征：

– 通常依赖于人工选取 heuristics；

– 难以调整何时何地应用 heuristics；

– 一般只能求得局部最优解。

启发式算法的设计过程需要特殊的领域知识，并可能需要反复试验来调整算法。实际上，每当问题设置变化 时，算法通常需要被重新修订，这需要我们重新优化系统，故而启发式算法在这时变得不切实际。

? 元启发算法

参考自【学界】整数规划精确算法/近似算法/(元)启发算法/神经网络反向传播等算法的区别与关联 - 留德华叫兽的文章 - 知乎 https://zhuanlan.zhihu.com/p/30140008

和一般的启发式算法不一样，元启发算法如遗传算法、蚁群算法、进化算法、智能算法针对普遍的问题。可 以将它当作一个黑箱子对几乎任何问题适用。元启发算法通常需要给定初始解；另外，算法不能保证在多项 式时间收敛，但我们常常可以控制算法迭代次数。

我们可以将不同的元启发算法视作一个个基本框架，这个框架下有着不同的子算法。值得注意的是，元启发 算法 (如蒙特卡洛法) 通常设计了跳出局部最优解的方法（虽然不能保证在有限时间内收敛到全局最优点）， 而启发式算法遇到了局部最优点则很可能停止搜索。

? 神经网络

神经网络通过构造更简单的函数来构建大型参数逼近器，它在具有大量数据点的高维空间中表现突出，其良 好的结构设计可能有助于提升 COP 求解的泛化性。近年来有研究者用序列到序列的结构求解 TSP 问题，用 端到端或图神经网络提取 COP 的特征后结合 RL、本地搜索等方法求解不同类型的 COP。

然而，COP 可能带有不少约束条件，而神经网络学习复杂约束的能力并未得到公开认可；另外，COP 大多 不可微分，神经网络直接反向传播可能会造成不好的结构。探索可微分学习的规划决策与逻辑推理机制对于 神经网络端到端求解 COP 十分重要。

? RL 方法

– 许多 COP 会涉及或可以转化成序列决策问题，例如 TSP 问题就是决定以怎样的顺序访问每一个城市， 加工车间调度问题就是决定以怎样的顺序在机器上加工工件。而 RL 天生就是用来进行序列决策的方案， 那么 COP 里的序列决策问题也许完全可用 RL 来直接求解，其主要难点是 MDP 五元组的定义。

– RL 方法不必然需要历史数据且智能体与环境交互时会不断产生新数据，所以我们可将 RL 方法与监督 学习结合以促进监督学习的训练，或 RL 预训练与本地搜索结合以提升单独使用搜索方法的性能。

– RL 方法在未知环境中平衡探索与利用，以更快更好地熟悉环境并做出决策。所以我们可以利用与环境 不断交互并学习的 RL 方法来指导分枝定界方法，用 RL 决定分支策略。