# 基准数据与报告

## 数据政策（重要）

**本仓库不再分发第三方测试数据集。** 只提供下载脚本、清单与报告；数据落在 `bench/data/`，该目录已被
`.gitignore` 忽略。

| 数据集 | 来源 | 获取方式 |
| --- | --- | --- |
| MIPLIB 2017 | <https://miplib.zib.de> | `bench/fetch-instances.ps1` 下载 `.mps.gz` 并就地 gzip 解压为纯 MPS |

### 为什么不用 Netlib LP 测试集

netlib 的 `lp/data/` **不是纯 MPS**：文件由一行 `NAME`、一行维度头，随后是它自己的压缩记录组成
（netlib 的 emps 容器）。在实现该容器的解压器之前，这些文件无法直接读取，因此解析报告改用
MIPLIB 2017 —— 它提供同样性质的工业实例，但以纯 MPS（gzip 压缩）发布。

如果将来要接入 Netlib，正确做法是先实现/移植 emps 解压，而不是把压缩数据喂给 MPS 读取器。

## 脚本

| 脚本 | 作用 |
| --- | --- |
| `fetch-instances.ps1` | 下载实例到 `bench/data/instances/`，生成 `manifest.txt`（相对路径，可移植） |
| `report-parse.ps1` | 通过 `moon run cmd/parse -- --manifest ...` 解析全部实例，生成 `parse-report.md` |
| `report-solve.ps1` | 加 `--solve --relax --max-rows N` 求解，生成 `solve-report.md` |
| `report-mip.ps1` | 加 `--mip --max-nodes N` 做分支定界，生成 `mip-report.md`（可换 `-Manifest` / `-Output` / `-CutRounds`：小规模满预算那一份就是这么生成的） |
| `check-relaxation-bounds.ps1` | 把求解报告里的目标值与 MIPLIB 官方最优值表对拍 |
| `check-mip-objectives.ps1` | 把分支定界报告里每个 `optimal` 与官方最优值**取等**对拍，并断言 `verified == nodes` |
| `report.ps1` | 生成 **`report.md`**：四份报告的索引（每份的范围、关键数字、生成时的提交）+ **一键复现命令** + "这份报告描述的代码是否仍是仓库里那份"（按报告自己记的提交与它依赖的源路径做差分判定） |

```powershell
powershell -NoProfile -ExecutionPolicy Bypass -File bench/fetch-instances.ps1
powershell -NoProfile -ExecutionPolicy Bypass -File bench/report-parse.ps1
powershell -NoProfile -ExecutionPolicy Bypass -File bench/report-solve.ps1 -Relax -MaxRows 1000 -MaxIterations 20000 -Presolve
powershell -NoProfile -ExecutionPolicy Bypass -File bench/check-relaxation-bounds.ps1
powershell -NoProfile -ExecutionPolicy Bypass -File bench/report-mip.ps1 -MaxRows 300 -MaxNodes 300 -MaxIterations 5000
powershell -NoProfile -ExecutionPolicy Bypass -File bench/check-mip-objectives.ps1
# 小规模实例的满预算口径（完成标准"M5 ①：小规模实例求到公开已知最优值"的证据）
powershell -NoProfile -ExecutionPolicy Bypass -File bench/report-mip.ps1 -Manifest bench/data/instances/small.txt -MaxRows 300 -MaxNodes 30000 -MaxIterations 20000 -Output bench/mip-report-small.md
powershell -NoProfile -ExecutionPolicy Bypass -File bench/check-mip-objectives.ps1 -Report bench/mip-report-small.md
```

**`check-mip-objectives.ps1` 按表头列名读报告，不按列位置。** 它此前是按位置取 "nodes / verified" 的：
报告插入 `cuts` 列之后，它把 `verified` 读成 `nodes`、把 `cuts` 读成 `verified`，对一个 33/33 全部过校验的
最优运行报 `UNVERIFIED` 并非零退出 —— 读数的人坏了，而报告里的数字一个都没变。加列就要重新走一遍这条命令。

**`mip-report.md` 是这条命令生成的**：`noswot` 的三个被拒证书在 M5 第三轮全部定论为内核缺陷
（对偶解在病态基上丢精度、方向求解没有自检、非负性自检的尺度与校验器不一致，见 `docs/history.md`），
32 个实例不再有被拒证书。报告是证据，脚本仍然按纪律拒绝写报告 —— 只要内核退出码非零、条目数不符、
出现被拒证书、或解没通过独立复核，就不写。

`report-solve.ps1` 用 **native release** 目标运行内核：同一实例在默认 wasm 目标上要慢约 6 倍
（实测 `mod010`：wasm 119.6s / native debug 203.6s / native release 18.8s），
报告里的每个结果与耗时都来自 native release。

