4-3 供應鏈和EDA中的學習輔助大規模優化.pdf

《4-3 供應鏈和EDA中的學習輔助大規模優化.pdf》由會員分享，可在線閱讀，更多相關《4-3 供應鏈和EDA中的學習輔助大規模優化.pdf（28頁珍藏版）》請在三個皮匠報告上搜索。

1、LEARNING-AIDED L ARGE SCALE OPTIMIZATION IN SUPPLY CHAIN&EDA 甄慧玲 華為 主任工程師|01Industrial Optimization Problems&Practical Bottleneck02目錄CONTENT|03 04Incremental Computation&Effective InitializationWhether Learning Can Help?Conclusions&Some Insights|01Industrial Optimization Problems&Practical Bottlenec

2、kConstraint Optimization&Mathematical Solver價值：Gurobi年收益1億美金+，XPRESS 年收益11億美金+實用性：彌補了純啟發式的不足，以數學模型為媒介，在數學模型限定的范圍內可以執行更加高效的啟發式搜索特點：求解器從來不排斥啟發式方法，當前求解器即使是開源版本也包含上百種的啟發式策略。求解器和啟發式方法的最大不同在于數學模型。約束規定了最大的搜索空間，并規定了所有可能的搜索路徑，在這樣的路徑下不同的啟發式方法高效配合。約束優化的一般數學模型：數學方法數據結構+programming skills輸入輸入 根據目標和約束的形式，數學優化模型往往

3、分成以下幾類：線性規劃（Linear Programming）a)約束和目標全都是線性的b)變量是浮點數 混合整數規劃（Mixed Integer Programming）a)約束和目標都是線性的b)一部分變量必須是整數 二次規劃（Quadratic Programming)a)目標或約束中含有x2b)有些文獻顯示nonlinear programming，但人類目前可以求解的模型其實不包括通用的三次的模型（例如：約束或者目標中含有x3）隨機規劃（Stochastic Programming）a)目標，約束受到隨機擾動，需要計算的是平均意義下的最優解 約束規劃（Constraint Progr

4、amming）a)約束中含有特殊約束：集合約束：x屬于或者不屬于A；順序約束：x和y之間x必須比y先到達（排隊模型、調度模型）SAT(Boolean Satisfactory)a)所有的變量均是布爾變量（0-1），沒有目標，一般不需要解的評估b)SAT模型可以轉化成MIP。目標約束Mathematical Programming優化問題的求解空間是約束定義的 求解器：給定一個數學模型，得到模型中變量的合法的并且達到目標的賦值目標用于評估求解質量|線性問題求解SimplexSimplex方法的核心：將優化問題轉化成一系列線性方程組的求解問題本質上是在凸多面體的頂點上，根據目標最優化方向在眾多頂點

5、上進行迭代，直到目標無法再優化為止。Simplex現有技術核心步驟為入基選擇：基于當前頂點，選擇哪一個方向作為下一步移動，能夠進一步優化目標函數？出基選擇：確保移動步長是合法，即如何從一個“基可行解”另一個“基可行解”？最優性檢驗：當前解是否已是最優解？Simplex在計算中可能碰到的問題：不斷迭代的線性方程組求解，帶來的浮點數的計算誤差入基變量選擇不準確，浪費搜索次數出基變量選擇不準確，影響矩陣的條件數穩定性初始解往往比最優解剛耗時 Simplex方法的可視化：總是從凸多面體的一個頂點，找下一個更合適的頂點，從而找到最優解。第一個頂點：可行解找初始可行解找最優解線性方程組求解選擇變量，完成增

6、量式更新|離散問題求解Branch and Bound Branch and bound（BB）是一種通用的搜索策略，并不局限于任何頂層模型的設計和結構。Branch and bound的核心分兩部分：Branch selection Conflict propagation 以Largest neighborhood search為例，說明BB策略在啟發式方法中的應用。不斷的分支，完成對求解空間的搜索過程。Bound:利用求解的中間信息完成對搜索空間的pruning lower bound是指搜索過程中一個partial solution（比如上圖插入2后形成的3個partialsoluti

