摘要：华为云擎天调度与算法团队近日刷新 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）”实践，即 对于优化问题，在无限的搜寻空间中，当且仅当咱们指定了具体的问题的时候，咱们能力说一个优化办法要优于另一种优化办法。或者说，实践上，并不存在一个在所有问题上都能取得最优后果的算法。
罕用求解 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 华为挑战赛，以云上调度挑战问题为题，邀请寰球算法精英一起摸索云上最优解之道。
参考
- https://ieeexplore.ieee.org/d…
- https://codeforces.com/nerc20…://bbs.huaweicloud.com/blogs/175251
点击关注，第一工夫理解华为云陈腐技术~