引言：“難解問題的表示、算法與應(yīng)用研討會（Workshop on Hard Computational Problems: Representations, Algorithms and Applications, 簡稱 HCP），是目前國內(nèi)難解問題領(lǐng)域頗具規(guī)模和水平的重要會議之一，致力于促進(jìn)難解計算問題相關(guān)領(lǐng)域?qū)W界和工業(yè)界研究人員的深度交流與合作，促成有影響力的學(xué)術(shù)成果和產(chǎn)研合作?！?/p>

近日，2023年第六屆“難解問題的表示、算法與應(yīng)用研討會”（HCP2023）在云南昆明勝利舉行，140多位來自國內(nèi)外多所高校、科研機(jī)構(gòu)以及高科技企業(yè)的專家學(xué)者齊聚一堂，共同探討了難解問題在組合優(yōu)化、求解器、EDA和圖論等領(lǐng)域的研究成果和應(yīng)用。

聯(lián)想研究院人工智能實(shí)驗(yàn)室機(jī)器學(xué)習(xí)主管研究員袁浩受邀出席，與來自皮卡第儒勒-凡爾納大學(xué)、中國科學(xué)院大學(xué)、北京大學(xué)、阿里、華為等高校和企業(yè)的專家學(xué)者進(jìn)行了深入探討交流。袁浩還就“聯(lián)想決策智能技術(shù)在供應(yīng)鏈上的應(yīng)用”作了主題報告，分享了聯(lián)想基于人工智能的運(yùn)籌優(yōu)化技術(shù)在提升制造業(yè)供應(yīng)鏈整體效能方面的成功實(shí)踐。

研討會中關(guān)注的“難解問題”通常指的是時間或空間復(fù)雜性很高的算法問題，其中NP-難問題就是一類典型代表。許多經(jīng)典的組合優(yōu)化問題，如旅行商問題和圖著色問題等，都屬于NP-難問題，因其重要性和難度備受學(xué)界和業(yè)界矚目。本次會議圍繞約束滿足、系統(tǒng)與應(yīng)用、AI與優(yōu)化三大主題展開，其中求解器和運(yùn)籌優(yōu)化在工業(yè)應(yīng)用中成為熱門話題。

01 面向場景的底層計算引擎

求解器作為解決復(fù)雜數(shù)學(xué)規(guī)劃問題的關(guān)鍵工具，扮演著底層技術(shù)的重要角色，其研發(fā)難度大、周期長、成本高，在工業(yè)領(lǐng)域有著廣泛需求。求解器集成多種優(yōu)化算法，例如單純形法、分支定界法、切平面法以及其他啟發(fā)式算法，然而對于復(fù)雜的NP-難問題，現(xiàn)有求解器的性能仍有限。尤其在實(shí)際場景下，問題規(guī)模不斷擴(kuò)大，如何高效求解成為當(dāng)前的挑戰(zhàn)。

隨著人工智能技術(shù)的發(fā)展，利用機(jī)器學(xué)習(xí)方法優(yōu)化求解器成為熱門課題。谷歌的DeepMind團(tuán)隊(duì)于2021年提出了用神經(jīng)網(wǎng)絡(luò)與機(jī)器學(xué)習(xí)方法加速混合整數(shù)規(guī)劃（MIP）問題求解的一類算法，通過模仿學(xué)習(xí)提升了求解器的效率，引起業(yè)界廣泛關(guān)注。

自2018年起，聯(lián)想研究院人工智能實(shí)驗(yàn)室的機(jī)器學(xué)習(xí)團(tuán)隊(duì)開始了依托機(jī)器學(xué)習(xí)和運(yùn)籌優(yōu)化技術(shù)解決供應(yīng)鏈的NP-難問題的技術(shù)研究和產(chǎn)業(yè)應(yīng)用。通過將人工智能技術(shù)與運(yùn)籌優(yōu)化算法相結(jié)合，聯(lián)想自主研發(fā)了“底層計算引擎”——聯(lián)想AI求解器，針對復(fù)雜的NP-難問題實(shí)現(xiàn)了更強(qiáng)的求解性能，提升了計算場景的適配性，相比現(xiàn)有的求解器主要有以下三個優(yōu)勢：