7、on）的目標值。由于當前只考慮了局部信息，因此，當考慮了全局約束時，最終目標值不可能比這個lower bound更好（minimize情況）。upper bound是指搜索過程中找到的一個feasible solution（比如上圖插入4后形成的12個completed solution中滿足所有約束的就是feasible solution）的目標值。Conflict propagation&backtrack:如果存在某支路的lower bound比upper bound還要差，那么該支路顯然是沒有繼續往下的必要了，可以剪去?；旌险麛狄巹潱∕ixed integer programming,

8、MIP）和Boolean Satisfactory(SAT)是兩類典型的BB搜索的應用。（MIP）（SAT）MIP&Branch and Bound約束和變量化簡(重點不在效率，而在效果）構建松弛模型，修正presolve結果求解根節點模型，得到初始解從待修整節點中，選擇一個執行修整約束化簡通過不斷迭代，完成變量修整，得到最優解求解對應連續模型維護決策樹，完成分支選擇利用中間求解信息，添加額外約束，加速求解7.6x7.6x1.5x1.5x1.3x1.3x1.2x1.2x1.5x1.5x3.8x3.8x4.6x4.6x2.7x2.7xTips:松弛模型：對原模型的代理模型，通過求解松弛模型得到初

9、始解 Cuts或Cutting planes：不屬于原模型，為加速原模型求解而額外添加的約束混合整數規劃（MIP）求解流程：通過求解一系列的線性規劃（LP）問題，得到最優解。一系列：branch and bound中的branch來決定不同LP的求解順序 當選錯了一個LP后，會返回bound，縮小搜索空間（不同約束之間conflict propagation）近6年不同商業求解器著重改進的模塊?？梢钥闯?，提升presolve的效果是商業求解器的重點從branch and bound的搜索框架來看，branch的選擇和bound（包括cut和conflict的處理）線性規劃（Linear pro

10、gramming）混合整數規劃（Mixed Integer programming）求解器在供應鏈、求解器在供應鏈、Cloud BU、海思等場景都有重要應用、海思等場景都有重要應用|SAT求解器的核心流程依然是branch and bound方法從初始assignments出發，通過不斷分支策略，找到符合全部約束（clause）的解，或者證明該問題無解（UNSAT），即任何約束都不可能同時滿足解作為求解器，除了核心搜索策略以外，SAT求解器內也包含：preprocessing，以及對問題結構的探測（kissat_sweep,2021）求解過程會配合各種啟發式策略：restart，local s

11、earch，probing核心策略1：當前SAT求解器核心方法是conflict-driven clause learning，利用錯誤的搜索信息，構建conflict 約束，不斷縮小搜索空間核心策略2：與MIP中conflict需要配合不同的Propagator以及LP的浮點數計算，在SAT中主要考慮non-chronological的UIPSAT&Branch and Bound|建模時間 求解時間？Motivation I:ATPG場景中，SAT引擎的求解性能，一直都卡到了circuit-to-CNF的效率上（如下圖）原因：存儲數據結構：鏈表，以及 lazy data structure

12、 不同故障對應的CNF(對應的故障的激發和傳播)的不同clause之間，很難嚴格排序，無法很好的利用目前通用的SAT求解器的數據結構；工業電路的設計中每個gate最多4-input，每個clause涉及的Literal少，但clause的個數多，會從而浪費了大量的IO耗時。以ATPG數據為例，上圖展示了對于大部分故障而言，circuit-to-CNF建模時間求解時間。橫軸：fault index；縱軸：時間（微秒）以其中一個故障為例，右圖展示了不同處理模塊具體的時間占比。|02Incremental Computation&Effective Initialization 將每個待選的非基變量

13、以及對應的reduced cost值維護在堆棧結構中；在完成了排序后，就可以將堆的根節點進行輸出，即對下游模塊輸出選擇的入基變量；單純形法的相鄰迭代之間，為了計算效率考慮，會近似計算矩陣的逆，即只有部分的基變量對應的reduced cost會發生變化，因此只需要在上述堆棧中部分更新節點的值，以及調整節點順序，維護最大堆性質處理手段 I 合適的數據結構+增強過程數據的利用Step 1:將top 1檢索問題更改為最大堆的維護問題，并將全局矩陣求逆轉化成增量計算，提升大規模問題的計算性能 首先我們要根據前M輪被選中變量的頻率構造這K個待選變量的概率向量（成反比的）；以e-greedy方式以及概率向量

14、，從K個變量中挑選出一個變量;3)記錄并輸出被選中的變量Step 2:基于歷史記錄的概率地挑選約束，增強對搜索過程數據的利用。通用問題的實驗效果：在大規模問題的求解中（變量、約束個數均超過百萬以上量級），本方法平均降低原有simplex計算時間50%以上。新的更新方式不僅降低了檢索的時間復雜度，充分利用了優化的過程數據，同時，增量更新一定程度上降低了全局更新所帶來的浮點數計算數值誤差的影響，提升求解的穩定性。目前該數據結構已經合并入華為云天籌求解器，并在公司內部服務供應鏈、CBG、能源多個場景。|標準求解器在求解時候通過包含下面三個步驟：本發明在次流程上增加了如下幾個模塊，分別加速第一次求解和