`report-solve.ps1` 在两种情况下**拒绝写报告**并以非零码退出：内核退出码非零
（崩溃或某个文件解析失败），或解析到的实例数与清单条数不一致。一次 native 崩溃曾被写成
"22/33 实例成功"的报告，而报告是仓库里唯一的实测证据，不能把一次没跑完的运行写成一次跑完的运行。

## 行数上限有两个，别混淆

| 上限 | 位置 | 含义 |
| --- | --- | --- |
| `--max-rows N` | `cmd/parse` | **模型约束数**，超过即报 `solve=skipped`，不进入内核 |
| `--max-iterations N` | `cmd/parse` | 迭代上限，让大实例可以被采样而不是被等待（默认沿用内核自身的 20000） |
| `max_kernel_rows` | `SimplexOptions`（默认 200000） | **内核行数**，超过即返回 `SimplexStatus::TooLarge` |
| `max_factor_entries` | `SimplexOptions`（默认 2×10⁷） | 因子分解的**填充量预算**，超过即分解失败 |

内核行数曾经 = 模型约束数 + **每个有限上界一行**，那套口径下 `fast0507` 是 507 条约束、
63009 个 0/1 变量、内核 **63516 行**。**现在有限上界是界而不是行**（有界变量枢轴，见
`simplex/`），同一实例的内核规模是 **489 行**；唯一还会放大行数的是"下界无界的自由变量 +
有限上界"（两个列之差没有单列界，只能留成显式行）。

**内核行数值得盯，而且不只是内存问题**：实测枢轴数随内核行数走、与列数几乎无关
（小规模覆盖型 LP 探针：20 / 40 / 120 / 240 行 → 57 / 137 / 632 / 2220 枢轴；
20 行时 100 列与 900 列分别是 57 与 35）。所以去掉 `fast0507` 的 63001 行上界行之后，
每次枢轴从约 **47.5 ms 降到约 2.4 ms**（实测 150000 次枢轴 400 秒），**Phase I 首次跑完**
（此前 20000 次上限下 Phase I 还停在人工和约 180）。

**内核规模的历史与每次取舍的理由记在 [`../docs/history.md`](../docs/history.md)**：内核最初求 `m×m` 稠密基逆
（63516 行 ≈ 30.8 GB，native 会在分配时以访问冲突退出），后来改成稀疏 LU 分解（内存 `O(nnz + fill)`），
再后来有限上界不再占行。现在两条边界是 `max_kernel_rows`（在分配之前拒绝）与 `max_factor_entries`
（填充量预算，超预算让分解失败而不是无上限分配）。实测：`30n20b8`（presolve 后 11591 行）16 秒求到最优，
`fast0507`（内核 489 行）能跑完 Phase I。

它现在的边界是 **Phase II 的定价**：Dantzig 按检验数选列，那是改进的**速率**而不是改进本身，
覆盖最多未覆盖行的列速率最大、却常被第一行接近紧的约束卡住（实测：Dantzig 选中的列
`r = −121.1`、步长 `0.00632`、增益 `0.76`，而 24 列抽样里就有 `r = −6`、步长 `1.0`、增益 `6.0`）。
改成按**实测增益** `|r| · step` 选列（`gain_candidates`，每迭代只测一个有界候选集）之后，
同一枢轴预算下的内核目标值：20000 次枢轴 165.115 → **156.778**，45000 次 → **133.032**
（Dantzig 要 250000 次枢轴才到 160.353）；代价是每次枢轴约 2.4 → 14 ms。

**非 `optimal` 的运行不打印目标。** 目标列只在真正解出时才有数字，其余状态印 `-`：
一次失败运行返回的目标是 0，而带 presolve 时 `ReducedModel::objective(0.0)` 会把它翻成
**化简自身的目标常数**，看上去像一个结果。`fast0507` 就因此被记成"Phase I 停滞在 13"
（那 13 是化简固定 8 个变量贡献的目标常数，与迭代次数无关）——先用 `--max-iterations 1`
再摘掉 `--presolve` 就能看到同一运行分别印 `obj=13` 与 `obj=0`。Phase I 的真实进度现在印在
迭代上限消息里（实测人工和），不再需要从别处推断。

四个脚本只用 ASCII 字符：Windows PowerShell 5.1 读取**没有 BOM** 的 UTF-8 脚本时会按 ANSI 解码，
非 ASCII 字符会变成乱码。新增脚本请遵守这一约定。

## 报告

