ICS35.240.01CCSL67團(tuán) 體 標(biāo) 準(zhǔn)T/ZSA266-2024CPU并行整數(shù)線性規(guī)劃求解器CPUparallelintegerlinearprogrammingsolver2024-11-21發(fā)布 2024-11-22實施中關(guān)村標(biāo)準(zhǔn)化協(xié)會 發(fā)布T/ZSA266-2024T/ZSA266-2024PAGE\*ROMANPAGE\*ROMANII目 次前 言 II范圍 1術(shù)語和定義 1技術(shù)要求 1可行解生成能力 1高質(zhì)量解生成能力 2輸入輸出支持能力 2問題規(guī)模支持能力 3誤差控制能力 3測試方法 3測試環(huán)境 3可行解生成能力測試 4高質(zhì)量解生成能力測試 4輸入輸出支持能力測試 4問題規(guī)模支持能力測試 4誤差控制能力測試 4檢測結(jié)果 4附 錄 A （資料性）測試實例最優(yōu)已知解 5附 錄 B （規(guī)范性）測試實例 7參 考 文 獻(xiàn) 9前 言本文件按照GB/T1.1—2020《標(biāo)準(zhǔn)化工作導(dǎo)則 第1部分：標(biāo)準(zhǔn)化文件的結(jié)構(gòu)和起草規(guī)則》的規(guī)定起草。本文件由中關(guān)村標(biāo)準(zhǔn)化協(xié)會人工智能分技術(shù)委員會提出并歸口。（北京本文件主要起草人：林錦坤、羅川、張立明、王藝源、張新杰、慕超。T/ZSA266-2024T/ZSA266-2024PAGEPAGE1CPU并行整數(shù)線性規(guī)劃求解器范圍本文件規(guī)定了CPU并行整數(shù)線性規(guī)劃求解器的技術(shù)要求和測試方法。本文件適用于需要利用CPU多核特性來有效求解大規(guī)模整數(shù)線性規(guī)劃問題的軟件工具（以下簡稱“求解器”）的設(shè)計、開發(fā)及驗收。術(shù)語和定義下列術(shù)語和定義適用于本文件。整數(shù)線性規(guī)劃問題integerlinearprogrammingproblem一種優(yōu)化問題，其目標(biāo)是最大化或最小化線性目標(biāo)函數(shù)，同時滿足一組線性約束條件，且所有變量都限制為整數(shù)值。CPU并行整數(shù)線性規(guī)劃求解器CPUparallelintegerlinearprogrammingsolver一種利用CPU的多核和多線程能力來加速整數(shù)線性規(guī)劃問題求解的軟件工具。可行解feasiblesolution在整數(shù)線性規(guī)劃問題中，滿足所有約束條件的解。高質(zhì)量解highqualitysolution在整數(shù)線性規(guī)劃問題中，目標(biāo)函數(shù)接近最優(yōu)的可行解。技術(shù)要求可行解生成能力可行解生成能力為在有限的時間內(nèi)找到可行解的能力。可行解生成能力指標(biāo)滿足表1要求。表1 可行解生成能力指標(biāo)實例類型線程數(shù)實例數(shù)可解實例數(shù)常規(guī)實例單線程112個≥80個32線程≥81個64線程≥82個大規(guī)模實例單線程9個≥1個32線程≥2個64線程≥3個注1：可解實例數(shù)表示求解器成功獲得可行解的實例個數(shù)。注2：常規(guī)實例是指變量數(shù)少于100萬的問題實例，大規(guī)模實例則是指變量數(shù)為100萬及以上的問題實例。注3：實例選取自于MIPLIB2003MIPLIB2010MIPLIB2017的數(shù)據(jù)集中標(biāo)記為困難和未解決的具有可行解的整數(shù)線性規(guī)劃實例，總共121個實例，包括常規(guī)實例112個，大規(guī)模實例9個。注4：為確保在實際應(yīng)用場景中，特別是對于需要實時決策的場景，求解器提供優(yōu)化方案的能力，設(shè)定運(yùn)行時間常規(guī)實例最多10秒，大規(guī)模實例最多60秒。高質(zhì)量解生成能力?表示，其中?(?)的計算方法見公式(1)~公式(3)。?0,1,?????0,1,?????ax?????,