15、后面若干次迭代求解完成包絡預預測：子問題包含了原問題的主干，但是容易求解完成修正：通過子問題最優解的變量狀態初始化原問題根據問題性質選擇部分重要約束組成子問題現實情況中，往往一次求解沒法滿足要求，因此在第一次求解之后還會根據解生成一批新約束加到模型中繼續迭代求解使前一次求解的最優解，在可行域被改變之后，能夠調整到可行域中，從而加速算法的啟動處理手段 II 增量計算（MIP）在供應鏈真實問題的計算效果：對于原有Hard problem（給定時間內無法求解或者耗時超過平均計算時間2倍+），平均可提升性能70%以上。新方法舊方法但不是對每個問題均適用：針對相對easy的問題，這種方法并不適用。會由于

16、增加了迭代的次數，而帶來了更多的浮點數數值計算誤差，從而降低計算性能。不可以按照規模來判斷問題的難易程度，因此，本方案常作為傳統直接求解方案的替補方案。對本方法性能的最關鍵步驟：采樣的有效性，從而直接影響了增量方法對全局搜索空間的不斷化簡效果。在ATPG中，我們也實現了兩種SAT-based ATPG的計算框架：Incremental UNSAT&Incremental SAT1.將電路文件轉成graph，依托電路結構信息實現incremental算法（分成UNSAT和SAT兩種情況）。2.優勢：從而降低CNF generation時間的占比，從而降低SAT使用瓶頸，提升全流程性能；利用SAT

17、求解器對partial assignments的處理，提升求解以及UNSAT問題的證明性能。Incremental UNSAT Proof After marking the fault site,a bounded depth first search traversal toward the POs is performed.It stops after reaching all fan-out gates with a certain depths.If the SAT solver proves the unsatisfiabilityof this partial SAT insta

18、nce,the fault is proven to be untestable.If,on the other hand,the SAT solver finds a satisfying solution for the partial SAT instance,the partial SAT instance has to be augmented.Augmented faults has a certain depth,extra local information is added:local fault propagation information(x_PO=1 at augme

19、nt)is added as a new clauses.Incremental UNSATIncremental SATIncremental SAT Proof The fault is still injected first and all influenced POs are determined.Only one fan-in cone is added.This partial SAT instance is then given to the SAT solver.If the SAT solver finds a satisfying solution,the fault i

