TZSA 266-2024 CPU 并行整数线性规划求解器.docx

ICS35.240.01

CCSL67

团 体 标 准

T/ZSA266-2024

CPU并行整数线性规划求解器

CPUparallelintegerlinearprogrammingsolver

2024-11-21发布 2024-11-22实施

中关村标准化协会 发布

T/ZSA266-2024

T/ZSA266-2024

PAGE\*ROMAN

PAGE\*ROMANII

目 次

前 言 II

范围 1

术语和定义 1

技术要求 1

可行解生成能力 1

高质量解生成能力 2

输入输出支持能力 2

问题规模支持能力 3

误差控制能力 3

测试方法 3

测试环境 3

可行解生成能力测试 4

高质量解生成能力测试 4

输入输出支持能力测试 4

问题规模支持能力测试 4

误差控制能力测试 4

检测结果 4

附 录 A （资料性）测试实例最优已知解 5

附 录 B （规范性）测试实例 7

参 考 文 献 9

前 言

本文件按照GB/T1.1—2020《标准化工作导则 第1部分：标准化文件的结构和起草规则》的规定起草。

本文件由中关村标准化协会人工智能分技术委员会提出并归口。

本文件起草单位：晞德求索（北京）科技有限公司、北京航空航天大学、吉林大学、东北师范大学、上海久章智能科技有限公司、中关村标准化协会。

本文件主要起草人：林锦坤、罗川、张立明、王艺源、张新杰、慕超。

T/ZSA266-2024

T/ZSA266-2024

PAGE

PAGE1

CPU并行整数线性规划求解器

范围

本文件规定了CPU并行整数线性规划求解器的技术要求和测试方法。

本文件适用于需要利用CPU多核特性来有效求解大规模整数线性规划问题的软件工具（以下简称“求解器”）的设计、开发及验收。

术语和定义

下列术语和定义适用于本文件。

整数线性规划问题integerlinearprogrammingproblem

一种优化问题，其目标是最大化或最小化线性目标函数，同时满足一组线性约束条件，且所有变量

都限制为整数值。

CPU并行整数线性规划求解器CPUparallelintegerlinearprogrammingsolver

一种利用CPU的多核和多线程能力来加速整数线性规划问题求解的软件工具。

可行解feasiblesolution

在整数线性规划问题中，满足所有约束条件的解。

高质量解highqualitysolution

在整数线性规划问题中，目标函数接近最优的可行解。

技术要求

可行解生成能力

可行解生成能力为在有限的时间内找到可行解的能力。可行解生成能力指标满足表1要求。

表1 可行解生成能力指标

实例类型

线程数

实例数

可解实例数

常规实例

单线程

112个

≥80个

32线程

≥81个

64线程

≥82个

大规模实例

单线程

9个

≥1个

32线程

≥2个

64线程

≥3个

注1：可解实例数表示求解器成功获得可行解的实例个数。

注2：常规实例是指变量数少于100万的问题实例，大规模实例则是指变量数为100万及以上的问题实例。

注3：实例选取自于MIPLIB2003、MIPLIB2010和MIPLIB2017的数据集中标记为困难和未解决的具有可行解的整数线性规划实例，总共121个实例，包括常规实例112个，大规模实例9个。

注4：为确保在实际应用场景中，特别是对于需要实时决策的场景，求解器提供优化方案的能力，设定运行时间常

规实例最多10秒，大规模实例最多60秒。

高质量解生成能力

对求解过程中目标函数值与最优已知解之间的差距的绝对值进行积分，并除以求解时间，得到整个求解过程的平均质量，用??表示，其中?(?)的计算方法见公式(1)~公式(3)。

?

0,1,???????????

0,

1,

????????????max???????,????

=????=0

?(??)=

??????????????0,

, else.

???????????1

??=1, 如果到时刻t为止没有找到可行解

????, 否则???是到时刻t为止找到的最优的解

???????????2

? ?

?(?)=? ????=Σ????1???????1 ??????????????3

?=0

?=1

式中：

????? ——截止至2023年12月1日为止，实例最优已知解，见