華為云天籌AI求解器助力高效求得問題最優(yōu)解

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

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

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

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

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

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

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

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

兩大新技術(shù)加持

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

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

基于網(wǎng)絡(luò)拓?fù)涮卣鞯摹白赃m應(yīng)稀疏度優(yōu)化”技術(shù)

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

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

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

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

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

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

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

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