# 技术路线图

本文件写里程碑、每个里程碑的**完成标准**、以及下一步的方向。里程碑只有在完成标准全部满足之后才算
结束，未达成时不允许把相应能力写进对外承诺。逐轮的实测过程与已否决的方案在 [`history.md`](history.md)。

## 里程碑总览

| 里程碑 | 主题 | 状态 |
| --- | --- | --- |
| M1 | 基础层与模型层：`core`、`model`、`oracle`、公开入口、CLI 与示例 | 已完成 |
| M2 | 标准模型输入：MPS（free / fixed）与 LP 格式读写 | 已完成 |
| M3 | 稀疏求解内核：修正单纯形 + 对偶单纯形 + presolve / postsolve | 完成标准已满足 |
| M4 | 证书与独立校验器：最优性、Farkas、无界射线 | 已完成 |
| M5 | 整数规划：分支定界 + 割平面 | 完成标准①②③全部满足 |
| M6 | 基准对拍、CLI、文档与发布 | 已完成（已发布 `0.1.0` / `0.1.1` / `0.1.2` / `0.2.0` / `0.3.0`） |

## M1 · 基础层与模型层

**交付物**：`core`（容差比较、Neumaier 补偿求和、CSC 稀疏矩阵）、`model`（变量、表达式、约束、目标、
校验）、`oracle`（稠密两阶段单纯形参考实现）、公开入口 `solve` / `solve_with` 与结果类型、
`cmd/main` 与两个可运行示例。

**完成标准（已满足）**：`moon check --deny-warn` 与 `moon test --deny-warn` 全绿；`moon fmt` / `moon info`
之后 `git diff --exit-code` 为空；native / wasm-gc / js 三个目标测试全绿；能力边界如实标注，越界调用
返回 `NotSolved` 加原因。

## M2 · 标准模型输入

**交付物**：`format` —— MPS（free / fixed）读取器与写出器、LP 格式读写、解析错误定位到行列号与具体
token；`cmd/parse` 巡检 CLI 与 `bench/` 的下载 / 报告脚本，让 `format` 能直接吃真实实例。

**完成标准（已满足）**：

- 读→写→读幂等：写出的文本再次写出逐字节相同；
- 真实实例解析：MIPLIB 2017 清单 32 个实例全部成功，见 [`../bench/parse-report.md`](../bench/parse-report.md)；
- 畸形输入只报错、不 panic，且错误信息带位置：`ParseIssue` 带行号、列号与 token，9 个畸形用例逐条断言
  位置与原因。

**被真实数据纠正过的两点**：额外的 `N` 行是 MPS 的 free row，系数应忽略而不是报错；真实文件里的
`1.5D+02` 指数写法、粘连表达式、`free` / `infinity` 写法都要显式支持。

## M3 · 稀疏求解内核

**交付物**：`simplex`（稀疏 CSC + 稀疏 LU 基分解 + 乘积形式基更新、有界变量枢轴、增益定价、
Harris 比值检验与 Bland 兜底、对偶单纯形热启动、证书生产端自检）、`presolve`（归约与还原）。

**完成标准（已满足）**：

