T/ZSA 266-2024 CPU 并行整数线性规划求解器

ICS 35.240.01
CCS L 67
团体标准
T/ZSA 266-2024
CPU 并行整数线性规划求解器
CPU parallel integer linear programming solver
2024-11-21 发布2024-11-22 实施
中关村标准化协会发布

目次
前言............................................................................ II
1 范围................................................................................. 1
2 术语和定义........................................................................... 1
3 技术要求............................................................................. 1
3.1 可行解生成能力................................................................... 1
3.2 高质量解生成能力................................................................. 2
3.3 输入输出支持能力................................................................. 2
3.4 问题规模支持能力................................................................. 3
3.5 误差控制能力..................................................................... 3
4 测试方法............................................................................. 3
4.1 测试环境......................................................................... 3
4.2 可行解生成能力测试............................................................... 4
4.3 高质量解生成能力测试............................................................. 4
4.4 输入输出支持能力测试............................................................. 4
4.5 问题规模支持能力测试............................................................. 4
4.6 误差控制能力测试................................................................. 4
5 检测结果............................................................................. 4
附录A （资料性） 测试实例最优已知解........................................... 5
附录B （规范性） 测试实例..................................................... 7
参考文献......................................................................... 9
T/ZSA 266-2024
II
前言
本文件按照GB/T 1.1—2020《标准化工作导则第1部分：标准化文件的结构和起草规则》的规定
起草。
本文件由中关村标准化协会人工智能分技术委员会提出并归口。
本文件起草单位：晞德求索（北京）科技有限公司、北京航空航天大学、吉林大学、东北师范大学、
上海久章智能科技有限公司、中关村标准化协会。
本文件主要起草人：林锦坤、罗川、张立明、王艺源、张新杰、慕超。
T/ZSA 266-2024
1
CPU 并行整数线性规划求解器
1 范围
本文件规定了CPU并行整数线性规划求解器的技术要求和测试方法。
本文件适用于需要利用CPU多核特性来有效求解大规模整数线性规划问题的软件工具（以下简称
“求解器”）的设计、开发及验收。
2 术语和定义
下列术语和定义适用于本文件。
2.1
整数线性规划问题integer linear programming problem
一种优化问题，其目标是最大化或最小化线性目标函数，同时满足一组线性约束条件，且所有变量
都限制为整数值。
2.2
CPU 并行整数线性规划求解器CPU parallel integer linear programming solver
一种利用CPU的多核和多线程能力来加速整数线性规划问题求解的软件工具。
2.3
可行解feasible solution
在整数线性规划问题中，满足所有约束条件的解。
2.4
高质量解high quality solution
在整数线性规划问题中，目标函数接近最优的可行解。
3 技术要求
3.1 可行解生成能力
可行解生成能力为在有限的时间内找到可行解的能力。可行解生成能力指标满足表1要求。
表1 可行解生成能力指标
实例类型线程数实例数可解实例数
常规实例
单线程
112个
≥80个
32线程≥81个
64线程≥82个
大规模实例
单线程
9个
≥1个
32线程≥2个
64线程≥3个
注1：可解实例数表示求解器成功获得可行解的实例个数。
注2：常规实例是指变量数少于100万的问题实例，大规模实例则是指变量数为100万及以上的问题实例。
注3：实例选取自于MIPLIB 2003、MIPLIB 2010和MIPLIB 2017的数据集中标记为困难和未解决的具有可行解的整
数线性规划实例，总共121个实例，包括常规实例112个，大规模实例9个。
注4：为确保在实际应用场景中，特别是对于需要实时决策的场景，求解器提供优化方案的能力，设定运行时间常
规实例最多10秒，大规模实例最多60秒。
T/ZSA 266-2024
2
3.2 高质量解生成能力
对求解过程中目标函数值与最优已知解之间的差距的绝对值进行积分，并除以求解时间，得到整个
求解过程的平均质量，用� �
�
表示，其中�(�)的计算方法见公式(1)~公式(3)。
�(