打破 51 项记录，解密华为云运筹优化技术实践

华为云调度与算法团队近日刷新了 PDPTW 问题榜单中 51 项算例的世界最好记录。此榜单由欧洲 SINTEF 机构自 1999 年就发起并管理，被认为是运筹优化领域中 VRP 相关问题的全球最权威的评测平台。

问题介绍

PDPTW 问题属于 VRP 系列问题之一，也是经典的 NP 难问题，已经被广泛研究超过 50 年。 与经典 VRP 问题相比，该问题扩展了更多的约束，求解难度也更高。

简单来讲， VRP 系列问题就是用来在图网络中寻找满足一系列约束情况下的最优路径问题。该系列问题在物流配送、航路规划、电路设计以及云计算等领域都有广泛应用。

VRP 系列问题都属于典型的 NP 难约束优化问题。 约束优化问题与工业场景优化关系非常密切，众多的工业场景下的问题都可以建模为约束优化问题，比如典型场景有，网络设计优化、码头作业调度、芯 片设计布线、人员和时刻表排班、库存管理等等。

在云场景下，我们同样面临着很多复杂的、大规模、 多目标的 NP 难优化问题，比如，机型规划、弹性保障、资源/任务调度、资源整理、容量管理等，这些问题也可以建模为一个或多个约束优化问题的组合。

什么是约束优化问题？

约束优化问题是一类数学最优化问题，它由目标函数以及与目标函数中的变量相关的约束条件两部分组成，优化过程则为在约束条件下最优化（最大化或最小化）目标函数。觉得太抽象？我举个例子：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。这个问题就是经典的背包问题，从约束优化角度来看，目标函数就是选择物品使得总价值最高；约束是不能超过“限定的总重量”，此外，还有一个隐含约束是每个物品都是一个整体，不能切分。背包问题和云上的虚拟机放置问题是同源问题，只是虚拟机放置问题的约束和目标会复杂的多。

求解这些约束优化问题有什么价值？

随着公有云规模越来越大，优化所能带来的价值也越来越高。单个云数据中心的物理主机规模可以达到 10 万数量级，云服务器规模可达数十万到百万台数量级。如果能够降低 1%的资源碎片率，这些资源就可以在高峰期为用户提供更强的弹性能力，为客户创造价值。

什么是资源碎片？

公有云的资源池有点像电脑硬盘，因为资源是不断动态分配与回收的， 且资源的规格种类又是多样的，随着时间的累积，资源池也可能会像硬盘一样产生无法被再次分配的碎片。举个简单的例子，某台主机上还有剩余的 2 核 CPU 资源，但是内存已经被分配完毕了，那么这 2 核的 CPU 在有新的内存释放之前就无法被分配和售卖了，这部分 CPU 就是碎片。

当然降低资源的分配碎片仅仅是云场景下约束优化问题的一个相对简单的例子。更复杂的，如提高资源的实际利用率的同时按照 SLA 严格保障用户的服务质量等。这是一个庞大的系统层面的问题，其中就包含 了亟待解决的多种复杂的 NP 难约束优化问题。这些问题不仅仅出现在资源调度的层面，而是贯穿整 个云资源的生命周期，如物理机型的规划、云服务器规格的定义、容量管理、资源调度、任务调度、站 点选址、甚至是定价等等。 建模与求解此类工业级复杂约束优化问题一直是学术界和工业界共同的挑战和目标。

云上遇到的约束优化问题有多难？

云上面临的约束优化问题通常有规模大、约束复杂、多目标、NP-困难等特点。

随着问题规模的增大，求解该问题最优解的时间是非多项式级别（比如指数级）增长的，而这是计算机无法承受的。

• 规模大

正如前文所讲，由于云本身的规模越来越大，单个云数据中心的物理主机规模可以达到 10 万数量级，云服务器规模可达数十万到百万台数量级。 因此，云上面临的约束优化问题往往规模非常大，决策变量可高达上亿规模，并且通常是离散的组合优化问题而不是单纯的线性规划问题。

了解优化领域的同学应该知道，这么大规模的组合优化问题求解难度是非常高的，这种情况下即使使用号称业界速度最快的商用求解器 Gurobi 也无法直接求解。

对于规模问题，我还是举个例子：在仅考虑容量约束的虚拟机最优分配问题场景中，假设虚拟机规模 为 30 万，主机规模为 10 万的情况下，搜索空间约 10^1500000。

• 约束多

公有云是一个复杂的系统，需要考虑很多复杂的实际约束。我还是以资源调度场景为例，需要考虑的约束可能包括：NUMA 结构问题（尤其是在 Kunpeng    CPU 场景下，NUMA 结构更加复杂），租户的亲和性与反亲和性、负载的亲和性与反亲和性、离线任务与在线任务的亲和性与反亲和性，生命周期 的亲和性、机柜功率约束、故障域约束、网络 QoS 约束、散热约束、节省电力、SLA 约束等等。如此复杂的约束极大增大了求解的困难度。

• 动态性

公有云相对企业自建的数据中心或者私有云的一个优势是，可以提供极致的弹性资源能力，但弹性给资源的调度与经营带来的就是高动态性，这意味着求解的状态变化很快，时间如果太久，求的结果就没有意义了。另外这种动态性以及随机性使得对解的优度的评估还需要考虑对未来的影响，避免陷入到自我矛盾的境地。

• 其他特点