=???=0??)=

???????????, else.

???????????1??=1, t為止沒有找到可行解???, 否則??是到時刻t

???????????2? ???)=? ????=Σ???1????1 ??????????????3?=0

1式中：??? 23年2月1A；???T ——所設(shè)定的運(yùn)行截止時間；? ——?∈,?,?∈,??1高質(zhì)量解生成能力指標(biāo)滿足表2要求。表2 高質(zhì)量解生成能力指標(biāo)實例類型線程數(shù)實例數(shù)???常規(guī)實例單線程112個≤0.65032線程≤0.56064線程≤0.550大規(guī)模實例單線程9個≤0.87032線程≤0.86064線程≤0.840輸入輸出支持能力求解器支持MPS格式文件輸入及編程API接口輸入，且按規(guī)范輸出結(jié)果。MPSMPS格式包括固定格式和自由格式。8自由格式：字段之間用空格字符分隔。名稱可以任意長，但不能包含空格。求解器可以讀取這兩種MPS類型，并自動識別它們的格式。API求解器應(yīng)支持以下API接口輸入支持功能：提供配置環(huán)境信息的類，用于設(shè)置求解器參數(shù)，如求解終止時間，線程等；提供模型類，支持添加變量、添加約束、求解模型等；提供變量類，用于描述變量；提供約束類，用于描述約束；提供線性表達(dá)式類，用于描述線性表達(dá)式。輸出支持能力問題規(guī)模支持能力求解器應(yīng)支持至少1億級別變量的輸入，在求解過程中求解器正常運(yùn)行，不發(fā)生崩潰退出的情況。誤差控制能力求解器求解結(jié)果應(yīng)能有效控制誤差，多次運(yùn)行結(jié)果的目標(biāo)值之間誤差應(yīng)不超過±10-12。測試方法測試環(huán)境測試服務(wù)器測試服務(wù)器須至少滿足以下要求：CPU：128個物理核心；內(nèi)存：1TB。測試試驗使用服務(wù)器參考配置如下：AMDEPYC7763CPU@2.45GHz；128個物理核心、1TB內(nèi)存；Ubuntu20.04Linux操作系統(tǒng)。機(jī)器性能基準(zhǔn)實例使用來自DIMACS的9個實例，分別為：e18.stp；b) i640-341.stp；fnl4461fst.stp；world666.stp；cc3-12p.stp；alue7080.stp；alut2625.stp；es10000fst01.stp；lin37.stp。基準(zhǔn)代碼使用來自DIMACS的基準(zhǔn)代碼dimbench.cpp。時間換算分。不同服務(wù)器的時間換算方法如下：創(chuàng)建一個臨時文件夾/目錄（以下稱為“temp”）；temp；temp；運(yùn)行可執(zhí)行文件（temp內(nèi)）score；score519.4的比例?519.4在該服務(wù)器上評估求解器性能時，常規(guī)實例和大規(guī)模實例的運(yùn)行時間分別設(shè)定為10?

