# Changelog

本文件记录每个版本的可见变化。格式参考 [Keep a Changelog](https://keepachangelog.com/)，
版本号遵循 [Semantic Versioning](https://semver.org/)。

开发过程中的逐轮实测记录、量过并否决的方案及其理由，见 [`docs/history.md`](docs/history.md)。

## [Unreleased]

（下一轮开发时在此累积。）

## [0.6.0] — 2026-10-31

自 `0.5.0` 起的变化。`0.5.0` 是一次纯文档发布，这一版是**能力**：整数路径新增一条精确的列支配归约，
公开面因此增长（`MipOptions::column_dominance`、`MipResult::domination`、`presolve::remove_dominated_columns`、
`presolve::DominationStats`）。四份基准报告的数字与 `0.5.0` 逐字相同，原因写在下面对应条目里。

### Added

- **列支配归约（`presolve::remove_dominated_columns`）**：0/1 集覆盖模型里，若存在一条更便宜的列覆盖
  另一条列的每一行、在那些行上的系数不小于它、且**自己就足以满足每一行**，那么后者可以固定为 0。这是
  **等价变换**（最优值不变），不是启发式：任何 `x_B = 1` 的可行点都能改写成 `x_B = 0`、`x_A = 1` 而目标
  不升。它返回删列后的模型、被删列的**原下标**（升序）与 `DominationStats`。
  - `MipOptions::column_dominance`（**默认开**）让 `solve_mip` 在搜索前调用它；`MipOptions::without_column_dominance()`
    关掉。`MipResult::domination` 报告删了多少列、看了多少列（后者为 0 表示模型不在这一类，一眼没看）。
  - 调用方拿到的 `values` 仍是**自己那张模型**的点（长度 = `num_vars()`，被删处为 0），因为 `solve_mip`
    会映回去并用 `max_row_violation` / `max_bound_violation` 在**原模型**上复核；映回去的点若通不过
    复核就报 `Unverified` 而不是当成答案。
  - 实测：两份清单 32 个实例里只有 `fast0507` 属于这一类，它删掉 **36 670/63 009 列（58.2%）**。
    **本版的报告数字不变**——`solve-report` 跑的是 LP 松弛（删列会改 LP 最优值），`mip-report` 的宽口径
    按 300 行上限把 507 行的它记为 skipped，小规模清单里没有它。这条规则的服务对象是使用者手上的集覆盖
    模型：列数减半时同一实例的 LP 墙钟 327 s → 263.6 s（同 20 000 枢轴上限）。

### Changed

- **文档**：[`docs/algorithms.md`](docs/algorithms.md) 的 presolve 一节新增列支配小节（四个条件、为什么
  第四条不能省、两处被它救回来的错误结论、限度），[`docs/api.md`](docs/api.md) 补 `presolve` 与 `mip`
  两个包的契约。

## [0.5.0] — 2026-10-29

**本版没有行为变化**：发布的是文档与三份实测记录。`.mbti` 一行未动，四份基准报告的数字与 `0.4.0` 逐字
相同，升级不会改变任何求解结果。版本号按 `0.x` 的惯例升 minor，但请把它当作一次**文档发布**来读。

### Added

- **README 新增「什么时候它不是合适的选择」一节**：把散在 `docs/` 与
  [`docs/history.md`](docs/history.md) 里的实测边界收在一处——规模（内核行数 200 000 上限、清单里 3 个
  实例抬到 20 000 行仍解不完）、高度退化实例（`fast0507` 20 000 个枢轴未收敛、150 000 个仍不收敛）、
  整数规划的证据边界（宽口径 32 实例证 5 个、小规模 10 个证 6 个）、割平面只有单行混合整数舍入、
  以及明确不做的那几项。写给"正在选求解器的人"，不给乐观估计。

### Changed

- **三条实测线收口，结论都写进了 [`docs/history.md`](docs/history.md)（含口径、表格与限度）**：
  ① 定价规则在 `fast0507` 上 `devex` 优于默认 `gain`（同一 20 000 枢轴 160.55 对 164.25），但整份
  清单上 `devex` 把 `mod011` 打成数值失败（6 084 枢轴后基奇异）⇒ **默认仍是 `gain`**；
  ② `fast0507` 的列支配初判有 **40.7%（下界）** 的列可删，但 LP 报告跑松弛（删列会改 LP 值）、
  MIP 报告按行数上限跳过它 ⇒ 记为能力而非覆盖面的数字；
  ③ flow cover 的靶子经行结构普查（容量行全正 × 需求行全正）收窄到 `misc07` 一个，而它宽口径是
  `node-limit`、小规模口径因每节点 8 ms 被排除 ⇒ **这条族不进入实现**。

## [0.4.0] — 2026-10-25

自 `0.3.0` 起的变化。这一版的主线是**覆盖面与保真各进一大步**：LP 覆盖面 27/32 → 28/32
（`mod011` 从"基奇异数值失败"到入报告最优）、整数侧的当前解质量（邻域启发）、以及一个热启动
装错基布局的真缺陷修复。自 9 月末基线（`0.2.0`，提交 `0632534`）累计：LP 最优 20/32 → 28/32、
MIP 证明 3/32 → 5/32 与 5/10 → 6/10、测试 198 → 224。

### Changed

- **求解报告的行上限挪到 presolve 之后量，口径 2 200 → 2 500，LP 覆盖面 27/32 → 28/32**。行上限回答
  的是"这次运行有没有机会跑完"，那是关于**内核实际拿到的问题**的问题——presolve 开时先归约、对归约
  模型查行数（skip 行报出两个数），presolve 关时行为不变；MIP 路径的检查不动（整数搜索不走线性
  presolve）。前提量过：等式 doubleton 代入把 `mod011` 降到归约后 **2 402 行**（原 4 497）并在 20 000
  枢轴内解到最优；按定标逻辑（覆盖已测最大可解模型的最小整百）口径升到 2 500，`core2536-691` 归约后
  2 505 行恰在线外。`mod011` 在报告里 **solve=optimal**（−62121982.55190222，10 177 枢轴）。

### Added

- **presolve 现在会代入等式 doubleton 行**。`a·x + b·y = r` 说 `y = r/b − (a/b)·x` 处处成立，于是
  `y` 整个离开模型：其余行的 `y` 项拼到 `x` 上（同行已有 `x` 时合并）、目标项变成偏移加 `x` 上的项、
  `y` 的盒子变成 `x` 的区间并与 `x` 的盒子取交、行本身消失；还原沿代入链（可链式）解析。只做等式
  （不等式 doubleton 只钉一侧，隐含界归约已覆盖），带总填充预算 10 000。新计数器
  `PresolveStats::rows_substituted`。**实测**：`mod011` 在抬高的行上限（20 000）下从"基奇异数值
  失败"变成 **solve=optimal**（−62121982.55190222，10 177 枢轴）；报告口径（2 200 行）覆盖面不变
  （`mod011` 的行数在 presolve 之前就被挡住），受影响已解实例目标逐位一致、枢轴净 −85
  （唯一上升 `cap6000` +1.5%）。前提测量（等式 doubleton 集中在 `mod011`、不等式是隐含界地盘）
  与实现细节见 [`docs/history.md`](docs/history.md)。

- **搜索的尾部现在会围绕当前解再解一次邻域子问题**（fix-and-optimize 式启发）。此前每个原始机制给出
  的都是"沿途遇到"的点；这一步把预算的末段（`max_nodes / 8`）花在**围绕**搜索最终落在的那个点上：
  放开前 20 个整数变量、其余固定在当前解的值上，交给一次普通搜索（它逐个过 `verify`，松弛计入
  `nodes` / `verified`，与所有机制同一条纪律）。三道门让它只在该付钱的地方付钱：有当前解、当前解
  离开界"远"（复用下潜启动条件的 1/5 线——要收口的运行分文不付）、整数变量多于放开的个数。
  **实测**：`markshare1` 当前解 99 → **80**（小规模口径）/ 257 → **105**（宽口径），`markshare2`
  122 → **103**；`pk1` 不变（其 20 整数邻域无猎物）、`noswot` 逐字不变（gap 过不了"远"门）。
  覆盖面与全部证明不动（宽 5/32、小 6/10，`p0201` 宽口径仍 577 个松弛证完）。前提的两端都是量出来
  的（10 整数邻域被证为空 / 20 整数邻域含 94），见 [`docs/history.md`](docs/history.md)；新旋钮
  `MipOptions::neighbourhood_passes`（默认 1，0 关闭）。

- **整数无界性现在可以证明**。分支定界在内核报松弛无界时，检查松弛证书里的**点**与**改善射线**是否在每个
  整数变量上都取整数值——两者都整数即 `x⁰ + k·d` 对每个整数 `k ≥ 0` 都保持整数且可行，于是整数模型确实
  无界，报新状态 `MipStatus::Unbounded`，`MipResult::values`（积分点）与新增的 `MipResult::ray`（积分射线）
  就是证明的两半。射线在整数变量上不是整数时先按**最小整数倍**缩放到整数（正倍数仍是回收方向，`(0.5, 1)`
  在倍数 2 下成 `(1, 2)`）——内核选的那个倍数不一定是 1，缩放后的证书同样过 `@verify` 复核。点本身是分数、
  或射线在限定的倍数内缩放不出整数时，仍报 `UnboundedRelaxation`（松弛无界、模型未知）。公开入口
  `SolveStatus::Unbounded` 因此对整数模型可达（之前永远到不了它），而公开 `Solution` 不带这两个数组
  （与线性路径一致：证明在低层结果上）。这是 [`docs/roadmap.md`](docs/roadmap.md) "下一步"第 6 项的收口；
  报告口径下没有实例报无界，所以四份报告的数字不变，变化在能力与公开面上。配套：`examples/unbounded` 是可
  运行的示例，`moon run cmd/main` 的六个演示现在覆盖全部四种公开状态（`Optimal` / `NodeLimit` / `Unbounded` /
  `NotSolved`）——模块注释此前声称含一个 "not solved" 演示、实际没有。

### Changed

- **树顶的分支改成"按实测选"，整数覆盖面 4/32 → 5/32、5/10 → 6/10**。默认规则（选最分数的整数变量）
  在 `gt2` 的根上每次挑中的都是一个**无用分支**：十个最分数变量里九个的两个子节点都把父节点的界原样
  还回来，而 `x82` 的下侧子节点高于模型最优值（21668.24 > 21166），那一侧本该被直接剪掉。现在在树顶
  （`depth < 2`）先量调用方自己的候选的两个子节点（两次松弛），只有当它抬不动界时才把测量扩到另外最多
  4 个候选，按"较差的那一侧更高"取最好的。测量的每次松弛**计入节点预算并逐个过 `verify`**，剩余预算
  不足 8 次或调用方自带节点求解器时不做，从不越过预算。结果：`gt2` 从 `node-limit`（界 21099.98、
  gap 66.02）变成 **331 个松弛证到最优**（小规模口径 432），`p0201` / `khb05250` / `22433` / `mod010`
  仍证到最优（577 / 113 / 39 / 21 个松弛）；两份报告的对拍分别是 `checked 5` / `checked 6`、
  `violations 0`。代价如实记：`flugpl` 的界 −0.1%、`misc07` 的界 −0.4%。门槛是怎么定下来的
  （无门槛那一版换一个实例丢一个实例）见 [`docs/history.md`](docs/history.md) 与
  [`docs/algorithms.md`](docs/algorithms.md) 第 6 节。

- **宽口径整数报告的节点预算 300 → 600，覆盖面 3/32 → 4/32**。预算由实测定：最浅的那个证明（`p0201`）落在
  555 个松弛上，600 是最小的整百覆盖值；它在 300 节点口径下报 `node-limit`，现在报 `optimal`（`obj=7615`，
  与 MIPLIB 公布的最优值逐位相同）。代价是 `dcmulti` 的当前解变差（`188706.00000021877` →
  `236997.10000014864`）——预算按比例分配（下潜储备 `max_nodes / 16` 等）意味着**改预算就是换一条轨迹**，
  两个口径只能整列读、不能逐格对比。旧口径的每个数字逐条留在 [`docs/history.md`](docs/history.md)。

- **求解报告的行上限 1000 → 2200，LP 覆盖面 20/32 → 27/32**。1000 是稠密基逆时代留下的数字，稀疏 LU 落地
  后从没重测过；把 1000~2200 的 7 个实例逐一套上内核，全部在枢轴上限内解完（`qiu` / `blp-ar98` / `dsbmip` /
  `aflow40b` / `bc1` / `mitre` / `cap6000`，1128~2176 行），而 2539 行的 `core2536-691` 把整段枢轴预算花在
  Phase I 上——所以 2200 是"最小整百覆盖已测最大可解模型（2176 行）"的值，不是挪球门：内核本来就能解这些，
  报告只是没量。求解报告总枢轴 12 361 → 25 918、最大已解模型 664 → 2176 行。

### Fixed

- **热启动不再把"另一套列编号"的基当自己的基装进来**。内核的列布局由模型界决定：核行右端 = 模型右端 −
  `Σ aⱼ·lⱼ`（下界平移进右端），分支收紧下界会把它推过零、行整体取反，该行的附加列从一个 slack 变成
  surplus + artificial、其后全部重新编号——两个布局可以行数列数都相同，形状检查放行，而基里的编号已经
  指向别的列。`SimplexBasis` 现在携带布局指纹（`layout`，公共面有意新增的字段），`new_with_basis`
  装载前比对，不符即回退冷启动。**实测**（`noswot`，小规模口径）：一个运行有 155 次这种装坏的基（每一个
  都含同一行的两个单元列、精确奇异），修复后无结论松弛 **10 → 3**、`verified` 29 990 → 29 997；两份
  MIP 报告覆盖面不动（5/32、6/10），LP 报告不受影响（全冷启动）。根因链与四层探针见
  [`docs/history.md`](docs/history.md)，热启动契约的补述见 [`docs/algorithms.md`](docs/algorithms.md) 第 3 节。

- **无界结论现在先量后发**。内核报 `Unbounded` 之前只检查了"跑在上面的那个点是可行的"，而校验器读一份无界
  证书时看四项：行不阻挡该方向、变量自己的界不阻挡、方向不是零向量、目标沿它严格改善。四项一项没量就宣布
  "目标无界"是一个带着自信状态的错误答案，而在分支定界里它走得比它来自的那个节点更远；同一处还漏了
  **点对模型变量自己的界**的检查（变量可以落在每一行之内、落在自己的界之外）。现在四项与点的界都在发证书前
  量过，任一不过就报 `NumericalFailure`（按"没有结论的松弛"计，搜索继续），不再发出注定被拒的证书。
  这是继最优性证书（残差 / 乘子符号 / 对偶间隙）与不可行证书（射线符号 / 盒吸收 / 边际）之后，
  第三类主张补上同一件事。**实测**：清单上的报告数字未变（报告口径下没有实例报无界），
  变化在保真轴上——见 [`docs/algorithms.md`](docs/algorithms.md) 第 7 节与 [`docs/history.md`](docs/history.md)。

## [0.3.0] — 2026-10-16

自 `0.2.0` 起的变化。这一版把三个**能力**补齐并新增了一个入口，其中 `Devex 定价` 是申报书核心功能清单里
列着、而 `0.2.0` 里没有的那一项，`对偶固定` 与 `整数行强化` 同属那份清单的 presolve 一行。

公开面有新增，也有**一处不兼容变更**：`presolve::strengthen_integer_rows` 的返回类型从 `Int`（改动的行数）
变成 `StrengthenStats`（`rows_rewritten` + `bounds_tightened`）——直接丢弃返回值的调用方不受影响，
读那个计数的调用方要改一行。`0.x` 语义下 minor 允许不兼容变更，所以版本号是 `0.3.0` 而不是 `0.2.1`。

### Added

- **`moonopt::relaxation(model)`**：整数模型不会以松弛的形式被回答（那是刻意的），所以"我要的是界，不是最优
  整点"需要一个显式入口。它返回同一个模型去掉整数性——变量与顺序、行、右端项、目标都不动——于是调用方手上
  那个点仍在同一空间里，可以用 `presolve::objective_value` / `max_row_violation` 读回，"当前方案 gap ≤ X%"
  因此是可算的。返回的是普通线性模型，走与其它线性模型完全相同的 `solve`（含化简与独立复核）。
- **`examples/schedule_bound`**：上面这条链路的完整可运行示例——LP 界、已证最优、手上那份方案的 gap，以及
  **界自己离最优有多远**（界线报告不写后者，读者就会把界当成答案）。
- **Devex 定价**（`simplex::Pricing::Devex`，Harris 1973）：按枢轴行给出每个非基列的权重，用
  `检验数²/权重` 排序近似最陡边。权重只影响**走哪条路**，不影响答案；`SimplexOptions::with_pricing`
  选规则，CLI 用 `--pricing dantzig|gain|devex`。表见 `docs/algorithms.md`。
- **对偶固定**（线性 presolve）：目标想走的方向不会让任何一行更难时，把变量钉在那个界上。
  计数见 `PresolveStats::variables_fixed_dual`。
- **系数强化**（`presolve::strengthen_integer_rows`，分支定界的入口调用）：把整数行的系数抬到
  "不丢掉任何一个整数点"的最高值，并应用该行隐含的整数界；线性 presolve 见不到整数模型，所以它跑在
  整数路径上。
- **整数行强化的另一半**：同一份算术现在**也**单独应用整数行隐含的整数界（`aⱼ > 0` 给上界、
  `aⱼ < 0` 给下界），它只需要其它项的**最小**贡献有限，因此比抬高系数那一半宽得多。整数可行集仍然逐点
  不变（两条穷举整数点的测试，含变量界）。返回值从"改了几行"换成 `presolve::StrengthenStats`
  （`rows_rewritten` + `bounds_tightened`），`mip::MipResult::strengthening` 如实转发，`--json` 的
  `strengthened_rows` / `strengthened_bounds` 两个字段就是它：这条归约有没有触发，从此是可测量的，
  而不是从答案里猜的。
- `mip::MipOptions::row_strengthening`（默认开）与 `MipOptions::without_row_strengthening()`：关掉它，
  搜索拿到的就是调用方写的那个模型，而不是它的重写（trace 测试与"量搜索本身"的测量需要这个开关）。

### Changed

- 全库按当前工具链（`moonc v0.10.15+943464bfa`）的写法重排：类型标注 `Int` → `Int32`，默认参数
  `name?` → `name~`，共 37 个文件。这不是行为变化——`moon info` 写出零 `.mbti` diff（公开面未动）、
  `moon test` 203/203 与改动前一致，四份基准报告的每一行计数除头部记录的 `- Toolchain:` 外逐字相同。
  代价是**构建这棵树需要认识 `Int32` 的工具链**：实测 `moonc v0.10.14` 报
  `The type Int32 is undefined`，`v0.10.15` 正常。已发布的 `0.2.0` 仍是旧写法（`v0.10.15` 依旧接受
  `Int` 与 `name?`），所以只有从源码构建本仓库的开发者会碰到这条下限。

### Fixed

- CLI 的文本路径自己拼了一套内核选项，于是 `--pricing`（以及任何只加在共用的选项构造处的选项）在
  `solve` / `verify` / `--reoptimize` 三条文本路径上**静默无效**：同一条命令在 `--json` 下走的是共用
  构造，在文本下走的是另一套。现在三条路径都走同一个 `kernel_options`。

## [0.2.0] — 2026-09-30

自 `0.1.2` 起的变化。公开 API 有新增（`MipOptions::primal_rounding` 字段与
`MipOptions::without_primal_rounding()`），按语义化版本是 minor 版本。

### Added

- 分支定界的原始启发式：从松弛取整读出整数点、取整不可行时把整数固定住重解、可行性泵；三者与下潜
  共用"当前解"这一槽位，只提供当前解、永不主张最优，并计入同一份预算。
- 采样取整：按每个整数自己的小数部分无偏地随机取整，零次求解，在三个确定性方向之外多一条找点的路。
- 下潜的第二个启动理由（当前解离开界很远时也走一次）与下潜储备（跑掉一半预算仍没有整数点的运行，
  额外拿到 `max_nodes / 16` 的份额用于走法）。
- 根割轮次按收益走：`cut_rounds` 是上限，前两轮无条件，之后只有上一轮把根界抬了至少 1.4% 才再开一轮。
- `MipOptions::primal_rounding` 与 `MipOptions::without_primal_rounding()`。

### Changed

- 基准报告的上限由实测定：求解报告的枢轴上限 1200 → 20000，小规模整数报告的节点预算 20000 → 30000。
  两处上限逐字记录在报告头部与索引里——**不同上限下的计数不能互相比较**。
- 割轮的整轮重解拿到 4 倍的迭代上限：原来"重解没跑完就丢弃整轮"会让一个本可证到最优的实例白白丢掉覆盖面。

### Fixed

- 热启动的拒签没有交回冷启动。基按检验数最优、但证书写不出来时，结果是以 `NumericalFailure`
  **返回**的，而不是以 `None` 返回的，所以回退被绕过，被丢弃节点的界随之消失。现在这类结果一律交回
  冷路径（迭代上限不交）。
- 内核的自检补齐两处：**模型变量自己的界**（此前只量内核列的非负性，两者不是一件事）与 **Farkas 射线
  的三条测量**（符号按射线自己的尺度、盒吸收、边际严格为正）。任一超容差就不发证书、报数值失败，
  搜索按"没有结论的松弛"继续。
- `nodes` 不再可能超过 `max_nodes`：每个"花掉一次松弛"的地方都先问预算。
- 报告的界改取"全部开着的活"（队列里的键 ∪ 松弛没有结论、因此不再入队的那些节点的键），
  不再因为丢弃子树而偏乐观。
- 数值失败的恢复梯子从一步扩到三步：Bland 重启 → 去掉退化微扰 → 换定价规则，后两步只在"乘子符号越出
  证书约定"这一类失败上触发，结果同样过全部自检与独立校验器。

## [0.1.2] — 2026-09-25

### Fixed

- 独立校验器算错对偶间隙的下界：`box_minimum` 在检验数落进容差带时把整项丢掉，而那一项的大小由检验数
  指向的界决定（在界为 `10²~10³` 的实例上最大可以差到自身容差的 1000 倍）⇒ 旧版本可能接受一份真实对偶
  间隙超容差的最优性证书。现在只要那个方向上有有限界，就照实算。
- 内核对偶间隙自检：宣布基最优之前量残差、乘子符号与对偶间隙三件，与校验器用同一条式子与同一套尺度。
- 无结论节点的界账目：`open_bound` 改取"队列的键 ∪ 被丢下节点的键"，界不再偏乐观。

## [0.1.1] — 2026-09-22

### Changed

- CI 补上显式的 `moon build` 步骤，让"检查 / 构建 / 测试"三步在工作流里直接可见。
- `moon run cmd/main` 不再打印开发期版本号 `0.1.0-dev`。
- 发布页的包文档与 README 补全（`cmd/main` 的包描述、过期的测试数与里程碑状态）。

## [0.1.0] — 2026-09-21

首个发布版本。

### Added

- 公开入口 `solve` / `solve_with` 与 `SolveStatus` / `Solution` / `SolveOptions`。
- MPS（free / fixed）与 LP 格式的读写。
- 稀疏修正单纯形内核：稀疏 LU 基分解、有界变量枢轴、增益定价、对偶单纯形热启动，以及 presolve / postsolve。
- `verify`：最优性、Farkas 不可行、无界射线的独立校验，证书可序列化为 JSON。
- `mip`：分支定界与根割，每个节点松弛都过 `verify`。
- `cmd/parse` 的五个子命令与统一的 `--json` 输出。
- 四份基准报告与它们的索引（含报告陈旧性的机械化判定）、CI，以及发布物自包含与公开面契约的验收。