[發(fā)明專利]組合優(yōu)化問題的求解方法和系統(tǒng)

在審

• 申請?zhí)枺?/td>: 202210495655.5
• 申請日: 2022-05-09
• 公開（公告）號: CN114595641A
• 公開（公告）日: 2022-06-07
• 發(fā)明（設(shè)計）人: 王貴陽;劉子奇;沈文博;周俊;華致剛
• 申請（專利權(quán)）人: 支付寶（杭州）信息技術(shù)有限公司
• 主分類號: G06F30/27
• 分類號: G06F30/27;G06K9/62;G06N3/04;G06N3/08;G06F111/04;G06F111/06
• 代理公司: 北京匯思誠業(yè)知識產(chǎn)權(quán)代理有限公司 11444
• 代理人: 周放

1.一種組合優(yōu)化問題的求解方法，包括：

獲取目標(biāo)組合優(yōu)化問題的目標(biāo)優(yōu)化模型，所述目標(biāo)優(yōu)化模型包括優(yōu)化目標(biāo)函數(shù)、目標(biāo)約束以及決策變量，所述決策變量中的至少部分為整數(shù)規(guī)劃變量；

基于分支定界法對所述目標(biāo)優(yōu)化模型進(jìn)行求解，確定目標(biāo)解，包括對每個分支節(jié)點：

基于預(yù)先訓(xùn)練好的決策模型確定當(dāng)前分支節(jié)點對應(yīng)的目標(biāo)強(qiáng)分支，所述決策模型是基于歷史優(yōu)化模型在通過分支定界算法求解過程中的每個樣本分支節(jié)點的樣本數(shù)據(jù)及其對應(yīng)的樣本決策訓(xùn)練得到的，所述樣本數(shù)據(jù)包括當(dāng)前樣本分支節(jié)點對應(yīng)的樣本約束以及樣本變量的松弛解，所述樣本決策包括所述當(dāng)前樣本分支節(jié)點對應(yīng)的樣本強(qiáng)分支；以及

輸出所述目標(biāo)解。

2.如權(quán)利要求1所述的組合優(yōu)化問題的求解方法，其中，所述目標(biāo)組合優(yōu)化問題為目標(biāo)人群圈定問題，所述歷史優(yōu)化模型與所述目標(biāo)優(yōu)化模型為同類模型。

3.如權(quán)利要求1所述的組合優(yōu)化問題的求解方法，其中，所述樣本數(shù)據(jù)包括二部圖結(jié)構(gòu)。

4.如權(quán)利要求3所述的組合優(yōu)化問題的求解方法，其中，所述二部圖結(jié)構(gòu)包括所述當(dāng)前樣本分支節(jié)點對應(yīng)的多個樣本約束、多個樣本變量的松弛解以及連接所述多個樣本約束和所述多個樣本變量的松弛解的邊。

5.如權(quán)利要求1所述的組合優(yōu)化問題的求解方法，其中，所述決策模型為圖卷積神經(jīng)網(wǎng)絡(luò)模型。

6.如權(quán)利要求1所述的組合優(yōu)化問題的求解方法，其中，在所述決策模型的訓(xùn)練過程中，基于仿射變換對所述樣本數(shù)據(jù)進(jìn)行初始化。

7.如權(quán)利要求1所述的組合優(yōu)化問題的求解方法，其中，在所述決策模型的訓(xùn)練過程中，基于最小化交叉熵?fù)p失函數(shù)對所述決策模型進(jìn)行訓(xùn)練。

8.如權(quán)利要求1所述的組合優(yōu)化問題的求解方法，其中，所述基于預(yù)先訓(xùn)練好的決策模型確定當(dāng)前分支節(jié)點對應(yīng)的目標(biāo)強(qiáng)分支，包括：

確定所述當(dāng)前分支節(jié)點對應(yīng)的當(dāng)前優(yōu)化模型，所述當(dāng)前優(yōu)化模型包括所述優(yōu)化目標(biāo)函數(shù)、當(dāng)前約束以及所述決策變量；

基于松弛算法，確定所述當(dāng)前優(yōu)化模型對應(yīng)的所述決策變量的當(dāng)前松弛解；以及

將所述當(dāng)前約束以及所述當(dāng)前松弛解輸入至所述決策模型中，確定所述當(dāng)前分支節(jié)點對應(yīng)的所述目標(biāo)強(qiáng)分支。

9.如權(quán)利要求8所述的組合優(yōu)化問題的求解方法，其中，所述將所述當(dāng)前約束以及所述當(dāng)前松弛解輸入至所述決策模型中，確定所述當(dāng)前分支節(jié)點對應(yīng)的所述目標(biāo)強(qiáng)分支，包括：

確定所述當(dāng)前分支節(jié)點對應(yīng)的兩個分支；

將所述當(dāng)前約束以及所述當(dāng)前松弛解輸入至所述決策模型中，確定所述當(dāng)前分支節(jié)點對應(yīng)的所述兩個分支的概率；以及

將所述兩個分支中概率高的一個分支作為所述目標(biāo)強(qiáng)分支。

10.一種組合優(yōu)化問題的求解系統(tǒng)，包括：

至少一個存儲介質(zhì)，存儲有至少一個指令集，用于對組合優(yōu)化問題進(jìn)行求解；以及

至少一個處理器，同所述至少一個存儲介質(zhì)通信連接，

其中，當(dāng)所述組合優(yōu)化問題的求解系統(tǒng)運(yùn)行時，所述至少一個處理器讀取所述至少一個指令集，并且根據(jù)所述至少一個指令集的指示執(zhí)行權(quán)利要求1-9中任一項所述的組合優(yōu)化問題的求解方法。