求解|破51项纪录的背后：华为云擎天架构调度求解引擎解读引擎|华为|约束|背后|纪录|架构

华为云擎天调度与算法团队近日刷新PDPTW问题榜单中51项算例的世界最好记录。该榜单自1990年起由科学工业研究院SINTEF发起并管理，该机构被认为是运筹优化领域中VRP问题的全球最权威评测平台。
问题介绍
PDPTW问题属于VRP系列问题，也是经典的NP难问题，已被广泛研究超过50年。与经典VRP问题相比，该问题扩展了更多的约束，求解难度也更高。 VRP系列问题，简单来讲，就是用来在图网络中寻找满足一系列约束情况下的最优路径问题。该系列问题在物流配送、航路规划、电路设计以及云计算等领域都有广泛应用。

文章插图
VRP问题示意图
VRP系列问题都属于典型的NP难约束优化问题。约束优化问题与工业场景优化关系非常密切，众多工业场景下的问题都可以建模为约束优化问题，如网络设计优化、码头作业调度、芯片设计布线、人员和时刻表排班、库存管理等。
什么是约束优化问题？
约束优化问题是一类数学最优化问题，它由目标函数以及与目标函数中的变量相关的约束条件两部分组成，优化过程则为在约束条件下最优化（最大化或最小化）目标函数。
太抽象？我们举个例子：
给定一组物品，每种物品都有自己的重量和价格，在限定总重量的情况下，我们如何选择才能使得物品的总价格最高？这就是经典的背包问题。从约束优化角度来看，目标函数就是选择物品使得总价值最高；约束是不能超过“限定的总重量”，此外，还有一个隐含约束：每个物品都是一个整体，不能切分。
在云场景下，我们同样面临着很多复杂的、大规模、多目标的NP难优化问题，如机型规划、弹性保障、资源/任务调度、资源整理、容量管理等，这些问题也可以建模为一个或多个约束优化问题的组合。背包问题和云上的虚拟机放置问题是同源问题，只是虚拟机放置问题的约束和目标会复杂得多。
求解这些约束优化问题有什么价值？
随着公有云规模越来越大，优化所能带来的价值也越来越高。单个云数据中心的物理主机规模可以达到百万数量级，云服务器规模可达数百万到千万台数量级。如果能够提升1%的资源分配率，这些资源就可以在高峰期为用户提供更强的弹性能力，为客户创造价值。
提升资源分配率仅仅是云场景优化问题中的冰山一角。这是一个庞大的系统层面的问题，其中包含了多种复杂的NP难约束优化问题。这些问题不仅出现在资源调度的层面，而是贯穿云资源的整个生命周期。
云上遇到的约束优化问题有多难？
云上面临的约束优化问题通常有规模大、约束复杂、多目标、NP-困难等特点。
随着问题规模的增大，求解该问题最优解的时间是非多项式级别（比如指数级）增长的，且是计算机无法承受的。
规模大
云上面临的约束优化问题往往规模非常大，决策变量可高达上亿规模，并且通常是离散的组合优化问题而不是单纯的线性规划问题。这么大规模的组合优化问题，求解难度非常高，即使使用号称业界速度最快的商用求解器Gurobi也是无法直接求解的。
约束多
公有云是一个复杂的系统，需要考虑很多复杂的实际约束。以资源调度场景为例，需要考虑的约束可能包括：NUMA结构问题，租户的亲和性与反亲和性、负载的亲和性与反亲和性、离线任务与在线任务的亲和性与反亲和性，生命周期的亲和性、机柜功率约束、故障域约束、网络QoS约束、散热约束、节省电力、SLA约束等等。如此多的约束会大大增加求解难度。
动态性
相较于企业私有云，公有云的客户对资源弹性诉求更高，公有云运营商需要面对突发流量峰谷时急速扩容，弹性调度资源。然而急速弹性会为资源的调度与经营带来高动态性，这意味着求解的状态变化很快，对算法求解时间的要求也更为苛刻，求解时间过长则结果无意义。同时，这种动态性及随机性，使得算法在对解的优度进行评估时，还需避免当前的优化目标对未来的决策产生负面影响。
此外，随着公有云发展，新增了分布式、边缘节点自治、突发型实例等特性，这些都让问题的难度指数级增加。
我们的解决方案：面向云场景的约束规划问题优化求解引擎
为了解决云上遇到的此类复杂的约束优化问题，尤其是资源规划与调度相关问题，华为云擎天架构调度与算法团队设计了面向云场景的约束规划问题优化求解引擎。
面向云场景的约束规划问题优化求解引擎的核心是基于元启发式搜索算法框架的，那么为什么我们选择元启发式搜索呢？