無(wú)監(jiān)督學(xué)習(xí)訓(xùn)練整數(shù)規(guī)劃求解器的新范式來(lái)了。

中國(guó)科學(xué)技術(shù)大學(xué)王杰教授團(tuán)隊(duì)（MIRA Lab）提出了一種全新的整數(shù)規(guī)劃求解方法——DiffILO（Differentiable Integer Linear Programming Optimization），相關(guān)論文已被人工智能頂級(jí)國(guó)際會(huì)議ICLR 2025接收為Spotlight。

結(jié)果顯示：與現(xiàn)有主流的監(jiān)督學(xué)習(xí)方法對(duì)比，DiffILO不僅顯著加快訓(xùn)練速度，還能生成更高質(zhì)量的可行解。

引言：用機(jī)器學(xué)習(xí)解ILP，為何如此困難？

整數(shù)線性規(guī)劃（ILP） 是組合優(yōu)化中最基礎(chǔ)也是最關(guān)鍵的一類問(wèn)題，廣泛應(yīng)用于工業(yè)調(diào)度、物流運(yùn)輸、網(wǎng)絡(luò)規(guī)劃、芯片布圖等現(xiàn)實(shí)場(chǎng)景。然而 ILP 的求解非常困難 —— 變量離散、可行域復(fù)雜、搜索空間指數(shù)爆炸，本質(zhì)上屬于 NP 難問(wèn)題。

近年來(lái)，機(jī)器學(xué)習(xí)逐漸被引入這一過(guò)程，嘗試通過(guò)數(shù)據(jù)驅(qū)動(dòng)的方式加速求解器。但當(dāng)前主流做法大多依賴監(jiān)督學(xué)習(xí)：先用傳統(tǒng)求解器（如Gurobi）生成一批解作為標(biāo)簽，然后訓(xùn)練模型去“模仿”這些解。這種做法存在兩大瓶頸：

• 高昂的訓(xùn)練成本：每個(gè)樣本都需調(diào)用求解器生成標(biāo)簽；
• 訓(xùn)練目標(biāo)與測(cè)試目標(biāo)不一致：只優(yōu)化預(yù)測(cè)誤差，無(wú)法保障最終解的可行性與質(zhì)量。

有沒(méi)有可能完全擺脫標(biāo)簽依賴，直接讓模型“自己”學(xué)會(huì)求解ILP問(wèn)題？

答案是：可以！該論文提出了DiffILO方法，可以用梯度下降來(lái)“解整數(shù)規(guī)劃”！

核心方法：DiffILO是如何做到的？

DiffILO，全稱 Differentiable Integer Linear Programming Optimization，是一種無(wú)監(jiān)督、端到端、可微分的ILP求解新范式。它的核心創(chuàng)新是將離散、帶約束的整數(shù)規(guī)劃問(wèn)題，轉(zhuǎn)化為連續(xù)、可微、無(wú)約束的問(wèn)題，并借助深度學(xué)習(xí)模型來(lái)直接預(yù)測(cè)高質(zhì)量解。

方法流程如下圖所示：

方法大致可以分為三個(gè)步驟：

Step 1：從離散到連續(xù)——概率建模與約束期望化

ILP問(wèn)題的形式通常如下：

DiffILO的第一步是將每個(gè)0-1變量視為伯努利分布下的隨機(jī)變量，即。

其中是需要優(yōu)化的概率值。

傳統(tǒng)ILP的“硬約束” 被轉(zhuǎn)化為“期望約束違背為零”：

這種期望建模方式有兩個(gè)好處：

• 仍能保留原問(wèn)題的最優(yōu)解結(jié)構(gòu)；
• 易于被懲罰函數(shù)進(jìn)一步轉(zhuǎn)化為無(wú)約束形式。

Step 2：從約束到目標(biāo)——懲罰函數(shù)與可微重參數(shù)化

該方法使用懲罰函數(shù)法將上述期望約束合入目標(biāo)函數(shù)：

但由于該函數(shù)的采樣項(xiàng)并不可微，DiffILO采用了Gumbel-Softmax + 重參數(shù)技巧，將離散采樣近似為一個(gè)連續(xù)可導(dǎo)的函數(shù)：

• 使用 ，實(shí)現(xiàn)對(duì)伯努利的可微近似；
• 使用保留組合結(jié)構(gòu)；
• 梯度通過(guò)回傳，值通過(guò)保留，兼顧
  “可微”和“離散”的雙重需求。

最終得到一個(gè)幾乎處處可導(dǎo)的目標(biāo)函數(shù)，可以直接用梯度下降

進(jìn)行優(yōu)化。

Step 3：從圖中學(xué)——GNN建模與端到端訓(xùn)練

每個(gè)ILP實(shí)例本質(zhì)上可以被表示為一個(gè)二分圖：左邊是變量，右邊是約束，邊代表變量出現(xiàn)在對(duì)應(yīng)約束中。

使用一個(gè)圖神經(jīng)網(wǎng)絡(luò)（GNN）來(lái)編碼這個(gè)結(jié)構(gòu)，輸入為圖G，輸出為概率向量，再接入一個(gè)MLP進(jìn)行最終預(yù)測(cè)。

訓(xùn)練過(guò)程完全無(wú)監(jiān)督，目標(biāo)是最小化上述可微目標(biāo)函數(shù)。還引入了三種訓(xùn)練技巧來(lái)增強(qiáng)穩(wěn)定性：

• 樣本歸一化：對(duì)目標(biāo)函數(shù)做歸一處理，適應(yīng)不同實(shí)例規(guī)模；
• 余弦退火：自適應(yīng)學(xué)習(xí)率調(diào)度；
• 懲罰系數(shù)調(diào)控：動(dòng)態(tài)調(diào)整μ，平衡解質(zhì)量與可行性。

實(shí)驗(yàn)結(jié)果

作者在多個(gè)標(biāo)準(zhǔn) ILP 數(shù)據(jù)集（如 Set Covering、Independent Set、Combinatorial Auction）上進(jìn)行了系統(tǒng)評(píng)估。結(jié)果顯示：與現(xiàn)有主流的監(jiān)督學(xué)習(xí)方法對(duì)比，DiffILO不僅顯著加快訓(xùn)練速度，還能生成更高質(zhì)量的可行解，并且在與Gurobi、SCIP結(jié)合使用時(shí)，顯著提升求解器的整體性能。

作者介紹

本論文作者耿子介是中國(guó)科學(xué)技術(shù)大學(xué)MIRA實(shí)驗(yàn)室2022級(jí)博士生，師從王杰教授。此前，他于2022年畢業(yè)于少年班學(xué)院，取得數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)學(xué)士學(xué)位。他的主要研究方向包括機(jī)器學(xué)習(xí)在運(yùn)籌優(yōu)化與芯片設(shè)計(jì)等領(lǐng)域的應(yīng)用、大語(yǔ)言模型等。他在NeurIPS、ICML、ICLR等人工智能頂級(jí)會(huì)議上發(fā)表論文十余篇，其中五篇論文入選Oral/Spotlight。他曾獲2024年度國(guó)家獎(jiǎng)學(xué)金；曾兩次獲得丘成桐大學(xué)生數(shù)學(xué)競(jìng)賽優(yōu)勝獎(jiǎng)；曾在微軟亞洲研究院實(shí)習(xí)，獲得“明日之星”稱號(hào)；曾多次擔(dān)任頂會(huì)審稿人，獲評(píng)NeurIPS 2023 Top審稿人；參與創(chuàng)辦南京真則網(wǎng)絡(luò)科技有限公司。

論文地址：
openreview.net/pdf?id=FPfCUJTsCn