20、s classified as testable.If not,no classification can be given.The fault could still be testable through the observation at another PO.i.e.,the SAT instance must be extended.處理手段 II 增量計算（SAT）實驗效果：利用增量計算，SAT的平均計算性能提升20%以上。但是：如果問題是UNSAT，但是選用了Incremental SAT，反而會降低計算性能。因此不同的增量計算框架，在增量求解前，高效識別問題類型是關鍵。|處理

21、手段 III 依托問題結構的預處理方法（MIP）將問題的結構特征引入presolve中，充分利用結構特征帶來的信息，增強presolve的化簡能力，從而化簡待求解的問題規模。更新后的計算框架如下。在供應鏈真實問題中得到驗證，是目前少數幾個穩定上線的learning-driven的求解方案之一。a)相比默認presolve方法，平均提速64.37%(從平均425s降低到151s)b)相比基于經驗參數的presolve方法，平均提速18.59%c)相比基于經驗啟發式的presolve，平均提速18.53%當前平均求解時間，對比性能最好的商業工具Gurobi，平均提升性能50%以上(Gurobi的平

22、均計算時間320s)。對問題結構的處理主要體現在離線訓練深度模型部分：將問題的稀疏度、數值特征、約束+變量規模、目標函數的系數特征等當做問題的綜合特征，訓練分類器。為不同特征匹配合適的Presolve算子順序，以及參數配置。利用訓練好的模型在新的問題上完成presolve算子順序和參數配置。|處理手段 IV 高質量的初始解（MIP）將對問題結構信息的處理，引入presolve后的初始模型構造中。針對presolve后的模型（如下圖）執行右圖流程，在根節點完成新的松弛問題的構造：根據該流程，原有求解流程被更改成：Key insights：修改模型的性價比修改求解方法。通過更新松弛模型，得到新的松

23、弛解，從而替代原有的初始解。1.首次通過整數變量所在約束，構造upper bounds，修正Presolve后的模型，從而構造了新的松弛模型（通過求解新的松弛模型，得到更好的初始解，降低需要修整的變量個數，從而縮短全流程計算時間）2.構造方法的理論保證可通過gomory cuts得到(但不同的是，不是利用中間解的信息，而是利用整數變量所在模型的幾何信息)，計算穩定性有保證|處理手段 IV 高質量的初始解（MIP）1.本發明方案中的核心發明點在華為供應鏈多工廠排產問題的混合整數規劃MIP任務上的表現，可以發現，大規模問題上，本發明方案能提高10%以上的計算性能2.本發明方案中的核心發明點+從屬發

24、明點在華為供應鏈多工廠排產問題的整數規劃任務上的表現，可以發現自2020年9月18日作為安全備份求解器上線服務多工廠排產問題，沒有發生數值不穩定的現象，穩定在8點半以前輸出任務令，并通過了業務測試，滿足日常生產需求。在這期間（2020年9月18日-現在），Gurobi發生了多次由于數值不穩定而無法收斂導致的算法回卷重算問題，而自研求解器全部穩定輸出結果。更新松弛模型的幾何含義：針對原有問題，得到新的convex hull，該convex hull可以通過一般方法（原有方法）得到距離最優值更“近”的初始點，從而提升搜索性能。本方案的實驗效果：紅色實線即為得到的新的convex hull。|03W

25、hether Learning Can Help?學習優化研究 JiayiZhang,Chang Liu,JunchiYan,Xijun Li,Hui-Ling Zhen,Mingxuan Yuan:A Survey for Solving Mixed Integer Programming via Machine Learning.CoRR abs/2203.02878(2022)WenxuanGuo,Junchi Yan,Hui-Ling Zhen,Xijun Li,Mingxuan Yuan,YaohuiJin:Machine Learning Methods in Solving th

26、e Boolean Satisfiability Problem.CoRR abs/2203.04755(2022)機器學習方法使能的MIP求解器方法1機器學習方法使能的SAT求解器方法2結合優化和機器學習，目前在google scholar上盛行的研究方向主要分成兩類：具體的啟發式算法的加速；不同啟發式算法的協同。|方式1：Learning to Improve HeuristicsStrong branchingSolving Mixed Integer Programs Using Neural Networks(Google Deepmind,2020 Dec)核心思路：Neural