● 智能化求解策略。聯(lián)想自研AI求解器引入多種人工智能技術(shù)替代現(xiàn)有求解器中的一些啟發(fā)式規(guī)則，比如對于求解NP-難問題最常用的方法——分支定界法，人工智能技術(shù)可以充分優(yōu)化其中的變量和節(jié)點(diǎn)選擇策略；對于原始啟發(fā)式算法，則能通過高質(zhì)量決策幫助求解器盡快盡好地找到問題的優(yōu)質(zhì)可行解。而對于其他的如單純形法、切平面選擇算法等，AI技術(shù)同樣能夠在很大程度上提升其優(yōu)化與求解效率。

● 定制化算法模型。綜合優(yōu)化需求、模型特性、計算資源等因素，聯(lián)想自研AI求解器能夠針對不同場景建立定制化的求解算法，并設(shè)計更有針對性的預(yù)求解、啟發(fā)式算法，使其能適應(yīng)不同場景下的優(yōu)化需求，從而在特定場景下的優(yōu)化問題求解上更具優(yōu)勢。

● 可配置的參數(shù)選擇。基于不同場景下的優(yōu)化問題的特性，聯(lián)想AI求解器能夠自主選擇更合理的參數(shù)配置進(jìn)行求解，無需針對不同的配置參數(shù)進(jìn)行反復(fù)測試，有效提升了求解模型的性能和泛化能力，進(jìn)而提升求解器在一般問題上的表現(xiàn)。

在與現(xiàn)有的SOTA開源求解器的性能對比中，聯(lián)想AI求解器表現(xiàn)出了明顯優(yōu)勢：

● 線性優(yōu)化行業(yè)標(biāo)準(zhǔn)數(shù)據(jù)集（NETLIB）：相比開源求解器CLP的運(yùn)行時間減少了77%

● 混合整數(shù)優(yōu)化行業(yè)標(biāo)準(zhǔn)數(shù)據(jù)集（MIPLIB 2017）：相比開源求解器SCIP的運(yùn)行時間減少了9%

此外，聯(lián)想AI求解器在集團(tuán)內(nèi)部供應(yīng)鏈場景中落地應(yīng)用，求解性能同樣明顯優(yōu)于現(xiàn)有的SOTA開源求解器。

02 智能決策，聯(lián)想的解題之策

供應(yīng)鏈作為聯(lián)想的核心競爭力之一，面臨著眾多的NP-難問題，如物料采購、分配、齊套以及生產(chǎn)排程等決策優(yōu)化問題?；谇把氐臋C(jī)器學(xué)習(xí)和運(yùn)籌優(yōu)化技術(shù)，聯(lián)想打造了決策智能技術(shù)，為供應(yīng)鏈構(gòu)建了“智能決策大腦”，實(shí)現(xiàn)了從預(yù)測到?jīng)Q策的全流程優(yōu)化，提升了供應(yīng)鏈的智能化水平。

通過“場景+AI”的方式，聯(lián)想創(chuàng)建了多個場景化的供應(yīng)鏈智能決策解決方案，包括需求預(yù)測、供應(yīng)計劃、物料計劃、庫存優(yōu)化、生產(chǎn)計劃、智慧選品和渠道分貨等，全面提高了供應(yīng)鏈決策效率和質(zhì)量。聯(lián)想連續(xù)榮獲Gartner全球供應(yīng)鏈25強(qiáng)和IDC“亞太最強(qiáng)供應(yīng)鏈”等榮譽(yù)，展示了其在供應(yīng)鏈管理和決策智能技術(shù)方面的領(lǐng)導(dǎo)地位。

03 結(jié)語

越是復(fù)雜問題的解決就越離不開基礎(chǔ)的、底層的算法和方法，實(shí)現(xiàn)技術(shù)創(chuàng)新的關(guān)鍵也正在于此。聯(lián)想通過技術(shù)創(chuàng)新不斷加強(qiáng)供應(yīng)鏈韌性，以決策智能技術(shù)引領(lǐng)供應(yīng)鏈智能化變革，并將其經(jīng)驗(yàn)和成果貢獻(xiàn)給更多行業(yè)領(lǐng)域，為未來發(fā)展注入了強(qiáng)大的技術(shù)力量。