T-ZSA 266-2024 CPU 并行整數(shù)線性規(guī)劃求解器

ICS35.240.01CCSL67團體標準CPUparallelintegerlinearprogrammin中關村標準化協(xié)會發(fā)布IT/ZSA266-2024 2術語和定義 3技術要求 3.1可行解生成能力 3.2高質量解生成能力 3.3輸入輸出支持能力 3.4問題規(guī)模支持能力 3.5誤差控制能力 4測試方法 4.1測試環(huán)境 4.2可行解生成能力測試 4.3高質量解生成能力測試 4.4輸入輸出支持能力測試 4.5問題規(guī)模支持能力測試 4.6誤差控制能力測試 5檢測結果 附錄A（資料性）測試實例最優(yōu)已知解 附錄B（規(guī)范性）測試實例 T/ZSA266-2024本文件按照GB/T1.1—2020《標準化工作導則第1部分：標準化文件的結構和起草規(guī)則》的規(guī)定起草。本文件由中關村標準化協(xié)會人工智能分技術委員會提出并歸口。本文件起草單位：晞德求索（北京）科技有限公司、北京航空航天大學、吉林大學、東北師范大學、上海久章智能科技有限公司、中關村標準化協(xié)會。本文件主要起草人：林錦坤、羅川、張立明、王藝源、張新杰、慕超。1T/ZSA266-2024CPU并行整數(shù)線性規(guī)劃求解器本文件規(guī)定了CPU并行整數(shù)線性規(guī)劃求解器的技術要求和測試方法。本文件適用于需要利用CPU多核特性來有效求解大規(guī)模整數(shù)線性規(guī)劃問題的軟件工具（以下簡稱“求解器”）的設計、開發(fā)及驗收。2術語和定義下列術語和定義適用于本文件。2.1整數(shù)線性規(guī)劃問題integerlinearprogrammingproblem一種優(yōu)化問題，其目標是最大化或最小化線性目標函數(shù)，同時滿足一組線性約束條件，且所有變量都限制為整數(shù)值。2.2CPU并行整數(shù)線性規(guī)劃求解器CPUparallelintegerlinearprogrammingsolver一種利用CPU的多核和多線程能力來加速整數(shù)線性規(guī)劃問題求解的軟件工具。2.3可行解feasiblesolution在整數(shù)線性規(guī)劃問題中，滿足所有約束條件的解。2.4高質量解highqualitysolution在整數(shù)線性規(guī)劃問題中，目標函數(shù)接近最優(yōu)的可行解。3技術要求3.1可行解生成能力可行解生成能力為在有限的時間內找到可行解的能力?？尚薪馍赡芰χ笜藵M足表1要求。表1可行解生成能力指標注2：常規(guī)實例是指變量數(shù)少于100萬的問題實例，大規(guī)模實例則是指變量數(shù)為100注3：實例選取自于MIPLIB2003、MI數(shù)線性規(guī)劃實例，總共121個實例，包括常規(guī)實例112個注4：為確保在實際應用場景中，特別是對于需要實時決策的場景，求解器提供優(yōu)化方案的能力，設定運行時間常2T/ZSA266-20243.2高質量解生成能力對求解過程中目標函數(shù)值與最優(yōu)已知解之間的差距的絕對值進行積分，并除以求解時間，得到整個求解過程的平均質量，用表示，其中P(T)的計算方法見公式(1)~公式(3)。優(yōu)的解……………2ti1ti—ti1……式中：opt——截止至2023年12月1日為止，實例最優(yōu)已知解，見附錄A；Y((t))——到時刻t為止，求解器所找到的最優(yōu)解與實例最優(yōu)已知解的差距函數(shù)；T——所設定的運行截止時間；ti——ti∈0,T,i∈1,…,I—1是求解器找到更優(yōu)解的時刻。高質量解生成能力指標滿足表2要求。表2高質量解生成能力指標P(T)T3.3輸入輸出支持能力求解器支持MPS格式文件輸入及編程API接口輸入，且按規(guī)范輸出結果。3.3.1MPS格式輸入支持能力MPS格式包括固定格式和自由格式。a)固定格式：各種字段從文件中的固定列開始。行名和列名應是8個字符，空格為名稱的一部b)自由格式：字段之間用空格字符分隔。名稱可以任意長，但不能包含空格。求解器可以讀取這兩種MPS類型，并自動識別它們的格式。3T/ZSA266-20243.3.2API接口輸入支持能力求解器應支持以下API接口輸入支持功能：a)提供配置環(huán)境信息的類，用于設置求解器參數(shù)，如求解終止時間，線程等；b)提供模型類，支持添加變量、添加約束、求解模型等；c)提供變量類，用于描述變量；d)提供約束類，用于描述約束；e)提供線性表達式類，用于描述線性表達式。3.3.3輸出支持能力對于求解器成功找到可行解的問題實例，求解器的輸出包括目標函數(shù)的數(shù)值及每個變量相應的賦值。其中，對于賦值為零的變量，可選擇不輸出其值以簡化結果。3.4問題規(guī)模支持能力求解器應支持至少1億級別變量的輸入，在求解過程中求解器正常運行，不發(fā)生崩潰退出的情況。3.5誤差控制能力求解器求解結果應能有效控制誤差，多次運行結果的目標值之間誤差應不超過±10-12。4測試方法4.1測試環(huán)境4.1.1測試服務器測試服務器須至少滿足以下要求：a)CPU：128個物理核心；b)內存：1TB。測試試驗使用服務器參考配置如下：a)AMDEPYC7763CPU@2.45GHz；b)128個物理核心、1TB內存；c)Ubuntu20.04Linux操作系統(tǒng)。4.1.2機器性能基準實例使用來自DIMACS的9個實例，分別為：a)e18.stp；b)i640-341.stp；c)fnl4461fst.stp；d)world666.stp；e)cc3-12p.stp；f)alue7080.stp；g)alut2625.stp；h)es10000fst01.stp；i)lin37.stp。4.1.3基準代碼使用來自DIMACS的基準代碼dimbench.cpp。4.1.4時間換算通過在機器性能基準實例中運行基準代碼，本文件測試試驗所使用服務器的機器分數(shù)為：519.4分。不同服務器的時間換算方法如下：4T/ZSA266-2024a)創(chuàng)建一個臨時文件夾/目錄（以下稱為“temp”）；b)解壓機器性能基準實例集，并將實例復制到temp；c)使用編譯器編譯基準代碼，編譯時開啟全面優(yōu)化，并將可執(zhí)行文件保存到temp；d)運行可執(zhí)行文件（不帶參數(shù)，在temp內），得到一個分數(shù)score；e)計算步驟d）的分數(shù)score與本標準所使用的服務器的分數(shù)519.4的比例按照本文件在該服務器上評估求解器性能時，常規(guī)實例和大規(guī)模實例的運行時間分別設定為秒和秒。4.2可行解生成能力測試對于測試實例集中的每一個實例，分別使用如下設置運行求解器，并統(tǒng)計求解器獲得可行解的實例數(shù)量。a)對于每一個常規(guī)實例，分別使用單線程、32線程和64線程運行求解器10秒。統(tǒng)計在該時間內求解器成功獲得可行解的實例數(shù)量。b)對于每一個大規(guī)模實例，分別使用單線程、32線程和64線程運行求解器60秒。統(tǒng)計在該時間內求解器成功獲得可行解的實例數(shù)量。注：測試實例見附錄B，附錄表格中說明了實例的變量數(shù)量、約束數(shù)量，一般變量數(shù)量與約束數(shù)量越大，實例越難4.3高質量解生成能力測試對于測試實例集中的每一個實例，分別使用如下設置運行求解器，并計算求解器在該實例上的：a)對于每一個常規(guī)實例，分別使用單線程、32線程和64線程運行求解器10秒，并計算求解器在該時間內的。b)對于每一個大規(guī)模實例，分別使用單線程、32線程和64線程運行求解器60秒，并計算求解器在該時間內的。4.4輸入輸出支持能力測試a)通過求解器提供的API接口，設置環(huán)境參數(shù)、添加變量和約束，并使用線性表達式進行建模，最終順利完成求解過程。b)求解器能夠讀取所有測試實例集合中的MPS文件，并執(zhí)行求解。c)對于求解器能夠成功找到可行解的問題實例，輸出目標函數(shù)的數(shù)值和每個變量相應的賦值。其中，對于賦值為零的變量，可以選擇不輸出其值以簡化結果。4.5問題規(guī)模支持能力測試使用求解器提供的API接口，建立變量數(shù)超過1億的數(shù)學模型然后求解，求解過程中程序正常運行，不發(fā)生內存溢出、程序崩潰的情況。4.6誤差控制能力測試重復執(zhí)行求解測試集中的每個實例10次，每次求解結果的目標值之間的差值不超過±10-12。5檢測結果求解器在滿足環(huán)境配置，并按要求進行測試，達到以下結果視為通過：a)求解器在可行解生成能力和高質量解生成能力測試中達到本文件3.1和3.2中設定的性能指標；b)求解器順利通過輸入輸出支持能力測試和問題規(guī)模支持能力測試；c)誤差控制能力測試的結果誤差未超過允許范圍。5T/ZSA266-2024（資料性）測試實例最優(yōu)已知解A.1實例最優(yōu)已知解測試用實例最優(yōu)已知解見表A.1。表A.1實例最優(yōu)已知解1neos-4360552-sangro2neos-4531126-vouga.m3neos-4954274-beardy4586NA7NA8NA9NAnursesched-medium-hint03.NAp6b.mpspb-gfrd-pnc.mpspb-grow22.mpspb-market-split8-70-4.mpsNApb-simp-nonunif.mpsNA0proteindesign121hz512p19.mproteindesign121hz512p9.mps0NA0NANANAneos-3214367-sovi.m0NAneos-3355120-tarago.neos-3355323-arnon.NAneos-3426085-ticinoneos-3426132-dieze.mneos-3530905-gaula.neos-3594536-henty.neos-3603137-hoteo.NAneos-3682128-sandon.6T/ZSA266-2024neos-4165869-wannon.表A.1（續(xù)）NAusafa.mpsNANA70NANA07T/ZSA266-2024