- **`report.md`：全部报告的入口（先读这一份）。** 它由 `bench/report.ps1` 生成，内容是三件事：
  ① 四份报告各覆盖什么、关键数字是多少、**生成时的提交**；② 按顺序的**一键复现命令**；
  ③ 每份报告**是否仍被当前代码支持**——脚本读取报告自己记下的提交，把该报告依赖的源路径在
  "那个提交..HEAD"之间做差分，有改动就标 **STALE** 并列出改动文件。
  这条判据故意偏保守：**改了注释也算改**（注释不可能动数字），因为方向要偏安全——只在"可能不再描述当前代码"
  时标出来，绝不在"可能仍然有效"时放行；被标出来的报告只有两种结局：重跑它的命令，或者**测出它要打印的数字没变**
  并把那次测量写在某处。
  脚本在三种情况下**拒绝写**（都用非零码退出且不落盘）：列出的报告文件缺失、某份报告的提交或某个汇总数字
  读不出来（索引宁可不出也不能印一个猜的数）、git 无法回答陈旧性。已验证：缺报告 `exit 2`、无 git 历史 `exit 4`。
- `parse-report.md`：解析报告。含工具链版本与产生它的提交哈希，因此每个数字都可追溯到具体代码；
  记录每个实例的规模、整数列数与校验结论，失败的实例逐条给出原因与位置。
- `mip-report.md`：分支定界报告（行数上限 300、节点预算 300）。清单里 32 个实例，逐实例给状态、
  目标值、仍在开的界、`nodes` / `verified` / `cuts` 与点复核结论；脚本在退出码非零、条目数不符、
  出现被拒证书或点没通过复核时**拒绝写报告**。
- `mip-report-small.md`：**小规模实例的满预算口径**（清单 `bench/data/instances/small.txt`、行数上限 300、
  节点预算 **30000**、迭代上限 20000、开根割）。它是完成标准"M5 ①：小规模实例求到公开已知最优值"的证据：
  **10 个实例里 5 个证到公开已知最优值**（`22433` 33 节点 / `khb05250` 107 / `p0201` 609 /
  `flugpl` 13806 / **`blend2` 24934**），`check-mip-objectives.ps1 -Report bench/mip-report-small.md`
  对 5 项**取等**通过。**节点预算 30000 是实测定的**：清单里最深的证明（`blend2`）落在 25 230 个松弛上，
  30000 是最小的整千覆盖值；早先 20000 的口径下同一实例报 `node-limit`（两场实验，旧数字留在 `docs/history.md`）。
  清单文件本身也是证据：它把每个实例**实测的每节点成本**与排除理由写在里面（`rout` 391 ms/节点、
  `misc07` 1000 节点超过 8 分钟 → 满预算的臂跑不起）。
  `blend2` 曾因一条证书拒签被记为 BLOCKED（M5 第十二~十四轮），内核补上**对偶侧自检**后已回到清单；
  它跑空的路上还有过**一格**写不出证书的松弛，第四十三轮给恢复梯子加了第三次走法（同一个模型、Dantzig 定价）
  之后它报 `optimal`（见 `docs/history.md`）。
  `verify` 列因此有两种可能小于 `nodes` 的原因：松弛撞上迭代上限，或该松弛的最优基**写不出**满足
  符号约定的证书（内核把它报成 `NumericalFailure`，搜索按"无结论"计）—— 两种都是"预算没做完的活"，
  而不是"被校验器拒绝的主张"。
