中心选址问题是通信与物流等领域中的重要问题, 其背后的单一成本集合覆盖问题更是用途广泛.
中心选址问题和单一成本集合覆盖问题主要研究如何使用有限的资源提供尽可能高质量的服务的问题.
例如, 移动基站, 消防站, 物流仓库, 数据中心等众多设施的选址都可以建模为中心选址问题.
高效的中心选址或单一成本集合覆盖问题的求解算法具有极其重要的理论与应用价值.

中心选址与单一成本集合覆盖算法训练

问题概述

给定一系列节点, 从中选出若干节点作为中心为其他节点提供服务.
若一个节点由某个中心服务, 则认为其间存在一条服务边.
在确保每个节点至少由一个中心服务的前提下, 使最长的服务边最短.

若固定服务半径 (服务边的最大长度), 该问题等价于集合覆盖问题.
即给定一系列元素与若干子集, 请选择给定数量的子集, 使其并集等于所有元素的全集.

参考文献.
- [1] Z. Su, Q. Zhang, Z. Lü, C.-M. Li, W. Lin, and F. Ma, “Weighting-based Variable Neighborhood Search for Optimal Camera Placement,” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 14, pp. 12400–12408, 2021.
- [2] Q. Zhang, Z. Lü, Z. Su, C. Li, Y. Fang, and F. Ma, “Vertex Weighting-Based Tabu Search for p-Center Problem,” in Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, 2020, pp. 1481–1487. doi: 10.24963/ijcai.2020/206.

命令行参数

请大家编写程序时支持两个命令行参数, 依次为运行时间上限 (单位为秒) 和随机种子 (0-65535).
算例文件已重定向至标准输入 stdin/cin, 标准输出 stdout/cout 已重定向至解文件 (如需打印调试信息, 请使用标准错误输出 stderr/cerr).
例如, 在控制台运行以下命令表示调用可执行文件 pcenter.exe 在限时 1000 秒, 随机种子为 12345 的情况下求解路径为 ../data/pmed1.n100p5.txt 的算例, 解文件输出至 sln.pmed1.n100p5.txt:

1	pcenter.exe 1000 123456 <../data/pmed1.n100p5.txt >sln.pmed1.n100p5.txt

运行时间上限.
- 超出运行时间上限后测试程序会强行终止算法, 请确保在此之前已输出解 (最好还能自行正常退出).
随机种子设置.
- 使用 C 语言随机数生成器请用 srand.
- 使用 C++ 随机数生成器 (如 mt19937) 请在构造时传参或调用 seed() 方法设置.

输入的算例文件格式

所有算例均已根据给定覆盖半径转换为判定问题, 处理为一系列固定集合数的单一成本集合覆盖算例, 并附有逐步缩小半径时新增的无法覆盖的节点的信息.
转换后每个节点都可以覆盖若干节点, 同时也对称地被若干节点覆盖, 故转换后的单一成本集合覆盖算例中集合数等于元素数.

所有算例的元素和集合分别从 0 开始连续编号.

第一行给出 2 个由空白字符分隔的整数 N 和 P, 分别表示节点数和中心数 (从集合覆盖的角度来看, N 既是集合数又是元素数, P 为可挑选出的集合数).

接下来每 2 行一组, 连续 N 组给出每个集合的覆盖范围.
每组中第一行为该集合能覆盖的元素数量 C, 第二行为空白字符分隔的 C 个数字, 分别表示该集合能覆盖的元素的编号.

然后给出 2 个由空白字符分隔的整数 U 和 L, 分别表示覆盖半径边长序号的上界和下界 (其中上界即前面给出的判定问题对应的覆盖半径的边长序号, 下界为估计值).

接下来连续 U - L 行给出每缩小一次覆盖半径新增的无法覆盖的元素的信息 (若 U = L = 0, 说明前面给出的判定问题对应的覆盖半径已经为最优半径, 缩小半径后已不存在可行解).
每行第一个整数 K 表示本次缩小半径将导致 K 个元素不再被某个集合覆盖, 随后连续 K 个由空白字符分隔的整数 S 表示集合 S 将新增一个无法覆盖的元素 (同一个集合可能重复出现多次).
注意, 在前面给出的判定问题数据中, 每个集合可覆盖的元素已按从近到远的顺序排序, 即每次只用将集合 S 可覆盖元素列表末尾的一个元素删除即可.

