仅需15秒即可搞定随机规划问题，速度比传统方法快了1440倍！

中科院自动化研究所的新研究，利用GCN在此类问题上取得了新突破，论文已入选AI顶会ICML 2024。

这意味着，在条件不确定的情况下，也能实现高效决策。

不确定性下的决策是一类重要的决策问题，它要求决策者能够充分考虑到所有的随机情况并做出最合理的决策。

在数学领域，一种常用的解决方式是随机规划，也就是把随机变量包含在数学规划模型当中。

其中，两阶段随机规划（Two-Stage Stochastic Programming, 2SP）作为建模此类决策问题的有效方法，应用十分广泛。

中科院自动化所的这项成果——HGCN2SP模型（HGCN代表分层图卷积网络），正是将2SP方法与图卷积网络结合，利用模型更高效地实现了此类问题求解。

论文第一作者为该所博士生吴洋，张一帆研究员是通讯作者。

什么是两阶段随机规划

随机规划的基本思想是将问题的未来可能情况转化为若干个样本场景，然后对每个样本场景进行优化，最后综合所有场景的优化结果来指导当前决策。

其应用领域包括供应链管理、金融投资、能源调度、灾害应急管理等。

而两阶段随机规划，顾名思义就是把这个过程分成了两个阶段。

具体来说，这两个阶段分别要做出宏观和微观决策，以最小化总成本或最大化总收益。

第一阶段的决策是在不确定性显现之前做出的，目标是优化初始决策以适应未来可能发生的多种情况。

第二阶段的决策是在不确定性显现之后进行的，根据第一阶段的决策和实际发生的情况进行调整，以优化整体结果。

通过2SP模型，决策者需要在决策过程中充分考虑可能发生的不同场景的影响，从而提高决策的鲁棒性和灵活性，做出更为科学和高效的决策。

举个例子，假设我们要从10个候选地点中选择一些建立仓库，以满足周边20个区域的需求。

第一阶段需要决策的是，在这10个候选地点中应该选择哪些；

第二阶段则要确定仓库和区域间的配送关系，此时的决策变量数量多达200个（即仓库i是否配送区域j）。

△图像由DALL·E生成

数学上，2SP问题通常表示为：

其中，Q(x,ξ)表示在给定第一阶段决策x和场景ξ下的第二阶段优化问题，其形式为：

在实际的求解中，一般会采样N个场景计算对应的Q值来近似期望。

显然N越大则近似值越可信，但随着场景数量的增加，问题规模迅速膨胀，会导致求解时间大幅提高。

还是用这个仓库选址的问题来说明，为了能做出更好的选址决策，需要将需求、天气、人流、交通等不确定因素考虑在内，而每一个因素的变化都对应着一个场景。

这意味着，需要广泛采样N个不同场景来尽可能模拟真实情况。这时，第二阶段总决策变量数会高达200N个，使得求解时间极为漫长。

事实上，当N取500时，即使使用最先进的商用求解器Gurobi，也至少需要6个小时才能做出最优的决策。

传统方法通常利用随机采样或聚类技术来挑选少量的场景（如10或20）以进行近似求解，虽然减少了时间，但得到的决策质量却往往不理想。

基于此，也就有了HGCN2SP模型的设计思路——在减少采样场景个数的同时，尽可能近似得到准确结果。

用图卷积网络解决2SP问题

研究团队针对两阶段随机规划问题求解，提出了基于层次化图卷积网络的HGCN2SP模型。

具体的在算法设计方面，团队通过构建层次图来表征2SP问题，其中底层的图用来表征每个场景的特性，而顶层的图则用于表征场景之间的关系。

然后，再利用层次化图卷积网络（HGCN），分别挖掘底层场景子图的嵌入信息和顶层场景空间的结构信息，以提取场景表示。

基于注意力机制的解码器被用于按序挑选场景，不仅能找到具有代表性的场景来简化问题，还可以通过优化场景的排列顺序来改善单纯形法求解问题时对初始基的选取，进而显著提升求解时间。

△HGCN2SP模型框架

团队还结合强化学习（RL），综合考察决策质量和求解时间来优化模型参数，显著提高了问题求解的效率和质量。

在上述的仓库选址问题中，尽管HGCN2SP只选取了10个场景，但其决策结果与Gurobi求解器用6个小时做出的决策差距仅为1.7%，而求解时间仅为15秒，相当于速度提升了1440倍，充分体现了该方法的有效性。

另外，在网络设计问题（Network Design Problem, NDP）的实验中，HGCN2SP仅用已有方法不到一半的时间得到了相近的决策效果。

尤其在大规模实例和大量场景情况下，HGCN2SP依然保持了强大的泛化能力。

HGCN2SP的提出为解决复杂的2SP问题提供了一种新的思路和工具，具有广泛的应用前景。

研究团队计划进一步优化模型，降低训练成本，并探索其在更多实际问题中的应用。

论文地址：

https://openreview.net/forum?id=8onaVSFTEj

文章来自于微信公众号量子位 作者中科院自动化研究所