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

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

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

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

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

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

引言

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

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

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

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

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

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

背景和問題介紹

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

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

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

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

方法介紹

分塊結構分析

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

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

約束矩陣分塊

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

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

通過分塊實現可擴展生成

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

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

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

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

圖 3：方法的總體流程。

實驗

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