論文作者劉昊洋是中國科學技術大學 2023 級碩士生，師從王杰教授，主要的研究方向為強化學習與學習優(yōu)化理論及方法。他曾在 NeurIPS、ICML 和 ICLR 等人工智能頂級會議上發(fā)表論文三篇，曾獲中國科學技術大學黃渝紀念獎學金、華為獎學金等榮譽。

近日，中科大王杰教授團隊（MIRA Lab）提出了矩陣分塊分解技術生成數(shù)學優(yōu)化問題，有效解決運籌優(yōu)化領域數(shù)據(jù)稀缺的問題，大幅提升 AI 運籌求解器求解質(zhì)量。

數(shù)學優(yōu)化在運籌優(yōu)化領域中具有核心地位，是一種通過構建數(shù)學模型來尋找最優(yōu)解的技術。混合整數(shù)線性規(guī)劃（MILP）是一種基礎的數(shù)學優(yōu)化問題，在實際世界中有廣泛的應用，如工業(yè)、金融、物流和芯片設計，其求解效率關系到重大的經(jīng)濟收益。

王杰教授團隊提出了一種新穎的 MILP 生成框架，該框架在整個生成過程中考慮問題分塊結構，從而生成高質(zhì)量的優(yōu)化問題樣例，大幅提升求解器的求解質(zhì)量。目前論文已被人工智能頂級會議 NeurIPS 2024 接收。

• 論文標題：MILP-StuDio: MILP Instance Generation via Block Structure Decomposition
• 論文鏈接：https://arxiv.org/abs/2410.22806

近年來，該團隊已在國際人工智能頂級會議上發(fā)表了混合整數(shù)線性規(guī)劃、偏微分方程等數(shù)據(jù)生成方法相關的論文四篇 [1-4]，提出了混合整數(shù)優(yōu)化領域首個基于機器學習的數(shù)據(jù)生成框架 G2MILP。目前，G2MILP [2] 發(fā)表在人工智能頂會 NeurIPS 2023 中并取得大會 Spotlight，之后擴展了難例生成的相關任務并公開于 [5]。

引言

為了加速 MILP 求解過程，傳統(tǒng)求解器和 AI 求解器都在很大程度上依賴大量高質(zhì)量的 MILP 樣例進行超參數(shù)調(diào)優(yōu)或模型訓練。然而，由于高昂的獲取成本或隱私問題，獲取大量樣例通常是困難的，稀缺的訓練數(shù)據(jù)成為嚴重制約求解器性能的瓶頸。

因此，研究者希望能開發(fā) MILP 優(yōu)化問題的數(shù)據(jù)生成技術來緩解數(shù)據(jù)稀缺的挑戰(zhàn)。近年來，通用 MILP 生成方面取得了一些進展。然而，現(xiàn)有方法仍然面臨顯著的挑戰(zhàn)。

（1）目前的方法在生成過程中往往忽略了 MILP 約束系數(shù)矩陣中與問題建模緊密相連的特定塊狀結構，這導致了塊狀結構的破壞和問題建模的改變，進而產(chǎn)生了難度過低或者不可解的樣例。

（2）現(xiàn)有方法未能生成與原始樣例不同大小的樣例，限制了樣例的多樣性。

（3）在生成大規(guī)模樣例時，現(xiàn)有方法需要大量運行時間。

針對上述挑戰(zhàn)，研究者嘗試分析和利用問題結構以解決上述問題。研究者觀察到許多現(xiàn)實世界的 MILP 問題在其約束系數(shù)矩陣中表現(xiàn)出重復的塊單元模式?；诖?，研究者提出了一種新穎的 MILP 生成框架，該框架在整個生成過程中考慮問題分塊結構，從而生成高質(zhì)量的樣例。

背景和問題介紹

混合整數(shù)線性規(guī)劃（MILP）是一種應用廣泛的通用優(yōu)化模型，其具體形式如下