秒和60?秒。可行解生成能力測試對于每一個常規(guī)實例，分別使用單線程、326410對于每一個大規(guī)模實例，分別使用單線程、326460注：測試實例見附錄B，附錄表格中說明了實例的變量數(shù)量、約束數(shù)量，一般變量數(shù)量與約束數(shù)量越大，實例越難被求解。高質(zhì)量解生成能力測試對于測試實例集中的每一個實例，分別使用如下設(shè)置運(yùn)行求解器，并計算求解器在該實例上的??：?對于每一個常規(guī)實例，分別使用單線程、326410在該時間內(nèi)的??。?對于每一個大規(guī)模實例，分別使用單線程、326460器在該時間內(nèi)的??。?輸入輸出支持能力測試APIMPS對于求解器能夠成功找到可行解的問題實例，輸出目標(biāo)函數(shù)的數(shù)值和每個變量相應(yīng)的賦值。其中，對于賦值為零的變量，可以選擇不輸出其值以簡化結(jié)果。問題規(guī)模支持能力測試使用求解器提供的API接口，建立變量數(shù)超過1億的數(shù)學(xué)模型然后求解，求解過程中程序正常運(yùn)行，不發(fā)生內(nèi)存溢出、程序崩潰的情況。誤差控制能力測試1010。檢測結(jié)果求解器在滿足環(huán)境配置，并按要求進(jìn)行測試，達(dá)到以下結(jié)果視為通過：3.13.2求解器順利通過輸入輸出支持能力測試和問題規(guī)模支持能力測試；誤差控制能力測試的結(jié)果誤差未超過允許范圍。A.1 實例最優(yōu)已知解測試用實例最優(yōu)已知解見表A.1。

附 錄 A（資料性）測試實例最優(yōu)已知解表A.1實例最優(yōu)已知解序號實例名稱目標(biāo)值序號實例名稱目標(biāo)值12club200v15p5scn.mps-7049neos-4360552-sangro.mps-82a2864-99blp.mps-25750neos-4531126-vouga.mps525053.6093academictimetablebig.mps42751neos-4954274-beardy.mps20946.484bab1.mps-218764.8952neos-954925.mps-237.768895bab2.mps-357544.3153ns1828997.mps86bab3.mps-656214.9554ns1853823.mpsNA7bab6.mps-284248.2355ns1854840.mpsNA8bley_xs1.mps3940855.4756ns894236.mpsNA9bley_xs1noM.mps3873690.7757ns894786.mpsNA10cdc7-4-3-2.mps-29458nu120-pr3.mps2813011circ10-3.mps28059nursesched-medium-hint03.mps11512comp12-2idx.mps29160opm2-z10-s4.mps-3326913comp21-2idx.mps7461opm2-z12-s14.mps-6429114d10200.mps1243062opm2-z12-s7.mps-6551415d20200.mps1224063opm2-z12-s8.mps-5854016datt256.mpsNA64p6b.mps-6317ds.mps93.5265pb-gfrd-pnc.mps889018ds-big.mps195.49899766pb-grow22.mps-41524319ex1010-pi.mps23567pb-market-split8-70-4.mpsNA20f2000.mps181068pb-simp-nonunif.mpsNA21fhnw-sq2.mps069proteindesign121hz512p19.mps338222graph20-80-1rand.mps-670proteindesign121hz512p9.mps147323graph40-20-1rand.mps-1571protfold.mps-3124graph40-40-1rand.mps-972pythago7824.mps025graph40-80-1rand.mps-773pythago7825.mpsNA26hanoi5.mps193174queens-30.mps-4027highschool1-aigio.mps075rail03.mps-867.0939728ivu06.mps142.8676ramos3.mps19229ivu06-big.mps140.7477reblock354.mps-3928052130ivu59.mps93178rmine10.mps-191431kosova1.mps29379rmine11.mps-2508.404132kottenpark09.mps171580rmine13.mps-3495.370733lectsched-1-obj.mpsNA81rmine14.mpsNA34methanosarcina.mpsNA82rmine15.mps-5018.8235neos-2974461-ibar.mps46890617583rmine21.mps-10618.75136neos-3068746-nene.mps61910283.784rmine25.mps-15541.66937neos-3214367-sovi.mps17996585rococoC11-010100.mps2088938neos-3237086-abava.mps086rococoC12-010001.mps3404539neos-3322547-alsek.mps40087rococoC12-111000.mpsNA40neos-3355120-tarago.mps-1111596688s100.mps-0.169723541neos-3355323-arnon.mpsNA89s1234.mps2942neos-3426085-ticino.mps22590scpj4scip.mps12843neos-3426132-dieze.mps40791scpk4.mps32144neos-3530905-gaula.mps15992scpl4.mps26245neos-3594536-henty.mps40122493scpm1.mps54446neos-3603137-hoteo.mpsNA94scpn2.mps49047neos-3682128-sandon.mps3466677095seymour.mps423序號實例名稱目標(biāo)值序號實例名稱目標(biāo)值48neos-4165869-wannon.mps29396seymour-disj-10.mps287表A.1（續(xù)）97sorrell3.mps-16110supportcase30.mpsNA98sorrell4.mps-24111t1717.mps15826099sorrell7.mps-197112t1722.mps109137100sp97ar.mps660706000113tokyometro.mps8263.1101splice1k1.mps-394114tw-myciel4.mps10102stp3d.mps493.71965115usafa.mps160.167136103sts405.mpsNA116v150d30-2hopcds.mps41104sts729.mpsNA117wnq-n100-mw99-14.mps259105supportcase10.mps7118woodlands09.mps0106supportcase19.mps12677206119z26.mps-1192107supportcase2.mps65120zib01.mpsNA108supportcase22.mps117121zib02.mpsNA109supportcase3.mps0測試實例測試實例見表B.1。

