僅需15秒即可搞定隨機(jī)規(guī)劃問(wèn)題，速度比傳統(tǒng)方法快了1440倍！

中科院自動(dòng)化研究所的新研究，利用GCN在此類問(wèn)題上取得了新突破，論文已入選AI頂會(huì)ICML 2024。

這意味著，在條件不確定的情況下，也能實(shí)現(xiàn)高效決策。

不確定性下的決策是一類重要的決策問(wèn)題，它要求決策者能夠充分考慮到所有的隨機(jī)情況并做出最合理的決策。

在數(shù)學(xué)領(lǐng)域，一種常用的解決方式是隨機(jī)規(guī)劃，也就是把隨機(jī)變量包含在數(shù)學(xué)規(guī)劃模型當(dāng)中。

其中，兩階段隨機(jī)規(guī)劃（Two-Stage Stochastic Programming, 2SP）作為建模此類決策問(wèn)題的有效方法，應(yīng)用十分廣泛。

中科院自動(dòng)化所的這項(xiàng)成果——HGCN2SP模型（HGCN代表分層圖卷積網(wǎng)絡(luò)），正是將2SP方法與圖卷積網(wǎng)絡(luò)結(jié)合，利用模型更高效地實(shí)現(xiàn)了此類問(wèn)題求解。

論文第一作者為該所博士生吳洋，張一帆研究員是通訊作者。

什么是兩階段隨機(jī)規(guī)劃

隨機(jī)規(guī)劃的基本思想是將問(wèn)題的未來(lái)可能情況轉(zhuǎn)化為若干個(gè)樣本場(chǎng)景，然后對(duì)每個(gè)樣本場(chǎng)景進(jìn)行優(yōu)化，最后綜合所有場(chǎng)景的優(yōu)化結(jié)果來(lái)指導(dǎo)當(dāng)前決策。

其應(yīng)用領(lǐng)域包括供應(yīng)鏈管理、金融投資、能源調(diào)度、災(zāi)害應(yīng)急管理等。

而兩階段隨機(jī)規(guī)劃，顧名思義就是把這個(gè)過(guò)程分成了兩個(gè)階段。

具體來(lái)說(shuō)，這兩個(gè)階段分別要做出宏觀和微觀決策，以最小化總成本或最大化總收益。

第一階段的決策是在不確定性顯現(xiàn)之前做出的，目標(biāo)是優(yōu)化初始決策以適應(yīng)未來(lái)可能發(fā)生的多種情況。

第二階段的決策是在不確定性顯現(xiàn)之后進(jìn)行的，根據(jù)第一階段的決策和實(shí)際發(fā)生的情況進(jìn)行調(diào)整，以優(yōu)化整體結(jié)果。

通過(guò)2SP模型，決策者需要在決策過(guò)程中充分考慮可能發(fā)生的不同場(chǎng)景的影響，從而提高決策的魯棒性和靈活性，做出更為科學(xué)和高效的決策。

舉個(gè)例子，假設(shè)我們要從10個(gè)候選地點(diǎn)中選擇一些建立倉(cāng)庫(kù)，以滿足周邊20個(gè)區(qū)域的需求。

第一階段需要決策的是，在這10個(gè)候選地點(diǎn)中應(yīng)該選擇哪些；

第二階段則要確定倉(cāng)庫(kù)和區(qū)域間的配送關(guān)系，此時(shí)的決策變量數(shù)量多達(dá)200個(gè)（即倉(cāng)庫(kù)i是否配送區(qū)域j）。

△圖像由DALL·E生成

數(shù)學(xué)上，2SP問(wèn)題通常表示為：

其中，Q(x,ξ)表示在給定第一階段決策x和場(chǎng)景ξ下的第二階段優(yōu)化問(wèn)題，其形式為：

在實(shí)際的求解中，一般會(huì)采樣N個(gè)場(chǎng)景計(jì)算對(duì)應(yīng)的Q值來(lái)近似期望。

顯然N越大則近似值越可信，但隨著場(chǎng)景數(shù)量的增加，問(wèn)題規(guī)模迅速膨脹，會(huì)導(dǎo)致求解時(shí)間大幅提高。