- 与 `oracle` 参照实现在随机 LP 上差分一致；
- presolve / postsolve 在 150 个随机模型上与未化简路径一致，且还原解在**原模型**上复核通过；
- 基准报告可由脚本复现，见 [`../bench/solve-report.md`](../bench/solve-report.md)（32 个实例中 27 个求到
  最优、4 个超行数上限跳过、1 个到 20000 枢轴上限）。被行数上限挡住的四个实例都在更高的上限下实测过，
  没有一个达到最优，失败方式各不相同（Phase I 成本 / 数值失败 / 枢轴成本，逐条见
  [`../bench/README.md`](../bench/README.md#报告)）；唯一撞上枢轴上限的 `fast0507` 也在 60 000 / 150 000
  枢轴下量过（139.78 / 133.18，1 587 s，仍未收敛且增益在衰减）⇒ 两个字面上限都不是"调大就能换覆盖面"的旋钮。

**增强项（已落地）**：DeVex 定价（`Pricing::Devex`，另见 [`algorithms.md`](algorithms.md#2-修正单纯形内核)）、
对偶固定（线性 presolve）、系数强化（整数路径的根松弛）。**未做**：精确 steepest-edge、行与列的支配检测。

## M4 · 证书与独立校验器

**交付物**：`verify` —— 独立于求解路径的最优性校验（原始可行性、对偶可行性、互补松弛、对偶间隙）、
Farkas 不可行射线、无界射线 + 可行起点、割的再推导、证书 JSON 序列化、CLI `verify` 子命令。

**完成标准（已满足）**：

- 故意注入的错解必须被拒，包括数值上"看起来对"的错解：覆盖"可行但非最优"、"偏离可行域一点点"、
  "看起来像但与点不配套的对偶"、目标值声称错、形状不对、符号错误的 Farkas 射线、零射线，
  以及对真实求解结果篡改后的三项；另有一条故意做错的求解器给出的答案必须被 `mip` 停下；
- 校验器不复用求解器的内部中间量：`verify/moon.pkg` 只 import `core`、`model` 与 `moonbitlang/core/string`，
  整包不含任何 `@simplex` 引用；
- 三类结论的证书都能被独立实现复核：200 个随机模型的语料上三种主张都出现且全部通过；真实实例上
  `flugpl` / `blend2` / `noswot` / `30n20b8` 的 `--verify` 全部 accepted（对偶间隙 ~1e-13）。

**限度**：Farkas 射线的构造仍是"Phase I 的最优对偶解"，不是显式导出的构造（生产端已按校验器的方式
自检三条测量）；无界射线只自检了"点可行"。

## M5 · 整数规划

**交付物**：`mip` —— best-bound 分支定界（节点 = 父节点 + 一条收紧的界，沿链重建，子节点热启动）、
根节点割（混合整数舍入，带推导证明）、原始启发式（取整读出整点、取整修复、可行性泵、下潜）、
cutoff 传播、预算合同。

**完成标准与实际结果**：

1. **小规模整数实例求到公开已知最优值：满足**。10 个实例 / 30000 节点的报告口径下 **6 个证到公开已知
   最优值**，对拍脚本 [`../bench/check-mip-objectives.ps1`](../bench/check-mip-objectives.ps1) 对 6 项
   **取等**通过；另外 4 个到节点预算（`markshare1` / `markshare2` / `pk1` 的界贴下界、`noswot`）。
   见 [`../bench/mip-report-small.md`](../bench/mip-report-small.md)。
2. **上限下给出过程状态：满足**，并由测试固定。节点预算到顶报 `NodeLimit`，同时给出当前整数点与仍在开
   的界；`markshare1` 在 20000 节点下给 61 / 下界 0，`pk1` 在 2000 节点下给不出整数点 / 下界 0.602，
   两者都没有被写成最优。
3. **每次 LP 重解都过 `verify`：满足**。报告的 `verified` 列是这件事的计数，另有"故意做错的节点求解器
   必须被拒"的测试；`verified < nodes` 的差额是"到达不了结论的松弛"，按开着的活计。

**覆盖面（宽口径）**：32 个实例 / 600 节点的报告口径下 5 个证到最优、10 个到节点预算、17 个超行数上限
跳过，见 [`../bench/mip-report.md`](../bench/mip-report.md)。节点预算 600 是**实测定的**：最浅的那个证明
（`p0201`）落在 577 个松弛上，600 是最小的整百覆盖值（300 节点口径下它报 `node-limit`，同一份清单因此只有
3 个证到最优）。**树顶的分支从"看小数部分"改成"看实测"**（`strong_branching_depth = 2`、
`strong_branching_candidates = 4`，见 [`algorithms.md`](algorithms.md#6-分支定界)）：`gt2` 因此从 `node-limit`
变成 **331 个松弛证到最优**，`p0201` 555 → 577、`khb05250` 107 → 113、`22433` 33 → 39、`mod010` 31 → 21
（都仍证到最优），代价是 `flugpl` 的界 −0.1%、`misc07` 的界 −0.4%。未证的实例里有 4 个
（`markshare1` / `markshare2` / `noswot` / `pk1`）**把预算翻倍也没有把界抬动**（`markshare1` 与
`markshare2` 的界逐位都是 0、`noswot` 动到 `-43.00000000005462`）。**树顶分支有没有信号也量完了**
（影子探针覆盖树顶两层的全部分数候选：四实例合计 228 个候选、456 个子节点）：**零个可分辨** ——
每个候选的两侧都把父界原样还回来（`markshare1`/`markshare2` 的子节点界精确为 0；例外只有 `pk1` 两个
单侧分离但另一侧仍在父界、`noswot` 两个不可行侧，都进不了"较差一侧"那把尺），与 `gt2`（十个候选里
一个抬穿最优）恰成对照 ⇒ **分支实测化对这四个实例关闭**。缺口分解（公开最优）：`markshare1` /
`markshare2` 离最优只差 1 而当前解 99 / 122（邻域启发落地后 80 / 103），**缺口 ~99% 在整数解一侧**；`noswot` 两侧各 ~2；`pk1`
界侧 6.34、解侧 7。**代价也要一起读**：`dcmulti` 的当前解
在 600 节点口径下**变差**（`188706.00000021877` → `236997.10000014864`），因为预算按比例分配的机制（下潜
储备 `max_nodes / 16` 等）让"改预算"等于"换一条轨迹"，两个口径不能逐格对比，只能整列读。

## M6 · 基准、CLI、文档与发布

**交付物**：四份基准报告 + 索引（含报告陈旧性的机械化判定）、CLI 的五个子命令与统一 JSON 输出、
设计 / 算法 / API / 路线图 / 生态调研文档、发布到 mooncakes.io。

**完成标准（已满足）**：

- 报告可由脚本一键复现，且脚本在运行没跑完、条目数不符、出现被拒证书、点没通过复核时**拒绝写报告**；
- 索引（[`../bench/report.md`](../bench/report.md)）对每份报告做陈旧性判决：读报告自己记的提交，
  把该报告依赖的源路径在那个提交与 HEAD 之间差分，有改动标 `STALE` 并列出文件；
- 发布版本通过 `moon check --deny-warn` / `moon test --deny-warn` 与全部目标平台测试；
  发布物自包含（归档解出来后当模块根 `moon check` / `moon test` 通过），且不含第三方数据。

## 下一步

按"难度 × 回报"排列，都属于研究性增量，不是工程欠账：

1. **扩大覆盖面**（回报最大）：宽口径 5/32、小规模 6/10（树顶分支改为实测选点之后）。已知的堵点另外还有
   LP 松弛本身（有实例跑完
   预算后界仍等于根 LP）与证明成本——`fast0507` 的 20 000 枢轴**已拆开**：37%（7 473 枢轴）花在
   Phase I 证明可行性，其余是 Phase II 在退化实例上的慢降（195.3 → 164.25，增益超线性衰减；与
   60 000 / 150 000 枢轴的抬上限实验同一条轨迹）⇒ 压它的两件事都是研究项：Phase I 成本（crash 基 /
   复合目标）与精确 steepest-edge 定价，见第 2 项（测量记录见 [`history.md`](history.md)）。
   **"抬上限"这一类旋钮已全部量完并关闭**：LP 枢轴上限（150 000 枢轴、1 587 s 仍未收敛）、MIP 割轮次
   （第二到第三轮就饱和：`gt2` 20→30 条后不再增长；`flugpl`/`blend2`/`markshare1` 在固定 200 节点下
   `r=2` 与 `r=16` 的界**逐位相同**）、节点预算（`noswot` 60 000 节点界不动），见
   [`../bench/README.md`](../bench/README.md)。**整数行强化已两半俱全**
   （隐含整数界 + 系数抬高，见 [`algorithms.md`](algorithms.md#4-presolve-与-postsolve)）：界那一半在
   报告口径的清单上触发 81 次、落在 4 个实例上（`noswot` 65、`blend2` 9、`p0201` 6、`gt2` 1），
   它对当前解是**两升一降**（`gt2` 首次拿到最优 21166、`p0201` 的 gap 减半、`noswot` 在小规模口径反而
   从 −40 退到 −39），覆盖面没动。**系数那一半这条线已经量完并关闭**：探针给出了它被挡住的分布（镜像
   10 718 个候选、守卫过严 2 490 个、其它项极值无穷 329 个、范围太宽无收益 70 个），而放宽守卫的版本
   虽然真的触发（`blend2` 79 行）却**有实测代价**（`blend2` 丢掉小规模口径的最优证明，覆盖面 5/10 → 4/10），
   已回退；镜像那一半撞的是同一堵墙（必要条件 `rest_max − rest_min < aⱼ`，两边同一个 `Δ`）。⇒ **下一步
   不在归约上，而在"把行换掉"**：更强的割（现实是四条割族都已经量完无净收益）或更紧的建模——其中覆盖型 cover 割是**数学上恒 LP 冗余**、唯一还开着的割族是 flow cover / lifted cover（把整数性搬回一般整数覆盖背包的那一步，公式需要可靠出处，见 [`algorithms.md`](algorithms.md#5-割平面混合整数舍入)）；**gt2 的行结构已取全**（12 条 demand 行 `Σ_t a_{d,t}·x_{d,t} ≥ d_d` + 17 条 avail 行 `Σ_d x_{d,t} ≤ u_t`，变量上界即容量，见 [`history.md`](history.md)）⇒ flow cover 必然是 demand 行 + avail 行的**多行组合**，因为单行 MIR 只能用个体界、用不到 avail 行的求和信息；**层 1（靶子结构）已量完**：系数符号普查显示"容量行全正 × 需求行全正"只有
`gt2`（17/17 与 12/12，已证）与 `misc07`（`L` 6/50 全正、`G` **127/127** 全正）符合，而 `noswot` 的 126 条
`G` 行里 **125 条是混合符号**（`c44 = -21·x14 - 0.25·x57 - 2.0833·x58 - x104 + x119 ≥ -21`，job-shop 的时序
约束，不是需求行）、`blend2` 的 3 条需求行同样全混合 ⇒ 这两个**不是靶子**，它们贴 LP 的界来自时序约束上的
整数性、不是覆盖上的；`misc07` 的耦合比 `gt2` 密集（`c9/c10/c11` 各 63 个变量触达 **126 条需求行**），但它
宽口径是 `node-limit`（开界 **1730.625** 已被根割从 LP 松弛 1415 抬起、当前解 3160、gap 1429），小规模口径
又因每节点 8 ms 被排除（30 000 节点约 4 小时）⇒ **即使做成，收益上限是 `misc07` 一个实例的界，不是覆盖面
的大面积提升**（层 1 的实测与限度见 [`history.md`](history.md)）；如果还要碰
   搜索侧，已量出的靶子有两个：`blend2` 这种"当前解已是公开最优、只差界"的实例单独诊断；以及
   `markshare1` / `markshare2` 的"当前解供应链"—— **已量完并落地**：当前解主体是修复链的产品，
   修复预算 `max_nodes / 50` 以 82% 不可行耗尽；抛光（固定整数重解 LP）零收益（目标由整数赋值经行
   耦合钉死）；邻域校准 `markshare1`：放开 10 个整数的邻域**被证为空**（当前解是 10 整数局部最优，
   73 松弛），放开 20 个**有猎物**（99 → 94，3 970 松弛）。**邻域启发已实现**（`neighbourhood_pass`，
   尾部 `max_nodes / 8`、"远"门、`neighbourhood_passes` 旋钮）：`markshare1` 99 → **80**（小规模）/
   257 → **105**（宽口径）、`markshare2` 122 → **103**，覆盖面与全部证明不动；剩余缺口 ~79 / ~102
   在界一侧（贴 0 不动），原始侧的便宜手段到此用完（记录见 [`history.md`](history.md)）。
   **预算这条轴也量完了**：小规模口径 5 个到预算的实例里，`noswot` 把节点预算从 30 000 翻到 60 000 后
   `bound` 仍是 `−43.00000000005462`（就是它的 LP 松弛值，一动没动）、当前解从 −40 走到
   `−39.000000000007525`、`43989` 个节点仍开着 ⇒ **把预算加一倍不推进界**，覆盖面的瓶颈在松弛本身，不在节点数。
   **剩余无结论松弛也量完了**：布局指纹修复后 `noswot` 还剩 3 个，LU 层"换列修复"实测无效——修复出的基
   条件数爆炸（重算基本值到 `-1e17` 级，健全性门如实拦截，3 → 3），记为该实例在当前数值设施下的限度
   （测量记录见 [`history.md`](history.md)）。
   **分支这一侧的第二档已量完并关闭**：树顶实测选点（`strong_branching_depth = 2`、
   `strong_branching_candidates = 4`）只在"某个方向的子节点把界抬起来"时才赚钱 —— `gt2` 的 `x82`
   下侧把界从 21 099.977 543 310 45 抬到 21 668.24（超过它的当前解 21 166，该侧本该被剪掉），而四个
   未证实例在 root 上一个这样的方向都没有：`noswot` 42/42 个分数整数（最大相对抬升 2.8e-11）、
   `pk1` 19/19（1.6e-14）、`markshare1` 8/8 与 `markshare2` 10/10（**逐位恰为 0**）；depth 1–2 的抽查
   同样平（`pk1` 只有一处移动 0.216，而它的当前解是 18）⇒ 加深度或加候选都没有可赚的钱，**这条线关闭**；
   仪器、全表与阳性对照（`gt2` 那条跳跃被逐位重现）见 [`history.md`](history.md)。
2. **剩下的定价工作 —— 已量完，不是覆盖面的杠杆**：三条规则在同一台机器、同一份清单上量过（清单级总枢轴
   `gain` 12 361 / `devex` 15 045 / `dantzig` 15 779，见 [`algorithms.md`](algorithms.md#2-修正单纯形内核)）；
   退化实例 `fast0507` 单独对比过（20 000 枢轴：`devex` 160.55、`gain` 164.25、`dantzig` 166.21），但
   **整份清单上 `devex` 把 `mod011` 从 optimal 打成 numerical-failure（6 084 枢轴基奇异）⇒ 不换默认**，
   而且 `fast0507` 处在 `iteration-limit`，它在报告里的 `objective` 列恒为 `-`，换规则改不动任何一列。
   精确 steepest-edge 仍未做，它需要每次迭代算 `‖B⁻¹aⱼ‖`，而上面这条对照说明"更精的定价度量"在清单级
   未必是净收益；要利用实例间的差异，得先有一个**运行前可判定**的特征（"退化程度"没有量过）。
3. **内核的系数尺度 —— 已量完，不是覆盖面的杠杆**：四个被行上限挡住的实例里只有 `mod011` 尺度大
   （矩阵系数跨 3.0e+05、目标跨 3.4e+05），其余三个都在 1e+03 以内。把实例先做行/列均衡
   （`x = s·x'`：行除以该行最大系数，列再除以列最大系数，目标值不变）再求解，**没有一个被解出来** ——
   `mod011` 仍在 1e+04 个枢轴处写不出证书（连目标系数一起缩放到系数全为 1 之后也一样）、
   `core2536-691` 与 `2club200v15p5scn` 逐位不变、只有 `dano3_3` 的 Phase I 快约一倍；而对照实例里
   `mod010` 反而慢 25%，所以"按尺度阈值决定要不要缩放"这种规则也拍不下来。⇒ 这条线在**覆盖面**上关闭；
   若以后只为"Phase I 速度"做它，先想清楚与证书的接口（缩放后的乘子必须能映回模型空间，`verify`
   看到的仍必须是原模型的证书）。实测表与命令见 [`../bench/README.md`](../bench/README.md) 的
   「均衡（行 / 列缩放）实测」一节。
4. **更完整的整体 presolve / 归约族 —— 等式 doubleton 已落地，余下已量**：**等式 doubleton 代入已实现**
   （`rows_substituted` 计数、可链式还原、填充预算 10 000）：`mod011` 在 20 000 行上限下从"基奇异数值失败"
   变 **solve=optimal**（10 177 枢轴），受影响已解实例目标逐位一致、枢轴净 −85（唯一上升 `cap6000`
   +1.5%）；报告口径 **27 → 28/32**——行上限的检查已挪到 presolve 之后、口径按定标逻辑升到 2 500，`mod011`
   以归约后 2 402 行进入报告并解到最优（10 177 枢轴）。前提细化量出的另一半：**不等式** doubleton 的大数字
   （`aflow40b` 95%、`qiu` 89%、`dano3_3` 684）是隐含界归约的地盘，不是代入猎物（`dano3_3` 无等式
   猎物，其堵点不在行数）；**重复列是死猎物**（全语料只有 `fiber` 一对）；**列支配已落地**（`presolve::
   remove_dominated_columns` + `MipOptions::column_dominance`，默认开）：`fast0507` 是整数 0-1 集覆盖
   （507 条 `≥` 行、63 009 个 `[0,1]` 整数变量、成本 1 或 2），按完整判据（成本不高于 + 覆盖包含 + 逐行
   系数不小于 + **该列单独就能满足该行**）删掉 **36 670 列（58.2%）**；第四条不是可选项，缺了它实测把
   `markshare1` 判成 `infeasible`、`pk1` 报出 `optimal 726`。它算**能力**增强而不是报告数字：LP 报告跑的是
   松弛（删列会改 LP 最优值）、MIP 报告按 300 行上限把 507 行的它跳过 ⇒ 四份报告的数字不变，收益落在
   使用者手上的集覆盖模型上（列数减半时同一实例的 LP 墙钟 327 s → 263.6 s）。测量与限度见
   [`algorithms.md`](algorithms.md#4-presolve-与-postsolve)。
5. **补齐射线自检**：**无界主张这一半已完成** —— 点的行残差与变量界、射线的四项（行不阻挡该方向、
   变量自己的界不阻挡、不是零向量、目标沿它严格改善）都在发证书前量过，任一不过就报 `NumericalFailure`
   （见 [`algorithms.md`](algorithms.md#7-证书与校验)）。**剩下的是不可行射线的构造 —— 已量过、语料上暂无
   靶子**：它仍是"Phase I 的最优对偶解"而不是显式导出的射线，但小规模清单全量打印"无结论松弛的原因"
   的测量显示 **Farkas 拒签为零**（第 41/42 轮的守卫加冷回退已把真实拒签清干净），构造出更好的射线没有
   可移动的数字（测量记录见 [`history.md`](history.md)）。
6. **导出到公开证书标准（VIPR）**：真正的成本是要一套有理数算术子系统——本项目的证书是浮点加带容差的
   判据，有理化会把证书变成另一份主张，必须重新论证它成立。做法与三个问题的答案见
   [`prior-art.md`](prior-art.md)。
7. **整数无界性的证明 —— 已落地**：松弛无界、且它的点与改善射线（分数时按最小整数倍缩放到整数）在整数
   变量上都是整数时报 `Unbounded`，`MipResult::values` / `ray` 就是证明的两半；其余情形（点本身是分数）仍报
   `UnboundedRelaxation`。还没做的是"找整数可行点"那半边——那才是点分数时的堵点，仍归搜索。

## 明确不做（非目标）

以下内容在可预见的版本内不做，也不写进对外承诺：

- 非线性 / 凸优化（NLP）、半定规划；
- 随机规划与分解算法（Benders、Lagrangian 松弛）；
- 并行 / 多线程求解；
- 网络单纯形专用高速路径；
- MPS 的极小众扩展（完整 `MARKER` / `SOS` 语义）与 CPLEX LP 格式的全部扩展；
- Python / JS 绑定（保持纯 MoonBit、零 FFI）。

## 规模承诺的措辞

不写"目标万级约束 / 变量"这类话。对外只报告**实测**结果：以公开实例清单为参照，列出每个实例的状态、
目标值、枢轴数或节点数，以及没解完的原因。任何"上限"都是结果的一部分，必须与它对应的数字一起给出。