公有云还有很多其他的特点，比如分布式、边缘节点自治、突发型实例等都让问题的难度呈指数级增加。

面向云场景的约束规划问题优化求解引擎

为了解决云上遇到的此类复杂的约束优化问题，尤其是云场景下资源规划与调度相关问题，华为云调度 与算法团队设计了面向云场景的约束规划问题优化求解引擎。

该优化求解引擎当前采用了基于元启发式搜索算法的求解框架，整合了包括自适应大规模邻域搜索、禁忌搜索、引导式局部搜索、创新的种群管理方法以及基于统计模型的禁忌表策略等方法，包含专门设计和优化的一系列核心算法和策略组件，

而且，针对云上大规模甚至是超大规模问题场景做了深度优化。本次 PDPTW 问题的解也是使用该引擎获得的。

面向云场景的约束规划问题优化求解引擎的核心是基于元启发式搜索算法框架，那么我们为什么选择元启发式搜索呢？

在计算复杂性和最优化领域，有一个理论叫做“没有免费的午餐理论（NFL，No Free Lunch）”， 这个理论的细节可以参考这篇论文https://ieeexplore.ieee.or/document/585893。

总结起来，NFL 理论是指，对于优化问题，在有限的搜索空间中，当且仅当指定了具体问题时，才能说一个优化方法优于另一种优化方法。或者说，理论上，并不存在一个**“一劳永逸”**的算法在所有的问题上都能获得最优的结果。

那么，我们再看常用的求解 NP 难约束优化问题的方法，大致可以分为精确算法和启发式算法。

精确算法，如 Branch-and-cut, Branch-and-bound 等，可以在理论上保证算法朝最优解收敛，但是通常适用于问题规模较小的情况。较大的规模问题，如超过 VRP 问题超过 200 节点，精确算法一般就无法在可接受的时间内给出结果了。 对于云上这么大规模（上亿决策变量）与复杂约束的问题，求解时长与资源消耗都是计算机完全无法接受的，因此，一般来讲并不合适在云场景下使用。

启发式算法，对于无法使用精确算法求得最优解的大规模甚至是超大规模问题，典型的场景当然就包括 云上面临的这些优化问题，研究者尝试使用一些“技巧”来求得“足够好的解”，典型的就是启发式类的算法，又可以分为简单启发式和元启发式。

二者最大的区别就是，简单启发式算法更多是问题相关， 而元启发式算法更多的是“问题无关”的。或者说，简单启发式算法对于 A 问题有效，但对于 B 问题可能完全无法使用。 但，元启发式是相对“通用”的搜索框架，可以应用到几乎所有的优化问题上面。

这样看起来，元启发式算法是不是违反了 NFL 理论，在使用一个算法解决所有问题？

其实不并不是的，元启发式算法内部一般包含两种关键机制，就是搜索集中性（  intensification）的机制和搜索的疏散性（diversification）的机制。

前者负责搜索当前解的周围区域，而后者负责逃出局部优陷阱去更有“前途”的搜索区域。而一个搜索策略就是要做二者的折中或者平衡，这里并没有一个“完美策略”可以  使得该策略在所有优化问题上的性能都最好，所以也恰恰是符合 NFL 理论的。

那么，在决定采用什么求解算法之前，再来看看云上面临的最优化问题的两个特点：

1、云上面临的不止是一个而是一系列的优化问题，问题之间可能具有一定的相似性和关联性。 如在线资源调度、资源容量管理、资源碎片整理等，都以云资源为核心且具有相似的模型和约束。

2、云上的绝大多数优化问题并不要求必须得全局最优解，而是要求在限定的时间内，给出尽可能高质量的解。

结合 NFL 理论、元启发式算法的特点以及云上优化问题的特点，我们采用基于元启发式的求解框架就顺理成章了。

元启发式算法可以在限定时间内求解问题的“足够好的解”，同时，使用元启发式的问题无关性来适应多种多样的优化问题。另外，又由于这云上系列问题的相似性和关联性，针对某个问题的优化策略很可能也会在其他相近或者关联问题上生效，多个问题有往往可以联合优化。

当然并不是只要使用了元启发式框架，整个引擎和算法就万事大吉了，求解框架只是第一步。

求解 的算法集、策略集、参数调教都是我们的重点工作。我们尝试引入多种元启发式算法框架，引入和设计多种集中性和疏散性策略包括文献中最好的方法以及团队创新方法，并尝试创新的组合以及参数优化， 包括引导式局部搜索、种群管理甚至是基于机器学习的手段，来丰富策略，使得求解引擎能够对云上一系列的问题生效。比如，创新的引导式局部搜索和种群管理策略就是刷新本次 PDPTW 记录  的两项关键技术。

此外，我们采用了并行化、参数自适应等多种技术来进一步改善求解引擎的性能表现和适应能力。到目前为止，我们取得了一些成果，如本次刷新 PDPTW 记录，和获得 GECCO2020 OCP&USCP 竞赛冠军，当然最重要的是，它为用户带去了价值。

面向云场景的约束规划问题优化求解引擎作为华为云擎天架构的一部分，为华为云的资源规划、资源经营保障、资源弹性能力等提供了强大的优化算法支持，最终客户也会从弹性能力保障、服务质量等方面获益。

参考链接：

1、https://ieeexplore.ieee.org/document/585893

2、https://bbs.huaweicloud.com/blogs/175251