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

 

什么是约束优化问题？

 

约束优化问题是一类数学最优化问题，它由目标函数以及与目标函数中的变量相关的约束条件两部分组成，优化过程则为在约束条件下最优化（最大化或最小化）目标函数。

 

太抽象？我们举个例子：

 

给定一组物品，每种物品都有自己的重量和价格，在限定总重量的情况下，我们如何选择才能使得物品的总价格最高？这就是经典的背包问题。从约束优化角度来看，目标函数就是选择物品使得总价值最高；约束是不能超过“限定的总重量”，此外，还有一个隐含约束：每个物品都是一个整体，不能切分。

 

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

 

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

 

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

 

提升资源分配率仅仅是云场景优化问题中的冰山一角。这是一个庞大的系统层面的问题，其中包含了多种复杂的NP难约束优化问题。这些问题不仅出现在资源调度的层面，而是贯穿云资源的整个生命周期。

 

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

 

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

 

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

 

规模大

 

云上面临的约束优化问题往往规模非常大，决策变量可高达上亿规模，并且通常是离散的组合优化问题而不是单纯的线性规划问题。这么大规模的组合优化问题，求解难度非常高，即使使用号称业界速度最快的商用求解器Gurobi也是无法直接求解的。

 

约束多

 

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