華為供應鏈問題由於其超大規模（千萬級的變數和約束，數百萬的整數變數）、數值範圍大（數學模型中最大係數和最小係數之間差距超過
）、約束矩陣低秩病態（約束矩陣的條件數超過
）、靈活魯棒的增量求解等問題，一直給包括Gurobi，CPLEX，XPRESS在內的各個數學規劃求解器帶來很大的計算挑戰。針對華為供應鏈的特殊場景，諾亞方舟實驗室（Noah's Ark Lab）團隊聯合來自香港理工大學孫德鋒老師(Professor Sun Defeng) 團隊和上海交通大學Apex實驗室張偉楠老師團隊共同實現了自研求解器的設計和加速，現已落地華為供應鏈多個場景，支援日常生產需要。
總體框架
以多工廠排產引擎（變數和約束均在2000萬以上，全流程需要完成90輪線性規劃問題的求解，包括數據預處理和後處理，需要260分鐘以內輸出報表，供業務使用）為例，諾亞自研求解器主要包括了模型化簡，線性規劃求解，連續求解，混合整數規劃求解和數據後處理5個部分。其中，連續求解的模組源自華為供應鏈的特殊業務訴求，其主要作用是根據第一輪線性規劃的解為一部分變量添加單邊懲罰目標，從而提升批量生產的滿足率。
技術重點
首先，根據華為供應鏈問題的特點，我們在線性規劃求解部分主要改進了對偶單純形法（dual Simplex）。考慮到約束矩陣的性質，我們設計了更高效的數據結構加速出入基的列更新計算。同時，我們改進了尋找初始基的方法，並添加了多種啟發式方法，在一定程度上防止了約束矩陣退化現象中頻繁無效出入基的現象。由於約束矩陣天然的病態性和數值差異，我們發現在完成實際問題的大規模計算過程中，Fill-in現象會遠比公開的Benchmark嚴重，這個現象會導致矩陣在計算過程中變得更加稠密從而降低計算性能。因此，我們利用AVX-512指令集，重新設計了數據結構，加速底層線性方程組的計算。
在連續求解的部分，由於添加的變數約束佔比不超過10%，因此這一部分我們選擇了原單純形法（primal Simplex）。同時，我們發現變量狀態（例如：upper bound, lower bound, superbasic等）的影響超過了變量取值的影響，據此我們設計了若干啟發式方法來加速狀態的修正，這種修正會降低求解過程中phase I的時間，從而加速全流程求解。事實上，即使是最快的商務軟件在連續求解的過程中計算也不滿足魯棒性，時常由於數值問題影響全流程計算的穩定性，但諾亞自研求解器由於更多啟發式演算法的設計，在日常運營中的穩定性超過當前最好的商務軟件。
在混合整數求解部分，我們採用了branch-and-cut的方法，充分利用cut separation的信息減少branching的決策失誤率。在這裡，分別採用了啟發式和learning的方法，實現了cut selection，加速全流程的求解。
運營效果
諾亞自研求解器已經服務于華為供應鏈多個項目，以多工廠排產任務為例，諾亞自研求解器已經在2020年9月18日上線，協助支撐引擎安全運營。
資料來源: https://mp.weixin.qq.com/s/xbzIlj4Togx2MDSAkgCs8g
— 完 —