現(xiàn)實應用中，許多 MILP 樣例在其約束系數(shù)矩陣 A 中表現(xiàn)出由多個塊單元組成的分塊結構。這些具有塊結構的 MILP 問題，在現(xiàn)實場景中廣泛存在，包括多個被廣泛研究的多個數(shù)據(jù)集，如組合拍賣（CA）、容量設施選址（FA）、物品放置（IP）、多重背包（MIK）和工作負載平衡（WA）等。在圖 1 中，研究者使用可視化這些 MILP 樣例的約束系數(shù)矩陣。

圖 1：四個常見運籌優(yōu)化問題中約束系數(shù)矩陣的分塊結構

在運籌學中，研究人員早已注意到來自同一問題類型的樣例中約束系數(shù)矩陣的相似塊結構，并意識到約束系數(shù)矩陣在確定問題建模和數(shù)學性質(zhì)中的關鍵作用。因此，現(xiàn)有的一些 MILP 方法已經(jīng)利用了該分塊結構，并在加速此類 MILP 問題的求解過程中展現(xiàn)出了巨大潛力，著名的例子包括求解大規(guī)模 MILP 問題的 Dantzig-Wolfe 分解和 Benders 分解。

方法介紹

分塊結構分析

現(xiàn)實場景中很多問題，將其約束系數(shù)矩陣會重新排列可以得到明顯得分塊結構。圖 2 是一些簡單的分塊例子，研究者將塊單元用藍色突出顯示。盡管這些結構相對簡單，但它們是更復雜塊結構的基本構建塊，并在運籌學中廣泛使用。

圖 2：一些簡單的分塊約束矩陣例子

約束矩陣分塊

研究者根據(jù)約束系數(shù)矩陣變量劃分算法進行塊分解。具體而言，研究者提取約束系數(shù)矩陣中塊單元的子矩陣。在上面的三個分塊例子中，第一個約束矩陣的分塊單元子矩陣是，在第二個例子中是  ，在第三個例子中是 。最后，研究者將約束系數(shù)矩陣劃分為一系列的分塊單元的子矩陣。

各樣例之間的塊單元在內(nèi)部結構上展現(xiàn)出顯著的相似性。這些共同特征表明，塊單元的分布蘊含著關于問題建模信息，使其成為重構新樣例的理想磚石。在獲得分塊單元子矩陣后，并將其收集起來構建一個樣例結構庫。這個結構庫作為收集到的子圖的存儲庫，允許高效存儲、檢索和利用塊信息。

通過分塊實現(xiàn)可擴展生成

借助結構庫，研究者設計了三類生成算子，生成具有多種規(guī)模的高質(zhì)量 MILP 樣例。

• 塊刪減：隨機從原始樣例中抽取一個分塊單元并將其移除，生成的 MILP 樣例相比原始樣例具有更小的規(guī)模。
• 塊替換：隨機從原始樣例中抽取一個塊單元，然后用結構庫中抽取的另一個塊單元進行替換。塊替換算子通過引入外部塊單元帶來了結構上的變化。
• 塊增加：從結構庫中隨機抽取一個塊單元并將其添加到原始樣例中。這個過程生成的新樣例規(guī)模相較于原始樣例更大。

為了保留塊結構，這些操作符應根據(jù)約束和變量的分類進行精確匹配結果。

研究者的方法具體流程如圖 3 所示。

圖 3：方法的總體流程。

實驗

研究者實驗測試了生成樣例的求解時間，發(fā)現(xiàn)該方法生成樣例的計算難度和可行性與原樣例的更加相近。說明生成的樣例數(shù)學性質(zhì)得到更好的保持。此外，研究者還將方法生成的樣例作為 AI 求解器的訓練數(shù)據(jù)，實驗表明該的方法能相比于其他數(shù)據(jù)生成方法能夠跟顯著提升求解器的性能，在困難的樣例上相比于 Gurobi 降低 66.9% 的 gap。