附 錄 B（規(guī)范性）測試實例表B.1測試實例序號實例名稱變量數(shù)量約束數(shù)量序號實例名稱變量數(shù)量約束數(shù)量1d10200200094744graph40-40-1rand1026003609002lectsched-1-obj287185010845graph40-80-1rand28364810501123methanosarcina79301460446hanoi53862163994ns185382321344022452647highschool1-aigio320404925685ns185484013575414361648ivu06-big227773611776ns8942369666821849ivu0678723911777ns894786272781679450ivu59256999634368nu120-pr38601221051kosova16142533049319opm2-z12-s141080031950852kottenpark09289302632554710opm2-z12-s71080031950853neos-2974461-ibar21473021410711p6b462585254neos-3068746-nene4890466412pb-simp-nonunif23848145191255neos-3214367-sovi4318724413protfold1835211256neos-3237086-abava501926947214rmine1084396527457neos-3322547-alsek1001000200015rmine143220526853558neos-3355120-tarago78008663316rococoC12-11100086191077659neos-3355323-arnon102482121617seymour-disj-101209510860neos-3426085-ticino468830818sts4054052727061neos-3426132-dieze1155057019sts7297298845262neos-3530905-gaula209020020zib0112471400588704163neos-3594536-henty229242128021zib0237709944904986864neos-3603137-hoteo400310510222club200v15p5scn2001701365neos-3682128-sandon78801492023a2864-99blp2007872211766neos-4165869-wannon317288586524academictimetablebig16897416766167neos-4360552-sangro102724601225bab1611526068068neos-4531126-vouga169996769426bab21479121724569neos-4954274-beardy128651735927bab33938002306970neos-95492584718298928bab61142402990471ns1828997272758172529bley_xursesched-medium-hint03342481406230bley_xs1noM3243329073opm2-z10-s4625016063331cdc7-4-3-2118111447874opm2-z12-s81080031950832circ10-327004262075pb-gfrd-pnc2788887433comp12-2idx118631680376pb-grow2225124132034comp21-2idx108631403877pb-market-split8-70-4711735d202004000150278proteindesign121hz512p19258993130136datt2562621441107779proteindesign121hz512p915914530137ds-big174997104280pythago782437401465238ds6773265681pythago782537451467239ex1010-pi25200146882queens-3090096040f200040001050083rail0375877525390541fhnw-sq26509184ramos32187218742graph20-80-1rand162635510785reblock354354019906序號實例名稱變量數(shù)量約束數(shù)量序號實例名稱變量數(shù)量約束數(shù)量43graph40-20-1rand312439906786r