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

在審

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

本說明書提供的組合優(yōu)化問題的求解方法和系統(tǒng)，通過分支定界算法求解組合優(yōu)化問題的實施例，并將求解實施例過程中的每個分支節(jié)點的約束和松弛解以及節(jié)點對應的強分支作為樣本數據，來訓練決策模型。所述求解方法和系統(tǒng)在對目標組合優(yōu)化問題求解過程中，基于分支定界算法，在每個分支節(jié)點，將分支節(jié)點對應的約束和松弛解輸入至訓練好的決策模型中，并輸出當前節(jié)點對應的強分支，從而基于決策模型來模擬分支定界過程中的分支過程，快速找到分支節(jié)點中的強分支，無需對每個分支進行求解，大大縮短計算時間，從而加快組合優(yōu)化問題的求解速度。

技術領域

本說明書涉及整數規(guī)劃技術領域，尤其涉及一種組合優(yōu)化問題的求解方法和系統(tǒng)。

背景技術

很多組合優(yōu)化問題都可以被形式化建模成為（混合）整數規(guī)劃問題來進行求解。組合優(yōu)化問題的特點是決策變量的決策空間為有限點集，可以通過窮舉法得到問題的最優(yōu)解。但是由于可行解的數量隨問題規(guī)模呈指數型增長，每增加一個決策變量，求解的速度就需要再增加一倍。當決策變量的規(guī)模較大時，求解最優(yōu)解所花費的時間也較長。

因此，需要提供一種新的組合優(yōu)化問題的求解方法和系統(tǒng)，以在大規(guī)模的變量下，提高組合優(yōu)化問題的求解速度和求解質量。

發(fā)明內容

本說明書提供一種新的組合優(yōu)化問題的求解方法和系統(tǒng)，以在大規(guī)模的變量下，提高組合優(yōu)化問題的求解速度和求解質量。

第一方面，本說明書提供一種組合優(yōu)化問題的求解方法，包括：獲取目標組合優(yōu)化問題的目標優(yōu)化模型，所述目標優(yōu)化模型包括優(yōu)化目標函數、目標約束以及決策變量，所述決策變量中的至少部分為整數規(guī)劃變量；基于分支定界法對所述目標優(yōu)化模型進行求解，確定目標解，包括對每個分支節(jié)點：基于預先訓練好的決策模型確定當前分支節(jié)點對應的目標強分支，所述決策模型是基于歷史優(yōu)化模型在通過分支定界算法求解過程中的每個樣本分支節(jié)點的樣本數據及其對應的樣本決策訓練得到的，所述樣本數據包括當前樣本分支節(jié)點對應的樣本約束以及樣本變量的松弛解，所述樣本決策包括所述當前樣本分支節(jié)點對應的樣本強分支；以及輸出所述目標解。

在一些實施例中，所述歷史優(yōu)化模型與所述目標優(yōu)化模型為同類模型。

在一些實施例中，所述樣本數據包括二部圖結構。

在一些實施例中，所述二部圖結構包括所述當前樣本分支節(jié)點對應的多個樣本約束、多個樣本變量的松弛解以及連接所述多個樣本約束和所述多個樣本變量的松弛解的邊。

在一些實施例中，所述決策模型為圖卷積神經網絡模型。

在一些實施例中，在所述決策模型的訓練過程中，基于仿射變換對所述樣本數據進行初始化。

在一些實施例中，在所述決策模型的訓練過程中，基于最小化交叉熵損失函數對所述決策模型進行訓練。

在一些實施例中，所述基于預先訓練好的決策模型確定當前分支節(jié)點對應的目標強分支，包括：確定所述當前分支節(jié)點對應的當前優(yōu)化模型，所述當前優(yōu)化模型包括所述優(yōu)化目標函數、當前約束以及所述決策變量；基于松弛算法，確定所述當前優(yōu)化模型對應的所述決策變量的當前松弛解；以及將所述當前約束以及所述當前松弛解輸入至所述決策模型中，確定所述當前分支節(jié)點對應的所述目標強分支。

在一些實施例中，所述將所述當前約束以及所述當前松弛解輸入至所述決策模型中，確定所述當前分支節(jié)點對應的所述目標強分支，包括：確定所述當前分支節(jié)點對應的兩個分支；將所述當前約束以及所述當前松弛解輸入至所述決策模型中，確定所述當前分支節(jié)點對應的所述兩個分支的概率；以及將所述兩個分支中概率高的一個分支作為所述目標強分支。