- `solve-report.md`：求解报告。记录模式（是否 LP 松弛）、行数上限、**枢轴上限**、工具链版本与提交哈希，
  逐实例给出状态、目标值与枢轴迭代数；非最优结果逐条如实列出，包含内核自检测得的残差与负值。
  **枢轴上限是基准口径的一部分**（报告头部写明，且 `pivots` 列等于上限的实例就是在那里停下的）：
  上限不同的两份报告是两场实验，不能互相比较—— 这条以前只靠人记，现在写在报告里。
  当前这份由 `-Relax -MaxRows 1000 -MaxIterations 20000 -Presolve` 生成（**上限现在是实测定的**：
  它与同一份清单里 MIP 报告给每个松弛的上限一致；早先那个 1200 的口径下同一清单只有 18 个最优、
  3 个到上限 —— 两场实验的数字都留在 `docs/history.md` 里）：
  **32 个实例全覆盖、20 最优、11 因行数上限跳过、`refused` 归零、1 到上限（`fast0507`）**，
  21 个实例经过化简、20 个重建解全部通过三项检查、0 次需要 Bland 恢复；总枢轴 12 336、
  最大已解模型 664 行。两个从"上限挡住的"变成"解完的"实例是 `danoint`（1907 枢轴、
  `62.637280418466226`）与 `mod010`（3455 枢轴）：它们在 1200 上限下一直报 `iteration-limit`。
  `fast0507`（内核 489 行）需要的不止 20 000 枢轴，仍停在上限上——它那一行报的是内核自己测得的进度
  （Phase I 人工和 / Phase II 内核目标值），不是答案。
  **`refused` 归零与两个实例从"上限挡住"变成"解完"是稀疏 LU 与增益定价的直接结果**：`30n20b8`
  （presolve 后 11591 行）16 秒求到最优并进入对拍表；`bienst1` / `bienst2` 需要约 2130 次枢轴，
  在 1200 上限下一直报 `iteration-limit`，改按实测增益选列后各 582 次枢轴解完。
  报告里每行还带 `presolve`（化简前后规模与各项计数）与 `check`（还原解在原模型上的
  最大行/界违反，以及用原模型目标向量重算出的目标值）两列 —— 化简是实验的一部分，
  它的记账必须自己站得住。
  化简对两个大实例的效果正好说明它能做什么、不能做什么：`30n20b8` 被化简掉 **7282 个变量**
  （18380→11098，内核行 18956→11591，降 39%），稀疏 LU 之后这 11591 行 16 秒就解到最优；
  `fast0507` 是集覆盖问题，几乎没有可约的上界行（63009→63001 个变量），化解它需要的不是化简，
  而是把上界当界用（内核行 63490 → 489，已落地）与按实测增益定价（也已在默认里），
  剩下的仍是 Phase II 的枢轴数，见 `docs/roadmap.md`。

## 交叉校验（外部权威，独立于本实现）

`check-relaxation-bounds.ps1` 把求解报告里的目标值与 **MIPLIB 2017 官方最优值表**
（`miplib2017-v26.solu`）对拍。松弛问题的目标值不可能超过原问题最优值，所以每个求到最优的实例
都给出一个可判定不等式；一旦松弛值超过官方最优值，就说明内核错了。

下表是较早口径（1200 枢轴上限、16 个实例）下的一次快照，方向性结论不变。**当前口径的完整对拍就是这条
命令的输出**（`checked 20, violations 0, not in the table 0`，口径见 `solve-report.md` 头部）：

| 实例 | 松弛目标值 | 官方最优值 | 结论 |
| --- | ---: | ---: | --- |
| flugpl | 1 167 185.7256 | 1 201 500 | 松弛 ≤ 最优 |
| blend2 | 6.9157 | 7.598985 | 松弛 ≤ 最优 |
| dcmulti | 183 975.5397 | 188 182 | 松弛 ≤ 最优 |
| fiber | 156 082.5176 | 405 935.18 | 松弛 ≤ 最优 |
| gt2 | 13 460.2331 | 21 166 | 松弛 ≤ 最优 |
| khb05250 | 95 919 464.0001 | 106 940 226 | 松弛 ≤ 最优 |
| markshare1 | 0 | 0.999999999999 | 松弛 ≤ 最优 |
| markshare2 | 0 | 1 | 松弛 ≤ 最优 |
| misc07 | 1 415 | 2 810 | 松弛 ≤ 最优 |
| noswot | −43.000000000044 | −41.00000885 | 松弛 ≤ 最优 |
| p0201 | 6 875.0000006 | 7 615 | 松弛 ≤ 最优 |
| pk1 | 1.37e−12 | 11 | 松弛 ≤ 最优 |
| rout | 981.8643 | 1 077.56 | 松弛 ≤ 最优 |
| 22433 | 21 240.5262 | 21 477 | 松弛 ≤ 最优 |
| **30n20b8** | **1.5664** | **302** | 松弛 ≤ 最优（稀疏 LU 后才进入可解范围） |
| 50v-10 | 2 879.0657 | 3 311.1799841 | 松弛 ≤ 最优 |

这不是正确性证明，但能廉价地排掉一整类错误，而且结论是记录下来的，不是假定的——表里每一行都由
`check-relaxation-bounds.ps1` 从报告文件直接生成并与官方最优值表对拍。`noswot` 一行
也说明了为什么这类对拍值得做：它的松弛值 `-43.000000000044` 比 MIP 最优值 `-41.00000885` 更小
才是正确的方向。`30n20b8` 一行则是稀疏 LU 的成果：它在稠密基逆时代需要约 1 GB 基逆而被拒绝，
现在 16 秒解出、目标值 1.5664 ≤ 302 方向正确。

## 报告原则

1. 只报告**实测**结果，不写没有测量支撑的推测；
2. 失败要显式：超时、迭代上限、数值失败、超出能力边界分别统计，不合并成“其他”；
3. 每次报告携带运行环境（`moon version --all`）与提交哈希，保证可复现；
4. 数据不入库，脚本入库，报告入库。