例如, 以下算例文件表示集合和元素的数量均为 4, 要求挑选出 2 个集合覆盖所有元素; 其中,
集合 0 可以覆盖 2 个元素, 分别为元素 0 和 3;
集合 1 可以覆盖 2 个元素, 分别为元素 1 和 2;
集合 2 可以覆盖 3 个元素, 分别为元素 1, 2 和 3;
集合 3 可以覆盖 2 个元素, 分别为元素 0 和 2;
覆盖半径边长序号的上界为 5 下界为 3; 其中,
半径缩小为第 4 短的边时, 集合 2 无法再覆盖最远的元素 3, 集合 3 无法再覆盖最远的元素 2;
半径缩小为第 3 短的边时, 集合 1 无法再覆盖最远的元素 2, 集合 2 无法再覆盖最远的元素 2:

输出的解文件格式

输出 P 个用空白字符 (建议使用换行符) 分隔的整数, 分别表示挑选出的 P 个中心 (集合).

例如, 以下解文件表示选择节点 0 和 2 作为中心 (集合):

1
2

0
2

提交要求

发送至邮箱 szx@duhe.tech.
邮件标题格式为 “Challenge2020PCP-姓名-学校-专业“.
邮件附件为单个压缩包 (文件大小 2M 以内), 文件名为 “姓名-学校-专业“, 其内包含下列文件.
- 必要算法的可执行文件 (Windows 平台).
  - 建议基于官方 SDK 开发 (https://gitee.com/suzhouxing/npbenchmark/tree/main/SDK.PCP).
  - 用 g++ 的同学编译时请静态链接, 即添加 -static-libgcc -static-libstdc++ 编译选项.
- 必要算法源码.
  - 可重入 (可在同一线程内反复调用而不会出现数据初始化错误或内存泄漏).
  - 可并发 (可在同一进程内的多个线程同时运行多个算法求解实例而互不干扰, 满足此要求一般不能有全局的非只读变量).
  - 可伸缩 (数据结构可以根据算例规模动态申请内存, 而非根据预先指定的编译期常量进行内存分配).
- 可选算法在各算例上的运行情况概要, 至少包括以下几项信息 (仅在无法成功调用算法输出可通过检查程序的解时作为参考).
  - 算例名.
  - 服务半径.
  - 计算耗时.
- 可选算法在各算例上求得的完全覆盖的解文件 (仅在无法成功调用算法输出可通过检查程序的解时作为参考).
其他所有问题通用的要求见 SmartLab Challenge - ReadMe.

例如:

苏宙行-华科-计科.zip
|   pcenter.exe
|   results.csv
|
+---src
|       main.cpp
|       algorithm.cpp
|       algorithm.h
|
+---results
        pmed1.n100p5.txt
        pmed2.n100p10.txt
        ...

算例清单

下载地址: https://gitee.com/suzhouxing/npbenchmark.data/tree/data/PCP/Instance

算例规模从小到大依次为 (求解难度不一定随规模增加, 但除 pcb3038* 以外的算例应该都很容易求解):

pmed01.n100p005
pmed02.n100p010
pmed03.n100p010
pmed04.n100p020
pmed05.n100p033
pmed06.n200p005
pmed07.n200p010
pmed08.n200p020
pmed09.n200p040
pmed10.n200p067
pmed11.n300p005
pmed12.n300p010
pmed13.n300p030
pmed14.n300p060
pmed15.n300p100
pmed16.n400p005
pmed17.n400p010
pmed18.n400p040
pmed19.n400p080
pmed20.n400p133
pmed21.n500p005
pmed22.n500p010
pmed23.n500p050
pmed24.n500p100
pmed25.n500p167
pmed26.n600p005
pmed27.n600p010
pmed28.n600p060
pmed29.n600p120
pmed30.n600p200
pmed31.n700p005
pmed32.n700p010
pmed33.n700p070
pmed34.n700p140
pmed35.n800p005
pmed36.n800p010
pmed37.n800p080
pmed38.n900p005
pmed39.n900p010
pmed40.n900p090
u1060p010
u1060p020
u1060p030
u1060p040
u1060p050
u1060p060
u1060p070
u1060p080
u1060p090
u1060p100
u1060p110
u1060p120
u1060p130
u1060p140
u1060p150
rl1323p010
rl1323p020
rl1323p030
rl1323p040
rl1323p050
rl1323p060
rl1323p070
rl1323p080
rl1323p090
rl1323p100
u1817p010
u1817p020
u1817p030
u1817p040
u1817p050
u1817p060
u1817p070
u1817p080
u1817p090
u1817p100
u1817p110
u1817p120
u1817p130
u1817p140
u1817p150
pcb3038p010r729
pcb3038p020r494
pcb3038p030r394
pcb3038p040r337
pcb3038p050r299
pcb3038p100r207
pcb3038p150r165
pcb3038p200r141
pcb3038p250r123
pcb3038p300r116
pcb3038p350r105
pcb3038p400r97
pcb3038p450r89
pcb3038p500r85

SmartLab Challenge 2020 - p-Center and Unicost Set Covering