近日，阿里巴巴達(dá)摩院宣布"敏迭"求解器（MindOpt）正式發(fā)布GPU版本。該版本利用GPU并行加速特性，引入新算法突破"長(zhǎng)尾效應(yīng)"難題，在約2000個(gè)通用算例測(cè)試中，可將99%以上的問(wèn)題類型穩(wěn)定求解至高精度，并支持傳統(tǒng)上"不可解"的億級(jí)變量線性規(guī)劃問(wèn)題。

求解器被譽(yù)為"工業(yè)軟件之芯"，承擔(dān)電力調(diào)度、航班編排、高端制造、金融管理等關(guān)鍵領(lǐng)域的復(fù)雜計(jì)算任務(wù)。傳統(tǒng)線性規(guī)劃求解器基于CPU設(shè)計(jì)，依賴矩陣分解計(jì)算，問(wèn)題規(guī)模膨脹后內(nèi)存需求爆炸式增長(zhǎng)，并行度有限，常導(dǎo)致數(shù)小時(shí)無(wú)法收斂甚至直接崩潰。

行業(yè)近年嘗試將求解器遷移至GPU，把核心運(yùn)算從矩陣分解轉(zhuǎn)為稀疏矩陣-向量乘法，利用GPU高并發(fā)高帶寬特性避免內(nèi)存膨脹。但這一路線普遍存在"長(zhǎng)尾效應(yīng)"——求解后期精度提升極為緩慢，難以達(dá)到業(yè)務(wù)所需的最終精度。

達(dá)摩院敏迭求解器GPU版通過(guò)算法加速策略與GPU內(nèi)核深度優(yōu)化，將數(shù)學(xué)規(guī)劃技巧與GPU工程優(yōu)勢(shì)結(jié)合，緩解了長(zhǎng)尾效應(yīng)。測(cè)試數(shù)據(jù)顯示：高精度要求下，敏迭GPU版穩(wěn)定求解的問(wèn)題類型占比超99%，業(yè)內(nèi)主流GPU求解器在同一測(cè)試集上的表現(xiàn)為96.7%至98.3%。大規(guī)模問(wèn)題上，敏迭成功率比主流產(chǎn)品提升14%以上，速度平均提升2.67倍。面對(duì)億級(jí)變量超大規(guī)模問(wèn)題，敏迭GPU版對(duì)常見問(wèn)題類型的穩(wěn)定求解率超過(guò)80%。

實(shí)際應(yīng)用中，某大型數(shù)字廣告平臺(tái)每次流量分配涉及約3.3億個(gè)變量和1600萬(wàn)個(gè)約束條件，要求2小時(shí)內(nèi)完成。多數(shù)商用求解器運(yùn)行48小時(shí)后仍無(wú)法給出可行解甚至崩潰，敏迭GPU版僅用1700秒便解到可靠精度。

目前敏迭求解器已在工信部相關(guān)賽事中連續(xù)奪冠，入選"人工智能賦能新型工業(yè)化"典型應(yīng)用案例，實(shí)現(xiàn)百萬(wàn)量級(jí)并發(fā)調(diào)用，服務(wù)數(shù)千家企業(yè)。此次GPU版本主要面向線性規(guī)劃（LP）問(wèn)題，混合整數(shù)規(guī)劃（MIP）和非線性規(guī)劃等復(fù)雜類型的表現(xiàn)尚未披露。

達(dá)摩院決策智能實(shí)驗(yàn)室負(fù)責(zé)人印臥濤表示，各行業(yè)計(jì)算規(guī)模正在爆發(fā)式增長(zhǎng)，團(tuán)隊(duì)將持續(xù)解鎖新型硬件在運(yùn)籌優(yōu)化領(lǐng)域的潛力。國(guó)際方面，Gurobi已在13.0版本中引入PDHG算法GPU加速，國(guó)內(nèi)杉數(shù)科技COPT也在推進(jìn)GPU異構(gòu)計(jì)算。