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

網絡線性規(guī)劃應用場景豐富

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

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

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

再比如在電力網絡中，中央控制器通過網絡線性規(guī)劃來調度能源，能夠實現對能源曲線的削峰填谷，保障能源輸出的平穩(wěn)供應。

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

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

兩大新技術加持

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

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

基于網絡拓撲特征的“自適應稀疏度優(yōu)化”技術

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

基于網絡單純形理論性質的“底層優(yōu)化及并行化”技術

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

如今“自適應稀疏度優(yōu)化”和“底層優(yōu)化及并行化”兩項技術已經集成到華為云天籌AI求解器中，大幅度提升其在網絡線性規(guī)劃問題上的算法性能，能快速求解與網絡結構相關的網絡規(guī)劃、調度優(yōu)化、物理運輸等問題。

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

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

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

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