27、branching:learning to branch的deep network版本。MIP變成二部圖以及GNN-embedding沒有變化，與2017年后流行的文章一致。Neural diving:利用子問題的partial assignments學習更好的dual bounds 測試結果：在測試的幾類問題上，有明顯提升。但是，針對MIPLIB，尤其是難例，幾乎沒有提升（在MIP求解器中，gap通常小于10-6,否則沒有得到解）。當前這套方法，只適合0-1 MIP(SAT)，原因：盡可能的回避mixed中浮點數的帶來的數值計算的挑戰。處理核心：Candidate variables rep

28、resentation B&B Tree state representation representation 網絡結構：GNN-based embedding structure+deep classifier 統計特征：LP bound and solution,statistics on search participation current node(depth,bound),tree composition(nodes explored,open,leaves),aggregated scores,open nodes statistics,past branchingLearn

29、ing to branch（當前學術文章中最流行的嵌入方式之一,2018）實驗結果：嵌入SCIP的branch策略中，相比本來的branch策略，平均降低求解時間50%以上。|核心策略:a)Motivation：將組合優化求解器當做深度模型的一層，從而利用深度模型的端到端訓練的過程，完成組合優化問題的求解.b)訓練過程：實驗結果：a)在不同的組合優化問題上測試，包括TSP、set cover、graph matching等。實驗表明該方式可以用來當做黑盒組合優化求解器。b)缺點：當前可以處理的組合優化問題，規模都很小。這類組合優化問題都被認為是無約束的組合優化問題（直接從圖上完成計算），大規模

30、約束可能會帶來新的挑戰。20方式2：Learning to Replace HeuristicsDIFFERENTIATION OF BLACKBOX COMBINATORIAL SOLVERS|Learning to choose smart primal heuristics 處理核心：利用data-driven方法判斷如何更好的搭配的primal heuristic方法 統計特征：Global/Depth Features:gap/depth related metrics to describe current state of search Node LP features:node

31、 LP relaxation solution to describe node characteristics Scoring Features for Fractional Variables:from diving heuristics to select the next variable to fix在MIPLIB上，平均降低決策次數1.5%，平均提升求解性能3.7%在GISP上，平均降低決策次數23%，相同時間內平均提升求解質量13%。Learning When to Use a Decomposition 發現是否真的有結構，從而更smart的選擇是否用分解方法 實驗：SCIP和

32、GCG平均分別提升性能27%和42%。發現如何將參數scale（歸一化），讓問題的結構對求解更友好。實驗：給定數據集上MIP求解性能平均提升28%。Learning to Scale MIP值得注意的是，商業求解器XPRESS也在產品版本更新時，提到了auto-scaling方法的選項，初步判斷該方法已經被集成到了求解器中。商業工具怎么玩？Learning to Choose|Our Paper Works I MIP求解器Learning to Reformulate for Linear Programming，Huawei,Submitted to NeurIPS 2022YORDLE:

33、An Efficient Imitation Learning for Branch and Bound,NeurIPS 2021 ML4CO1 Li,Xijun,Qingyu Qu,Fangzhou Zhu,Jia Zeng,Mingxuan Yuan,Kun Mao,and Jie Wang.Learning to Reformulate for Linear Programming.arXiv e-prints(2022):arXiv-2201.2 Qu,Qingyu,Xijun Li*,and Yunfan Zhou.YORDLE:An Efficient Imitation Lear

34、ning for Branch and Bound.“NuerIPS 2021 ML4CO competition首次提出在建模端通過重排優化求解器效率二部圖+GCN提取規劃問題結構信息指針網絡輸出變量/約束重排序強化學習方式訓練上述網絡在NeurIPS 2021 ML4CO數據集以及華為供應鏈排產數據集上求解，使能開源、商業求解器（SCIP/CLP/Gurobi）效率提升15%propose a hybrid sampling strategy based on Pseudocost branching and active constraint methods to generate da

