NPBenchmark-SDK

NP 难组合优化问题算法 SDK 与测试数据集.

问题列表

问题名称	文件夹	备注
最大数问题	MaxNumber	热身题, 仅用于熟悉 SDK 的使用
图着色问题	GraphColoring
拉丁方补全问题	LatinSquareCompletion
中心选址问题	PCenter	包含更复杂的 SDK 使用示例
单位成本集合覆盖问题	UnicostSetCovering	包含更复杂的 SDK 使用示例
多层几何最短路问题	MultiLayerGeoShortestPath	规划中
路由与波长分配问题	RoutingAndWavelengthAssignment
二维网格多智能体路径规划问题	MultiAgentPathFinding2d
二维平面上带时间窗的车辆路由问题	VRPTW2d
柔性作业车间调度问题	FlexibleJobshopScheduling
有向无环图任务调度问题	TaskGraphScheduling
二维矩形条带装箱问题	RectangleStripPacking
二维矩形多箱切割问题	RectangleCutting
二维异形多箱装箱问题	IrregularPacking
布尔表达式可满足性问题	Satisfiability

提交要求

将算法源代码打包为单个压缩包提交, 满足以下要求.
- 压缩包大小 5 MB 以内.
- 基于最新版 SDK 开发.
- 各级子目录内所有 *.cpp, *.cc, *.h, *.hpp, *.c 文件自动参与编译 (建议打包问题名称下 Src 目录或直接上传单个 .cpp 文件).
  - 不需要 CMakeLists.txt/makefile/.vcxproj/.sln 等项目配置文件.
  - 仅支持可直接编译所有源码的第三方库 (如 header-only 库), 依赖额外编译选项配置或静态库会导致自动编译失败.
  - 根目录将被设为附加包含目录 (-I 选项), 包含自行编写的头文件时使用从根目录出发的相对路径.
  - 禁止使用文件 I/O, 目录操作, 多进程, 网络通信, 键鼠控制, 系统设置及其他操作系统 API/ABI.
    - 禁止包含 fstream, filesystem, Windows.h 等头文件以及使用其中的函数或定义同名函数.
      - 包含上述头文件的文件亦不允许被包含 (模板文件除外), 例如 SDK 中的 Util.h.
      - 平台不强制禁止使用多线程, 但测试使用了占用所有 CPU 核心的线程池, 一个 solve() 函数内开多个线程只会算得更慢.
- 在指定的入口函数实现算法, 并调用 SDK 模板文件提供的接口进行超时判断和最优解记录等操作.
  - 确保所有代码中仅有唯一的 main() 函数.
  - 在 XxxSolver::solve() 中实现求解算法.
  - 必须使用 restMilliSec() > 0 判断是否超时, 任意个测试用例超时直接提前终止后续算例的测试, 判定为无效提交.
  - 使用传入 XxxSolver::solve() 函数的随机种子 seed 初始化随机数发生器.
  - 使用 XxxTester::reportNewOptima() 函数向判题程序报告找到的最优解.
- 一般规范性要求.
  - 可重入 (可在同一线程内反复调用而不会出现数据初始化错误或内存泄漏).
  - 可并发 (可在同一进程内的多个线程同时运行多个算法求解实例而互不干扰, 满足此要求一般不能有全局的非只读变量).
  - 可伸缩 (数据结构可以根据算例规模动态申请内存, 而非根据预先指定的编译期常量进行内存分配).
  - 高兼容 (禁止定义与 C++ 标准库或常见系统 API 同名的函数/类型/变量/常量).
  - 跨平台 (仅依赖 C++ 标准中的特性).

评分规则

设算例集为 $I$ . 某解题者某次提交了算法 A. 算例 $i \in I$ 上所有解题者求得的最优解目标函数值为 $b (i)$ . 算例 $i \in I$ 上算法 A 求得的最优解目标函数值为 $o (i)$ . 若 $b (i)$ 为 0, 则修正目标函数值 $b (i) = b (i) + 1, o (i) = o (i) + 1$ 以避免除零错误. 则算例 $i \in I$ 上算法 A 与所有解题者的最优解目标函数值绝对差距为 $g (i) = ∣ o (i) - b (i) ∣$ , 相对差距为 $r (i) = g (i) / b (i)$ . 另设衰减参数 $t = 1$ , $e$ 为自然对数. 则算法 A 在算例 $i \in I$ 上得分为 $f(i) = 1 - e^{-t \cdot r(i)}$ . 算法 A 在所有算例上的总得分为 $f = \sum_{i \in I} f(i)$ .

排行榜上排序时, 若两个算法总得分持平, 则比较总计算时间, 越短排名越靠前. 若总计算时间差距在 $10 ∣ I ∣$ 秒内, 则提交时间越早排名越靠前.

温馨提示

SDK 使用.
- 本地测试.
  - 在 SDK 根目录/问题名称/Submission/ 目录下创建与编译生成的可执行文件同名目录, SDK 会在该目录内生成 run.log 文件, 记录有每次运行的情况 (同测评系统中 “我的提交” 页面的运行日志).
    - 例: SDK 根目录为 NPBenchmark-SDK/, 问题为 PCenter, 生成的可执行文件为 NPBenchmark-SDK/PCenter/pcp.exe, 则可在 NPBenchmark-SDK/PCenter/Submission/pcp/run.log 找到运行日志.
  - 修改 SDK 根目录/问题名称/Data/0.Baseline.txt 文件可以控制测试哪些算例, 每个算例重复测试多少次, 以及每个算例的求解时间上限.
    - 该文件各列分别表示: 难度等级, 算例名称, 重复测试次数, 进入难度等级要求的与最优持平的最少测试次数, 求解时间上限, 已知最优目标函数值.
    - 删除某行将在批量测试中跳过对应算例.
平台使用.
- 测评系统会进行安全检查, 其中一项检查基于关键字匹配, 而标准库和系统 API 使用了 open 和 remove 等常见词, 易产生误判.
  - 正常情况应避免在用户代码中定义与标准库和系统 API 同名的函数或类型.
学术诚信要求.
- 所有提交的代码均有完整记录, 严禁使用作弊手段刷榜.
  - 禁止查表输出预先算出的最优解或作为初始解.
  - 禁止查表使用预先算出的最优目标函数值.
  - 禁止针对每个/个别测试用例分别使用针对性策略或参数设置.
    - 针对一类测试用例的具备泛化性的特征 (规模大小, 图的稠密度, 图直径等) 采用不同策略不受限制.