華為云EI創(chuàng)新孵化Lab與華為2012實驗室中央研究院理論研究部聯(lián)合團隊（以下簡稱“華為聯(lián)合團隊”）在網(wǎng)絡(luò)線性規(guī)劃求解器關(guān)鍵技術(shù)上實現(xiàn)突破，天籌AI求解器在國際權(quán)威求解器測評——Hans Mittelmann教授的大規(guī)模網(wǎng)絡(luò)線性規(guī)劃榜單中位列TOP1，性能領(lǐng)先第二名11%。

網(wǎng)絡(luò)線性規(guī)劃應(yīng)用場景豐富

助力高效求得問題最優(yōu)解

網(wǎng)絡(luò)線性規(guī)劃是網(wǎng)絡(luò)流理論與算法的核心，本質(zhì)上是要充分利用和有效提升現(xiàn)有網(wǎng)絡(luò)資源的能力，使系統(tǒng)的流量達到最大并有效運行。如今網(wǎng)絡(luò)線性規(guī)劃已廣泛應(yīng)用在網(wǎng)絡(luò)規(guī)劃、調(diào)度優(yōu)化、物理運輸?shù)痊F(xiàn)實場景，覆蓋通訊、交通、物流、電力、工程規(guī)劃、任務(wù)分派、設(shè)備更新以及計算機輔助設(shè)計等眾多領(lǐng)域。

比如在交通網(wǎng)絡(luò)中，控制中心可以通過網(wǎng)絡(luò)線性規(guī)劃來調(diào)度車流，實現(xiàn)高峰期擁塞路段的流量疏導，提高城市路面通勤效率。

再比如在電力網(wǎng)絡(luò)中，中央控制器通過網(wǎng)絡(luò)線性規(guī)劃來調(diào)度能源，能夠?qū)崿F(xiàn)對能源曲線的削峰填谷，保障能源輸出的平穩(wěn)供應(yīng)。

或者一個更形象具體的例子，下圖是一個連接某物資產(chǎn)地Vs（蘭州為例）至銷地Vt（上海為例）的鐵路運輸網(wǎng)，弧上的數(shù)字表示該路段的最大通過能力。如果要制定一個運輸方案，使從產(chǎn)地Vs運到銷地Vt的物資數(shù)量最多，通過網(wǎng)絡(luò)線性規(guī)劃能夠快速得出最優(yōu)解。

求解網(wǎng)絡(luò)線性規(guī)劃問題可實現(xiàn)成本開銷最小化、有限資源配置最優(yōu)、發(fā)揮網(wǎng)絡(luò)傳輸能力最大化的目的。隨著業(yè)務(wù)的不斷增大，企業(yè)將會面對越來越多關(guān)于網(wǎng)絡(luò)結(jié)構(gòu)的決策優(yōu)化問題，如何在大規(guī)模的變量和約束條件下求得最優(yōu)解，是企業(yè)提升運營效率的關(guān)鍵。

兩大新技術(shù)加持

華為云天籌AI求解器再度突破求解性能

本次打榜主要比拼基于大規(guī)模變量和約束條件的問題求解速度。華為聯(lián)合團隊提出了基于網(wǎng)絡(luò)拓撲特征的自適應(yīng)稀疏度優(yōu)化技術(shù)和基于網(wǎng)絡(luò)線性規(guī)劃問題理論性質(zhì)的底層優(yōu)化及并行化技術(shù)，在榜單的25個問題中實現(xiàn)高效求解，性能領(lǐng)先第二名11%。兩大技術(shù)充分利用網(wǎng)絡(luò)線性規(guī)劃問題的結(jié)構(gòu)化特征，極大提升了華為云天籌AI求解器在網(wǎng)絡(luò)線性規(guī)劃問題上的性能。

基于網(wǎng)絡(luò)拓撲特征的“自適應(yīng)稀疏度優(yōu)化”技術(shù)

華為聯(lián)合團隊提出了一種全新的調(diào)節(jié)迭代過程稀疏性的方法，并基于問題的代數(shù)特征恢復物理拓撲并結(jié)合網(wǎng)絡(luò)節(jié)點度分布等信息自適應(yīng)選擇最優(yōu)策略，從而實現(xiàn)整體求解時間的大幅下降。

基于網(wǎng)絡(luò)單純形理論性質(zhì)的“底層優(yōu)化及并行化”技術(shù)

對于大規(guī)模網(wǎng)絡(luò)線性規(guī)劃問題，特別是實際場景中涉及千萬甚至上億規(guī)模的問題，底層實現(xiàn)也是求解器性能的瓶頸所在。華為聯(lián)合團隊利用網(wǎng)絡(luò)線性規(guī)劃問題的理論性質(zhì)，大幅優(yōu)化了矩陣庫等基礎(chǔ)模塊的底層實現(xiàn)，并利用并行化技術(shù)大幅加速求解過程，使得華為云天籌AI求解器能夠支持億級規(guī)模網(wǎng)絡(luò)線性規(guī)劃的高效求解。

如今“自適應(yīng)稀疏度優(yōu)化”和“底層優(yōu)化及并行化”兩項技術(shù)已經(jīng)集成到華為云天籌AI求解器中，大幅度提升其在網(wǎng)絡(luò)線性規(guī)劃問題上的算法性能，能快速求解與網(wǎng)絡(luò)結(jié)構(gòu)相關(guān)的網(wǎng)絡(luò)規(guī)劃、調(diào)度優(yōu)化、物理運輸?shù)葐栴}。

在大規(guī)模通信網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化問題中，網(wǎng)絡(luò)優(yōu)化平臺基于全網(wǎng)流量規(guī)律，通過網(wǎng)絡(luò)線性規(guī)劃分配網(wǎng)絡(luò)資源，提升用戶體驗。

在大規(guī)模云資源調(diào)度問題中，云調(diào)度平臺結(jié)合各個區(qū)域資源，在滿足客戶算力、帶寬和存儲需求的條件下，結(jié)合預測規(guī)劃和網(wǎng)絡(luò)線性規(guī)劃方法使得計算資源供需平衡、支撐業(yè)務(wù)彈性和滿足業(yè)務(wù)波動等需求。

未來，網(wǎng)絡(luò)線性規(guī)劃求解器關(guān)鍵技術(shù)還將應(yīng)用在華為數(shù)字能源能量優(yōu)化調(diào)度問題上，幫助分鐘級完成問題求解，提升能源利用率、降低碳排放。

隨著華為運籌優(yōu)化技術(shù)的發(fā)展和優(yōu)化理論的突破，更多創(chuàng)新技術(shù)將會落地天籌AI求解器。未來，華為聯(lián)合團隊將持續(xù)從運籌優(yōu)化理論和算法層面進行難題攻堅，不斷優(yōu)化天籌AI求解器性能，提升求解器領(lǐng)域技術(shù)競爭力，為客戶創(chuàng)造更大價值。