高效運籌：中科大創新數據生成技術助力復雜問題解決

目前論文已被人工智能頂級會議NeurIPS 2024接收。

原標題：NeurIPS 2024｜拆解高復雜運籌問題的磚石，打破數據稀缺的瓶頸，中科大提出高質量運籌數據生成方法
文章來源：機器之心
內容字數：5778字

研究背景與挑戰

近年來，混合整數線性規劃（MILP）在運籌優化領域的應用愈發廣泛，但其求解過程依賴于大量高質量的樣例。然而，由于獲取樣例的高昂成本或隱私問題，導致訓練數據稀缺，限制了求解器的性能。為此，研究者們亟需開發MILP優化問題的數據生成技術，以緩解這一挑戰。

新框架MILP-StuDio

中國科學技術大學王杰教授團隊提出了一種新穎的MILP生成框架——MILP-StuDio，該框架在整個生成過程中考慮問題的分塊結構。這一方法有效解決了傳統生成方法中存在的樣例難度過低或不可解等問題，并顯著提升了生成樣例的質量。

方法介紹

研究者分析了現實世界中許多MILP問題的約束系數矩陣，發現其存在明顯的分塊結構。基于此，研究者提出了一種塊分解的方法，將約束系數矩陣劃分為一系列塊單元的子矩陣，并建立樣例結構庫以高效存儲和利用這些塊信息。研究者設計了三類生成算子：塊刪減、塊替換和塊增加，通過這些操作生成多種規模的高質量MILP樣例。

實驗結果

實驗表明，使用該方法生成的樣例在求解時間和可行性方面與原樣例相近，數學性質得到了更好的保持。此外，將生成的樣例用作AI求解器的訓練數據，結果顯示該方法相較于其他數據生成方法顯著提升了求解器的性能，降低了求解難度。

論文信息

該研究成果已被國際人工智能頂級會議NeurIPS 2024接收，論文標題為《MILP-StuDio: MILP Instance Generation via Block Structure Decomposition》。相關論文鏈接為：https://arxiv.org/abs/2410.22806。

如您有優秀的研究工作想要分享，歡迎聯系投稿郵箱：liyazhou@jiqizhixin.com；zhaoyunfeng@jiqizhixin.com。

聯系作者

文章來源：機器之心
作者微信：
作者簡介：專業的人工智能媒體和產業服務平臺