還是用這個(gè)倉(cāng)庫(kù)選址的問(wèn)題來(lái)說(shuō)明，為了能做出更好的選址決策，需要將需求、天氣、人流、交通等不確定因素考慮在內(nèi)，而每一個(gè)因素的變化都對(duì)應(yīng)著一個(gè)場(chǎng)景。

這意味著，需要廣泛采樣N個(gè)不同場(chǎng)景來(lái)盡可能模擬真實(shí)情況。這時(shí)，第二階段總決策變量數(shù)會(huì)高達(dá)200N個(gè)，使得求解時(shí)間極為漫長(zhǎng)。

事實(shí)上，當(dāng)N取500時(shí)，即使使用最先進(jìn)的商用求解器Gurobi，也至少需要6個(gè)小時(shí)才能做出最優(yōu)的決策。

傳統(tǒng)方法通常利用隨機(jī)采樣或聚類技術(shù)來(lái)挑選少量的場(chǎng)景（如10或20）以進(jìn)行近似求解，雖然減少了時(shí)間，但得到的決策質(zhì)量卻往往不理想。

基于此，也就有了HGCN2SP模型的設(shè)計(jì)思路——在減少采樣場(chǎng)景個(gè)數(shù)的同時(shí)，盡可能近似得到準(zhǔn)確結(jié)果。

用圖卷積網(wǎng)絡(luò)解決2SP問(wèn)題

研究團(tuán)隊(duì)針對(duì)兩階段隨機(jī)規(guī)劃問(wèn)題求解，提出了基于層次化圖卷積網(wǎng)絡(luò)的HGCN2SP模型。

具體的在算法設(shè)計(jì)方面，團(tuán)隊(duì)通過(guò)構(gòu)建層次圖來(lái)表征2SP問(wèn)題，其中底層的圖用來(lái)表征每個(gè)場(chǎng)景的特性，而頂層的圖則用于表征場(chǎng)景之間的關(guān)系。

然后，再利用層次化圖卷積網(wǎng)絡(luò)（HGCN），分別挖掘底層場(chǎng)景子圖的嵌入信息和頂層場(chǎng)景空間的結(jié)構(gòu)信息，以提取場(chǎng)景表示。

基于注意力機(jī)制的解碼器被用于按序挑選場(chǎng)景，不僅能找到具有代表性的場(chǎng)景來(lái)簡(jiǎn)化問(wèn)題，還可以通過(guò)優(yōu)化場(chǎng)景的排列順序來(lái)改善單純形法求解問(wèn)題時(shí)對(duì)初始基的選取，進(jìn)而顯著提升求解時(shí)間。

△HGCN2SP模型框架

團(tuán)隊(duì)還結(jié)合強(qiáng)化學(xué)習(xí)（RL），綜合考察決策質(zhì)量和求解時(shí)間來(lái)優(yōu)化模型參數(shù)，顯著提高了問(wèn)題求解的效率和質(zhì)量。

在上述的倉(cāng)庫(kù)選址問(wèn)題中，盡管HGCN2SP只選取了10個(gè)場(chǎng)景，但其決策結(jié)果與Gurobi求解器用6個(gè)小時(shí)做出的決策差距僅為1.7%，而求解時(shí)間僅為15秒，相當(dāng)于速度提升了1440倍，充分體現(xiàn)了該方法的有效性。

另外，在網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題（Network Design Problem, NDP）的實(shí)驗(yàn)中，HGCN2SP僅用已有方法不到一半的時(shí)間得到了相近的決策效果。

尤其在大規(guī)模實(shí)例和大量場(chǎng)景情況下，HGCN2SP依然保持了強(qiáng)大的泛化能力。

HGCN2SP的提出為解決復(fù)雜的2SP問(wèn)題提供了一種新的思路和工具，具有廣泛的應(yīng)用前景。

研究團(tuán)隊(duì)計(jì)劃進(jìn)一步優(yōu)化模型，降低訓(xùn)練成本，并探索其在更多實(shí)際問(wèn)題中的應(yīng)用。

論文地址：https://openreview.net/forum?id=8onaVSFTEj