35、taset.develop a data selection method based on BAIL algorithm to select the state-action pairs that possess higher cumulative reward.利用更少（僅20%）的數據訓練，性能大幅超越（40%+）基線算法(NeurIPS19)，獲得學生榜單第一，總榜第二Cumulative RewardBest Action Imitation Learning(BAIL)|Learning to cut 處理核心：如何利用中間求解信息構造更高質量的Cut 在啟發式的cut候選集中選擇

36、合適的Cut在不同的問題上，相同時間平均提升求解質量15%以上我們在供應鏈真實問題中實現了Cuts selection,平均降低求解時間10%以上。處理核心：通過Learning 對問題實現reformulate，從而發現對求解友好的問題結構或者數值歸一化方法。Learning-aided reformulation的模型，會更方便執行高效求解方法。By learning By ManualLearning to ReformulateOur Paper Works I MIP求解器|24我們利用learning-aided branching方法，從UNSAT和SAT的求解上分別做了測試.T

37、raining Set：Using the optimization information to construct training set,rather than CNFGenerate DRAT proof for each UNSAT instance，label each literal if it exists in UNSAT core or DRAT proof.Training set is made of the pickles from branching rules.實驗設置：a)Vanilla SAT Solver:CaDiCal 2018 b)Instance:S

38、AT competition.c)Neuro-CaDiCal is the learning-assisted CaDiCal.d)Learning-assisted strategy+doubly linked list:676s-374s.e)Our modified SAT solver has won 4thposition in SAT competition in EDA track 2021.Comparison on branching decisions numbers：decrease 10%decision numbers in optimization.Training

39、 Network:GNN-based network and predict whether the literal is in UNSAT core.Make decision according to the rank of literals during SAT solving.Update the embedding information of literal and clausesrespectively.Test:Embedding the results in the Incremental framework：classify the literals and guiding

40、 the branching and partition resultsOur Paper Works II SAT求解器|Learning to choose method in ATPG?但是相似的方法用到ATPG中時，最高預測準確率70%。原因：ATPG中數據結構主要考慮故障的傳播和激發，即使在相似的電路中，不同數據規模/性質的數據比例，也各不相同。設計方案（流程圖如下）：Our Paper Works III ATPG引入生成模型，完成數據增強。a)生成模型選擇DGAN，兩個discriminators,一個用來判斷結構特征的相似性，一個用來判斷求解質量的相似性（通過conflict的

41、統計信息完成判斷）在增強后的數據上，訓練分類器，識別不同故障類型，隨后按照類型完成方法選擇。實驗效果：生成模型可以完成數據增強么：90%以上的數據可以保持原有數據的類型，并以損失很低的比例，維持原有的結構特征。增強后的數據可以輔助同樣的learning model提升預測準確性么？平均預測準確率提升到90%+新的模型可以在選定的數據上，可以提升SAT-based ATPG的性能么？平均可以提升30%+的求解性能，端到端提升ATPG性能7%+。|04Conclusions&Some Insights|Conclusions工業中的優化問題常見瓶頸是大規模以及約束復雜，因此高效的處理大規模約束是處理工業優化問題的核心。在合適的建模方式下，求解器在工業優化問題中有非常重要的地位。但考慮到不同的場景特點，在一些高頻調用的模塊中，優化問題的瓶頸不一定是求解，很可能是建模。因此，合適的建模方法很重要。AI是可以輔助優化求解器進行加速的，但目前，端到端的利用AI替代傳統求解器還有比較長的一段路要走目前，對AI的利用，更多的圍繞在方法選擇、采樣/selection、超參調優等場景。生成模型和數據增強在工業中，可能會有比較大的應用前景。非常感謝您的觀看|