破51项国际榜单纪录！解读华为云擎天架构调度求解引擎
摘要：华为云擎天调度与算法团队近日刷新PDPTW问题榜单中51项算例的世界最好记录。
华为云擎天调度与算法团队近日刷新PDPTW问题榜单中51项算例的世界最好记录。该榜单自1990年起由科学工业研究院SINTEF发起并管理，该机构被认为是运筹优化领域中VRP问题的全球最权威评测平台。
问题介绍
PDPTW问题属于VRP系列问题，也是经典的NP难问题，已被广泛研究超过50年。 与经典VRP问题相比，该问题扩展了更多的约束，求解难度也更高。 VRP系列问题，简单来讲，就是用来在图网络中寻找满足一系列约束情况下的最优路径问题。该系列问题在物流配送、航路规划、电路设计以及云计算等领域都有广泛应用。
VRP问题示意图
VRP系列问题都属于典型的NP难约束优化问题。 约束优化问题与工业场景优化关系非常密切，众多工业场景下的问题都可以建模为约束优化问题，如网络设计优化、码头作业调度、芯片设计布线、人员和时刻表排班、库存管理等。
什么是约束优化问题？
约束优化问题是一类数学最优化问题，它由目标函数以及与目标函数中的变量相关的约束条件两部分组成，优化过程则为在约束条件下最优化（最大化或最小化）目标函数。
太抽象？我们举个例子：
- 给定一组物品，每种物品都有自己的重量和价格，在限定总重量的情况下，我们如何选择才能使得物品的总价格最高？这就是经典的背包问题。从约束优化角度来看，目标函数就是选择物品使得总价值最高；约束是不能超过“限定的总重量”，此外，还有一个隐含约束：每个物品都是一个整体，不能切分。
- 在云场景下，我们同样面临着很多复杂的、大规模、多目标的NP难优化问题，如机型规划、弹性保障、资源/任务调度、资源整理、容量管理等，这些问题也可以建模为一个或多个约束优化问题的组合。背包问题和云上的虚拟机放置问题是同源问题，只是虚拟机放置问题的约束和目标会复杂得多。
求解这些约束优化问题有什么价值？
随着公有云规模越来越大，优化所能带来的价值也越来越高。单个云数据中心的物理主机规模可以达到百万数量级，云服务器规模可达数百万到千万台数量级。如果能够提升1%的资源分配率，这些资源就可以在高峰期为用户提供更强的弹性能力，为客户创造价值。
提升资源分配率仅仅是云场景优化问题中的冰山一角。这是一个庞大的系统层面的问题，其中包含了多种复杂的NP难约束优化问题。这些问题不仅出现在资源调度的层面，而是贯穿云资源的整个生命周期。
云上遇到的约束优化问题有多难？
云上面临的约束优化问题通常有规模大、约束复杂、多目标、NP-困难等特点。
随着问题规模的增大，求解该问题最优解的时间是非多项式级别（比如指数级）增长的，且是计算机无法承受的。
- 规模大
云上面临的约束优化问题往往规模非常大，决策变量可高达上亿规模，并且通常是离散的组合优化问题而不是单纯的线性规划问题。这么大规模的组合优化问题，求解难度非常高，即使使用号称业界速度最快的商用求解器Gurobi也是无法直接求解的。
- 约束多
公有云是一个复杂的系统，需要考虑很多复杂的实际约束。以资源调度场景为例，需要考虑的约束可能包括：NUMA结构问题，租户的亲和性与反亲和性、负载的亲和性与反亲和性、离线任务与在线任务的亲和性与反亲和性，生命周期的亲和性、机柜功率约束、故障域约束、网络QoS约束、散热约束、节省电力、SLA约束等等。如此多的约束会大大增加求解难度。
- 动态性
相较于企业私有云，公有云的客户对资源弹性诉求更高，公有云运营商需要面对突发流量峰谷时急速扩容，弹性调度资源。然而急速弹性会为资源的调度与经营带来高动态性，这意味着求解的状态变化很快，对算法求解时间的要求也更为苛刻，求解时间过长则结果无意义。同时，这种动态性及随机性，使得算法在对解的优度进行评估时，还需避免当前的优化目标对未来的决策产生负面影响。
此外，随着公有云发展，新增了分布式、边缘节点自治、突发型实例等特性，这些都让问题的难度指数级增加。
我们的解决方案：面向云场景的约束规划问题优化求解引擎
为了解决云上遇到的此类复杂的约束优化问题，尤其是资源规划与调度相关问题，华为云擎天架构调度与算法团队设计了面向云场景的约束规划问题优化求解引擎。
面向云场景的约束规划问题优化求解引擎的核心是基于元启发式搜索算法框架的，那么为什么我们选择元启发式搜索呢？
在计算复杂性和最优化领域，有个“没有免费的午餐（NFL，No Free Lunch）”理论[1]，即对于优化问题，在有限的搜索空间中，当且仅当我们指定了具体的问题的时候，我们才能说一个优化方法要优于另一种优化方法。或者说，理论上，并不存在一个在所有问题上都能获得最优结果的算法。
常用求解NP难约束优化问题的方法，大致可分为精确算法和启发式算法。
精确算法，如Branch-and-cut, Branch-and-bound 等，可以在理论上保证算法朝最优解收敛，但是通常适用于问题规模较小的情况。 对于云上这么大规模（上亿决策变量）与复杂约束的问题，求解时长与资源消耗都是计算机无法接受的，因此并不适合在云场景下使用。
启发式算法，又可以分为简单启发式和元启发式。二者最大的区别就是，简单启发式算法更多的是问题相关的，而元启发式算法更多的是“问题无关”的。或者说，简单启发式算法对于A问题有效，但是对于B问题可能完全无法使用。 但是，元启发式是相对“通用”的搜索框架，几乎可应用到所有的优化问题上面。
这么听起来，元启发式算法是不是违反了NFL理论，在使用一个算法解决所有问题？
并不是。元启发式算法内部一般包含两种关键机制，就是搜索集中性（ intensification）的机制和搜索的疏散性（diversification）的机制。前者负责搜索当前解的周围区域，而后者负责逃出局部优陷阱去更有“前途”的搜索区域。而一个完善的搜索策略就是要做二者的折中或者平衡，这里并没有一个“完美策略”可以使得该策略在所有优化问题上的性能都最好，所以也恰恰是符合NFL理论的。
在决定采用什么求解算法之前，我们再来看看云上面临的最优化问题的两个特点：
- 云上面临的是不止一个而是一系列的优化问题，问题之间可能具有一定的相似性和关联性。 比如在线资源调度、资源容量管理、资源碎片整理等，都以云资源为核心且具有相似的模型和约束。
- 云上的绝大多数优化问题并不要求必须得全局最优解，而是要求在限定的时间内，给出尽可能高质量的解。
结合NFL理论、元启发式算法的特点以及云上优化问题的特点，我们采用基于元启发式的求解框架就顺理成章了。 元启发式算法可以在限定时间内求解问题的“足够好的解”，同时，使用元启发式的问题无关性来适应多种多样的优化的问题。另外，又由于云上系列问题的相似性和关联性，针对某个问题的优化策略很可能也会在其他相近或者关联问题上生效，多个问题又往往可以联合优化。
当然并不是我们只要使用了元启发式框架整个引擎和算法就万事大吉了，求解框架只是第一步。复杂问题的建模、求解的算法集、策略集、参数调教都是我们的重点工作。尤其建模更是重中之重，它关系到问题的复杂度以及解是不是可以被应用到实际的生产环境当中去。我们还尝试引入多种元启发式算法框架，引入和设计多种集中性和疏散性策略包括文献中最好的方法以及团队创新的方法，并尝试创新的组合以及参数优化，包括引导式局部搜索、种群管理甚至是基于机器学习的手段，来丰富我们的策略，使得求解引擎能够对云上一系列的问题生效。比如，新的引导式局部搜索和种群管理策略就是我们刷新本次PDPTW记录的两项关键技术。此外，我们采用了并行化、参数自适应等多种技术来进一步改善我们求解引擎的性能表现和适应能力。
至此，我们取得了一些优秀成果，包括此前获得GECCO2020 OCP&USCP竞赛冠军，以及此次刷新51项PDPTW问题榜单。更为重要的是，面向云场景的约束规划问题优化求解引擎作为华为云擎天架构的一部分，为华为云的资源规划、资源经营保障、资源弹性能力等方面提供了强大的优化算法支持，最终客户也会从弹性能力保障、服务质量等方面获益。在探索云上最优化问题的道路上，我们并非闭门造车，华为云联合ICPC组委会将在12月12日-12月20日在线举办ICPC 2020 NERC华为挑战赛[2]，以云上调度挑战问题为题，邀请全球算法精英一同探索云上最优解之道。
参考
-
https://ieeexplore.ieee.org/document/585893
-
https://codeforces.com/nerc2020