# 算法说明

本文件写**实现里真正在跑的是什么**，以及每个策略背后那条实测数字。数字的出处是
[`bench/*.md`](../bench/README.md)（可由脚本复现的报告）、[`history.md`](history.md)（逐轮实测记录），
或这里直接给出的命令。

## 1. 模型层与标准形

模型层接受 `min` / `max`、`≤` / `≥` / `=`、任意有限上下界、自由变量与整数标记。交给内核时一律化成

```
min cᵀx    s.t.  A x = b,    l ≤ x ≤ u
```

| 模型层构造 | 内核层变换 |
| --- | --- |
| `x ≥ lb` | 代换 `x = lb + y`（`y ≥ 0`）：列系数乘 `lb` 移到右端项，`c·lb` 计入目标常数 |
| `x ≤ ub` | **列上界**，不占行（比值检验两个方向都读） |
| `ub < lb` | 显式行 `Σ sign·y ≤ ub − lb`；负右端项让运行报 `Infeasible`，而不是把负区间交给内核 |
| 下界无界 | 拆成 `x = p − n` 两个非负列；上界有限时额外加一行 `p − n ≤ ub`（两列之差没有单列界） |
| `a·x ≤ b` | 松弛列 `+1` |
| `a·x ≥ b` | 剩余列 `−1` + 人工列 `+1` |
| `a·x = b` | 人工列 `+1` |
| 右端项为负 | 整行取反并交换 `≤` / `≥`（保证起始基存在） |
| `maximize` | 代价与目标常数取反，`model_sign` 记回程符号 |

**为什么"上界不是行"值得单独说**：内核的枢轴数随行数走、与列数几乎无关。覆盖型 LP 探针实测
20 / 40 / 120 / 240 行对应 57 / 137 / 632 / 2220 个枢轴（同样 20 行时 100 列与 900 列分别是 57 与 35）。
把每个有限上界写成一行会让 507 条约束的 `fast0507` 变成 63490 行，去掉之后是 489 行，
每次枢轴从约 47.5 ms 降到 2.4 ms。

**证书回映**：内核的行是归一化过的（关系符号、负右端项整行取反），而证书必须按模型自己的行陈述。
每个内核行因此带两个因子：`row_dual_factor`（回映**乘子**，含关系符号与整行取反）与 `row_sign`
（回映**系数**，只含整行取反）。两者不是同一个数，混用会给取自 `≤` 行的割带符号错误。
等式性另存 `row_relation`：符号约定只对 `≤` / `≥` 限制、`=` 行自由，而上面两个因子的量级恒为 1，
答不出这件事。

## 2. 修正单纯形内核

- **稀疏 LU 基分解** `P·B = L·U`（行主元相对阈值）+ **乘积形式（eta）基更新**：内存 `O(nnz + fill)`。
  默认每 500 个枢轴重新分解一次；填充量由 `max_factor_entries` 预算约束，那是稀疏分解唯一无法
  事先预测的量。
- **有界变量枢轴**：非基变量停在上下界之一；比值检验同时读两种限制（基本变量落到零、基本变量升到
  自己的上界）以及进入变量自身的区间。**枢轴步长必须由比值检验选中的那一行给出**，不能在 pivot 里
  从行反推——两个界都在时"离开变量落到哪个界"决定步长怎么读，零步长的人工驱逐枢轴必须显式传 0，
  否则会拿到无界列的 `1e30` 哨兵当步长、一步写出 `1e32` 的状态。
- **定价**：三条规则，`SimplexOptions::pricing` 选（CLI 的 `--pricing`）。
  - **Dantzig**：选检验数最大者。每次迭代最便宜，但会被"速率大、步长极小"的列误导。
  - **实测增益（默认）**：检验数是**改进速率**，实际增益是 `|r| · step`，两者可以差一个数量级：
    `fast0507` 上 Dantzig 选到 `r = −121.1`、步长 `0.00632`、增益 `0.76`，而抽样里有 `r = −6`、
    步长 `1.0`、增益 `6.0`。改成"每迭代对有界候选集（Dantzig 候选、近期好列池、轮转窗口）测实际增益再选列"
    之后，同一枢轴预算下目标值 165.1 → 156.8（20000 枢轴）、→ 133.0（45000 枢轴；纯 Dantzig 要 250000
    枢轴才到 160.4），每次枢轴的增益提升约 40 倍，代价是每次枢轴 2.4 → 14 ms。
  - **Devex**（Harris 1973）：把检验数按列的权重缩小，近似"最陡边"方向长度。权重由**枢轴行**给出：
    取 `e_rᵀB⁻¹`（一次转置求解，与 `duals` 同一套乘积形式求解），令
    `G = max_j u_j²/w_j`（Harris 的 γ²），然后 **`w_j ← u_j²/G`**、进入列 `w ← 1`。
    这里必须是**赋值而不是 `max`**：因为 `G` 就是最大的缩放项，`u_j²/G ≤ w_j` 恒成立，
    `max` 形式一个权重也改不动——那就是"每迭代多一次转置求解的 Dantzig"。权重每 `DEVEX_RESET_PIVOTS`
    （1000 个枢轴）重置一次，并设下限 `DEVEX_MIN_WEIGHT`（否则枢轴行上正交的列会把排名变成无界）。
    这些数字**只用于排序**：写错只会让运行多花枢轴，不会给出不同答案——所以测试断言的是三条规则
    **落在同一个最优值**，而不是走同一条路径。

  **三条规则在同一份清单上量过**（当时的 1000 行口径：32 实例、枢轴上限 20000、presolve 开；现报告口径
  已改为 2 500 行、28 个最优，见 `bench/solve-report.md`，本表是三规则的**相对**比较、绝对枢轴数只在当时
  口径下成对可读。表里是枢轴数，19 个解完的实例的合计不含 `fast0507`——它停在 20000 的上限上）：

  | 实例 | Dantzig | 实测增益（默认） | Devex |
  | --- | ---: | ---: | ---: |
  | `mod010` | 1771 | 3455 | **1601** |
  | `danoint` | 4153 | **1907** | 3771 |
  | `misc07` | 813 | 905 | **752** |
  | `rout` | 364 | 432 | **315** |
  | `22433` | 1016 | 1035 | **978** |
  | `khb05250` | 784 | **442** | 787 |
  | `bienst1` | 1865 | **629** | 1848 |
  | `flugpl` | 11 | 17 | 11 |
  | `noswot` | 182 | **131** | 182 |
  | **合计（19 个实例）** | 15 779 | **12 361** | 15 045 |

  没有一致赢家：Devex 在 6 个实例上最少，却在 `khb05250`、`bienst1` 上明显多于增益定价；增益定价总体
  最少，所以默认仍然是它。Devex 的实测价值是**总体优于 Dantzig**（15 045 对 15 779）并在 `mod010`
  这类实例上最好。三条规则下每个实例的目标值在这份清单上逐位相同——定价改路、不改答案。

  **限度**：`DEVEX_RESET_PIVOTS`（1000 个枢轴重置一次权重）与 `DEVEX_MIN_WEIGHT`（1e-8 的下限）都是
  **有理由但没量过的常数**——三个变体（从不重置 / 100 / 10000）没跑；它们只影响走哪条路，所以"没量"
  的代价是枢轴数而不是正确性。

- **对偶单纯形冷启动：一条实测关闭的路**。覆盖型 LP 的"教科书答案"是把对偶单纯形从**全剩余基**冷启动
  （每行自己的 slack/surplus 基本、对偶量全零 ⇒ 检验数就是成本本身，覆盖型模型的成本非负所以对偶可行），
  而这正是 `fast0507`（63 009 列 / 507 条覆盖行 / 472 358 非零）卡住的地方。实装成 `SimplexOptions::dual_start`
  + CLI `--dual-start` 后**回退**，三条实测：① 原始两阶段路径在 40 000 枢轴（8 分钟墙钟）后目标仍在下降
  （164.25 → 152.94），报告口径的 20 000 枢轴远远不够；② 对偶冷启动**真的跑起来了**（全剩余基通过对偶可行性
  检查），但同样在 20 000 枢轴内没有结论；③ 它对整份清单**只有代价**：`--solve --dual-start` 跑满 32 个实例的
  墙钟从 **107 s 变成 644 s**（每次尝试先花掉自己的预算、失败后再走两阶段路径），而 20 个已解实例的枢轴数
  **逐个逐位相同**。⇒ "对偶单纯形适合覆盖问题"这条在**这个实现**上不成立：缺的是对偶侧的防停滞与界翻转机制
  （对偶比值检验、最不可行行的选择规则），不是"一个冷启动入口"；要碰就得先把对偶路径做到与原始侧同等。
- **Harris 两遍比值检验 + 可行性守卫**、**退化扰动**（确定性，默认 `1e-12`，只用于打破平局）、
  **停滞窗口触发 Bland 规则**（固定窗 500 个枢轴，不随 `m` 变）。窗口取固定值是有实测理由的：旧口径
  `2m + 50` 在 63490 行的实例上要求 127030 个连续不改进枢轴，等于永远不会触发。目标重新有改进时解除
  闩死——闩死不解的代价实测是 `mod010` 15527 → 3455 个枢轴、20 个实例总枢轴 24408 → 12336（−49%），
  其余 19 个逐位不变。解除不丢保证：循环是零改进，会在窗口内重新触发；以 Bland 起步的恢复尝试保持闩死。
- **自检（为什么内核宁可报失败）**：三角求解只保证**残差**小、不保证**误差**小（病态基上两者差一个
  条件数），所以每个结论都要量它所依据的那个方程的残差。
  - 对偶量 `c_B − Bᵀy`：一步迭代精化把 `noswot` 某节点从 `3.7e-7` 降到 `4e-13`，而那一点的真乘子是 0。
  - 方向量 `aⱼ − A·d`：每迭代自检。一次差值 20 的枢轴曾让一个有界节点被报成无界。
  - 非负性**按逐变量**量：曾按整个解的最大元素缩放，`-7.7e-7` 挨着 `1e5` 量成 `7.7e-12` 放行，
    而校验器按 `raw/(1+|xⱼ|)` 量成 `7.7e-7` 拒签。
  - **模型变量自己的界** `[lⱼ, uⱼ]`：非负性说的是内核列 `xⱼ ≥ 0`，两者不是一件事（内核的 `upper`
    是 `uⱼ − lⱼ`，拆成两列的变量干脆没有），所以取 `KernelProblem::model_lower` / `model_upper` 来量。
    实测：一次"去掉退化微扰"的恢复走法对一个**越出变量界 0.0029**的点（容差 1e-7 的四个数量级）
    宣布了 `Optimal`，行残差与非负性两条都看不见它。
  - **行乘子的符号约定**：按校验器同一条式子 `raw · max|aᵢⱼ| / max|cⱼ|`（下限 1，`=` 行自由）量。
    超容差先 `refactorize()` 重测，仍在容差外就报 `NumericalFailure`，而不是发出注定被拒的证书。
  - **对偶间隙**：前几条各说一半——点是可行的、乘子写得出来——都不说**乘子证明的那个界**是否等于
    **这个点有的目标值**。式子与尺度逐字取校验器那一条 `|primal − L| / (1 + |primal| + |L|)`，
    模型自己的系数、界与右端项由 `KernelProblem::model_cost` / `model_lower` / `model_upper` /
    `model_rhs` 一路带过来，而不是从标准形反推。
  - **这几条自检的开销量过**（20 个实例、上限 20000，短路对照）：方向残差自检 −0.05%（噪声内）、
    枢轴稳定性校验逐位相同（在这份清单上从不触发）、每枢轴的时钟成本 1.55 ms（有自检）对 1.57 ms（去掉）。
    一个迭代由增益定价决定，所以**自检的代价落在"把运行送上哪条枢轴路径"上，而不是时钟上**。
    间隙自检只在一次成功求解的收尾跑一遍（结构列一遍、模型行一遍），不随枢轴数增长；它的间接代价
    在语料上看得见：触发 `refactorize()` 会换一条树。
- **恢复梯子**：数值失败时依次换三条走法，**每一次都是一次完整求解**，结果同样过全部自检。
  1. **Bland 重启**：从初始基重启，改用 Bland 规则并缩短重新分解间隔。这一步对**任何**失败都做。
  2. **去掉退化微扰**（只在失败是"乘子符号越出证书约定"这一类时）：微扰是加在每行右端项上让并列变
     严格的小量，它同时决定这次运行落在对偶面的哪个顶点上，所以要换乘子就得换它。`blend2` 上那三个
     "基按检验数最优、却写不出证书"的节点（符号违反 2.73e-7 / 1.15e-7 / 1.15e-7，容差 1e-7，分别只花了
     248 / 293 / 287 个枢轴）在无微扰的走法下都有了结论，界 `7.479003457675444 → 7.571088603672391`、
     gap `0.11998154232455605 → 0.027896396327609096`。
  3. **换定价规则**（同一个门）：定价规则决定运行走哪条路到顶点，所以也决定落在最优面的哪个顶点上。
     影子探针（在无结论的分支里对同一模型试几种走法，**不计入 `nodes`**，运行轨迹逐字不变）实测：
     同一个模型在 `gain_candidates` 0 / 4 / 128 下都写出证书（331 / 331 / 312 个枢轴），而调用方用的 32
     拒签，于是第三步取候选数最少、规则最老的纯 Dantzig。结果是 `blend2` 报
     `mip=optimal nodes=24934 verified=24934 obj=7.598985`（该实例的公开最优值）。
  为什么第 2、3 步必须限定在符号这一类：把无微扰走法用在任何失败上时，`noswot` 的一次恢复回来的是
  `Infeasible`，而它的射线被校验器拒（符号违反 `7.65e18`）——在分支定界里，被拒的证书会停掉整轮，
  比丢掉一个节点贵得多。另外，把无微扰**当默认值**会让整条轨迹都变（`blend2` 的当前解从 `7.598985`
  掉到 `8.970912`），所以它只是一次恢复尝试。三次都失败时返回**原始失败**并标注。

## 3. 对偶单纯形热启动

改界之后**检验数不变**（它们只依赖基与目标），所以上一次的最优基对子问题仍然对偶可行，缺的只是原始
可行性——这正是对偶单纯形修的东西。契约是"只是提速，永不给出不同答案"：形状不匹配、对偶可行性丢失、
数值失败一律回退冷启动。

**拒签也要回退**：`SimplexStatus::NumericalFailure`（基按检验数最优、但证书写不出来）是以**结果**
返回的，不是以 `None` 返回的，所以它必须显式交回冷路径。实测代价：`blend2` 的树在 24743 个松弛处跑空，
其中 **40 个松弛在热启动路径上没有结论、冷启动重解全部有结论**，而它们被丢掉的键正是运行报出的界；
修正后小规模口径下 `blend2` 的界 `7.399764899326714 → 7.479003457675444`，`noswot` 的"无结论松弛"
`91 → 2`。冷回退不计入 `nodes`（沿用既有的口径），`IterationLimit` 不交回。

**布局也是契约的一半**：形状相同（行数 × 列数相同）不代表编号相同。核行右端 = 模型右端 − `Σ aⱼ·lⱼ`
（下界平移进右端），**分支收紧下界会移动它**；跨过零的行整体取反（`≤` 变 `≥`），该行的附加列从
一个 slack 变成 surplus + artificial，**其后所有附加列重新编号**——两个这样的布局可以行数列数都
相同。实测（`noswot`，30 000 节点）：一个运行把 **155 个**这种基交给了 `new_with_basis`，每一个都
含同一行的两个单元列（精确奇异——列集被另一套编号重读出来的形状），10 个松弛因此到达不了结论。
`SimplexBasis::layout`（每行起始列、每个变量的列分裂、行的关系与取反号的指纹）在装载前比对，不符即
拒——与形状不符同一条冷回退。修复后 `noswot` 的无结论松弛 **10 → 3**、`verified` 29 990 → 29 997，
两份 MIP 报告的覆盖面不动（剩下的 3 个是中途在整数系数上形成的精确相关，是另一个口子）。

**加行之后的热启动**走同一条论证：新行乘子从 0 起 ⇒ 检验数不动、基仍对偶可行；把新行自己的
松弛/剩余列（**不能用人工列**，它会吸掉违反量）设为该行基变量，其值就是"点违反该行多少"，再由对偶
单纯形修。实测把"每个候选割都重解一次"的代价从 45.8 s 压到 1.0 s（`22433`，14 倍）。但它只用在测量上：
用在割轮整轮重解会落到退化最优面的另一个顶点、传给子节点的基随之改变，实测改树变差
（`p0201` 586 → 808 节点）。

## 4. Presolve 与 postsolve

归约：空行 / 空列、冗余行、singleton 转界、隐式界收紧、**对偶固定**、固定变量消元（含目标偏移）、
**等式 doubleton 代入**（`a·x + b·y = r` ⇒ `y` 整列离开模型：其余项拼到 `x`、目标项拆成偏移加项、
`y` 的盒子搬成 `x` 的区间取交、行消失；还原沿可链式的代入链解析；只做等式——不等式 doubleton 只钉
一侧，隐含界已覆盖；总填充预算 10 000，实测语料最大 `mod011` 的 1 568）。
**每条归约先证明再触发**；化简自己证出的 `Infeasible` / `Unbounded` 直接作为结论上报，不交给内核。

**实测（等式 doubleton 代入）**：前提是量出来的——presolve 之后剩下的等式 doubleton 几乎全在
`mod011` 上（2 077 / 4 479 行），此前"解不完"（基奇异）的它在 20 000 行上限下 **solve=optimal**
（−62121982.55190222，10 177 枢轴）；报告口径 27/32 不变（它的行数在 presolve 之前被挡），受影响
已解实例目标逐位一致、枢轴净 −85（唯一上升 `cap6000` +1.5%）。

**对偶固定**把一个变量钉在某个界上，条件是"目标想走的方向不会让任何一行更难"：对 `≤` 行，系数为正时
减小变量只会放松它；对 `≥` 行则要求系数为负，`=` 行两个方向都不合格。所有出现它的行都满足这条时，
任何可行点都能挪到那个界而仍然可行、目标也不变差，于是"存在一个最优解落在那个界上"。两条边界写进了
代码：**整数变量只钉在整数界上**（断言的是"存在一个取该值的最优解"，不是"这个值可以取整"），
以及**界已经冲突（`lb > ub`）的变量绝不参与**——把它钉在一个它自己的区间都不再包含的值上，等于把
一条不可行结论盖过去；那种情形归 `eliminate_fixed` 判并上报。这一条不是推出来的，是实测撞出来的：
它在随机模型语料上让一个 `−x₀ = 5, x₀ ≥ 1` 的模型从 `Infeasible` 变成"有解"（差分测试立刻变红），
所以对偶固定在**每轮的末尾**运行，排在 `eliminate_fixed` / 空列消元之后。

**实测量（对偶固定，当时的 1000 行口径清单）**：它多消掉了 23 个变量（`gt2` 15、`misc07` 6、`flugpl` 2、
`noswot` 1），求解报告的总枢轴 12 336 → 12 361（+0.2%），覆盖面一个没动（20 最优 / 11 跳过 / 1 到上限），
`gt2` 的枢轴 36 → 35、`misc07` 879 → 905。这是一个"触发得很干脆、收益很小"的归约，数字如实写在这里，
而不是拿它去换默认行为。

回程：`reconstruct` 把化简解映回原变量，调用方用 `max_row_violation` / `max_bound_violation` /
`objective_value` 在**原模型**上复核——化简自己的记账不是证据。

**整数行强化**（`strengthen_integer_rows`，只走整数路径）：同一份算术给两样东西，一行可以给其中一样、两样
或都不给。统一写成 `≤` 形式（`≥` 行乘 −1），`rest_min` / `rest_max` 是**其它项**能贡献的最小 / 最大量。

**隐含整数界**：`aⱼxⱼ ≤ b − rest_min`，对**整数** `xⱼ` 就是界——

```
aⱼ > 0:  xⱼ ≤ ⌊(b − rest_min) / aⱼ⌋
aⱼ < 0:  xⱼ ≥ ⌈(b − rest_min) / aⱼ⌉
```

它只从**松弛**里拿掉整点、不从模型里拿掉整点，这正是整数路径需要一个 presolve 的理由。它的前提比另一半松
得多：只要其它项在各自符号所花的那一端有界（**最小**贡献有限）。会与变量另一端的界交叉时就不做——`lb`
高于 `ub` 是 `eliminate_fixed` 的判断，不是一次重写的判断。

**系数**：写 `xⱼ = lⱼ + yⱼ`，行允许 `yⱼ ≤ k`，而系数只能抬到"其它项取各自最大时还能保住这 k"的高度：

```
k  = ⌊(b − aⱼlⱼ − rest_min) / aⱼ⌋     变量能取到的最大整数步数
aⱼ' = ⌊(b − aⱼlⱼ − rest_max) / k⌋      还能保住这 k 的取值
```

两边都用 `rest_min` 是错的，而且不是学术差别：`3x + y ≤ 5`、`x, y ∈ [0,10]` 整数会被改成 `5x + y ≤ 5`，
丢掉 `(x, y) = (1, 2)`。抬高一个系数同时抬高它在自己上界端的贡献，而那是同一行其它项 `rest_max` 的一部分，
所以一处抬高之后，下一个项读到的那两个和是**就地修正**的。

**两半的容差方向相反**，因为算错的代价相反：界算松一元只是少剪一点，所以整数值带着 allowance **加上**去读；
系数算大一元会拿掉一个整点，所以带着 allowance **减掉**去读。后者会拒掉"许可恰好落在一个整数上"的情形，
而数据全是整数时那恰是最常见的情形 ⇒ 凡是算术允许的地方就不去"读"许可，而是**证明**它：
`ā·k + rest_max ≤ room`，而 2⁵³ 以内的整数加法与乘法都是精确的，于是这个证明是证明而不是读数。

它跑在分支定界之前（`mip::solve_mip` 的入口），因为线性 presolve 见不到整数模型（整数模型的答案不能取决于
化简碰巧定死了什么），所以需要整数性的归约在那里没有一行可以触发。`MipOptions::row_strengthening`（默认开）
可以关掉它，此时 `MipResult::strengthening` 如实报零。

**实测量（`--mip --json`，两份报告各自的清单口径）**：15 个进入分支定界的实例里，**界那一半在 4 个上触发、
共收紧 81 个变量界**（`noswot` 65、`blend2` 9、`p0201` 6、`gt2` 1），**系数那一半一行也没有**；小规模清单是
它的子集，数字相同。

两份分支定界报告相对上一版（只有这条改动）的差异**两升一降**，两个方向都如实写：

| 口径 | 实例 | 当前解 | gap | 证明成本 |
| --- | --- | --- | --- | --- |
| 300 节点 / 32 实例 | `gt2` | 无点 → **21166**（最优） | 1e300 → 66.02 | 30 条割（不变） |
| 300 节点 / 32 实例 | `noswot` | −35.000000000009315 → **−39.000000000007525** | 8.00 → 4.00 | 10 → 20 条割 |
| 300 节点 / 32 实例 | `p0201` | 7975 → **7785** | 420 → 220 | 20 → 30 条割 |
| 30000 节点 / 10 实例 | `gt2` | 38455 → **21166**（最优） | 18222 → 66.02 | 30 条割（不变） |
| 30000 节点 / 10 实例 | `p0201` | 7615（已最优） | 0 | **609 → 555** 个松弛 |
| 30000 节点 / 10 实例 | `noswot` | −40 → **−39.000000000007525** | 3.00 → **4.00** | 2 → 10 个松弛无结论 |

覆盖面两个口径都没变（3/32、5/10）——这张表的宽口径一列测于当时的 **300 节点**版本，现报告口径已改为
**600 节点**（最浅的证明 `p0201` 落在 577 个松弛上，600 是最小的整百覆盖值），宽口径覆盖因此是 5/32；
上表的每一格都只与它自己那一行的预算成对可读。注意 `gt2` 的开界也跟着动了（20232.49 → 21099.98）：这条改动改的是
**树**，不是"界必然更紧"，所以同一实例在不同预算下一升一降是正常结果，写的时候两个方向都要写。

**限度（如实写）**：① 一次调用只扫一遍，收紧后的界不拿回去重算同行其它项（保守方向：代价是紧得慢，不是错）；
② 容量超过 `1e9` 的项跳过（整数值读不出来，那个量级的"收紧"也不值这份算术）；③ allowance 一旦大于一个单位
就整行跳过——那说明这个界连到一个单位都定不下来，此时取整不被许可。

**系数那一半为什么在本清单上一次也不触发（量出来的，不是猜的）**：给这一半加了一个临时探针，按"第一个没
过的前提"给每个（行，整数变量）候选计数，跑两份报告各自的清单（15 个实例）：

| 挡住它的前提 | 候选数 |
| --- | --- |
| 系数为负——镜像的一半没写 | 10 718 |
| 行能到达的范围已经装满了变量的盒子（守卫直接跳过） | 2 490 |
| 其它项**最小**贡献无穷 | 301 |
| 其它项能贡献的范围太宽，抬高没有收益 | 70 |
| 其它项**最大**贡献无穷 | 28 |
| 变量自己两端界无穷 / 容量读不出来 / allowance 过大 | 0 |

第二行那 2 490 个是**守卫过严**：许可要除的是"变量能取到的最大取值"，那个值是 `min(行的可达步数, 盒子宽度)`，
旧守卫却要求"行比盒子宽"才动手，正好把盒子绑定的一类（二值变量，或界已经被其它行压紧的变量）全部跳过。
改成 `min(k, span)` 之后这一半**真的开始触发**（`blend2` 的 79 行系数被抬高），但**实测有害，已回退**：
`blend2` 在小规模口径（30000 节点）从"**证明最优 7.598985，24934 个松弛**"退成"30000 个松弛未证完、当前解
8.970912、界 7.564854、gap 1.406"，宽口径从"没有整点、界 7.139367545067016"变成"有整点 28.714988（gap 21.63）、
界 7.0847655592606955"——界变差、证明变贵，覆盖面还会从 5/10 掉到 4/10。这与本项目反复量到的同一条规律一致：
这条改动改的是**树**，不是"更紧的松弛必然更好"。

第一行那 10 718 个（镜像的一半）不值得接着写：抬高一个系数能通过的**必要条件**是"其它项能贡献的范围比该
系数还窄"。把许可写成 `left = c·reach − Δ`（`Δ = rest_max − rest_min`）就能看出来——触发要求
`m ≤ c·f − Δ`（`reach = m + f`，`m = ⌊reach⌋`），于是 `Δ < c` 是必要条件。镜像那一半是同一套算术、同一个
`Δ`，撞的是同一堵墙，写了也只是把"不触发"从一行挪到另一行。⇒ **系数抬高这一半在本语料上关闭**；能动的
只剩把行**换掉**（更强的割或更紧的建模），而不是在同一条规则上继续调容差。

**列支配**（`remove_dominated_columns`，只在 0/1 集覆盖模型上触发）：一条列 `B` 可以固定为 0，当存在另一列
`A` 满足四件事——成本不高于 `B`、覆盖 `B` 覆盖的每一行、在那些行上的系数不小于 `B`、并且**自己就足以满足
每一行**（`a_rA ≥ b_r`）。改法是任取一个 `x_B = 1` 的可行点，置 `x_B ← 0`、`x_A ← 1`：`B` 覆盖的行少掉
`a_rB`、`A` 至多补上 `a_rA`，而 `A` 原本就是 1 的那些行仍由它自己满足；目标不升，因为 `A` 不比 `B` 贵、
且模型没有负成本。所以最优值不变——这是**等价变换**，不是松弛，代价是那几条前提要一条不落地检查。

第三条（覆盖的包含）与第四条（单独满足该行）不能省。右端项大于 1 时一条列未必能独自满足该行，而只比覆盖的话
`x_A = x_B = 1` 的删法会让行少掉 `a_rB`、没有任何东西补回来。**量到的代价**：按"覆盖超集 + 成本"筛（缺第四条、
也不先行分类）时，`markshare1` 从 `node-limit obj=80` 变成 1 个节点就判 `infeasible`、`pk1` 在被删掉 86 列中的
54 列后从 `node-limit obj=18` 变成 `optimal obj=726`——两个都是错的，而报告里它们只会表现为"这一行忽然解出来了"。

**实测（两份清单 32 个实例，只读结构探针 + 现实现的计数）**：只有 `fast0507` 属于这一类（507 个 `≥` 行、系数
全 1、右端项 254 个 1 与 253 个缺省 0、成本 1 或 2），它删掉 **36 670/63 009 列（58.2%）**；`markshare1`/
`markshare2` 是纯等式模型、`pk1` 的行与变量都不在这一类、`gt2`/`noswot`/`blend2` 同理，所以 `columns_compared`
对它们是 0——那是"没看"的记录，与"看了没东西"是两句话。

**为什么它不动报告数字**：`solve-report` 跑的是 `--relax`（LP 松弛），删列会改变 LP 的最优值；`mip-report` 的宽
口径按 `--max-rows 300` 把 507 行的 `fast0507` 记为 skipped，小规模清单里没有这个实例。所以这条规则的收益是给
**使用者手上的集覆盖模型**的：列数从 63 009 降到约 26 000 时，同一实例的 LP 在同样的 20 000 枢轴上限下墙钟
263.6 s 对 327 s（−19%），两次都停在 `iteration-limit`，所以这是墙钟的比较而不是目标值的比较。

**限度**：① 只扫一遍，删掉的列不再当候选，正确性靠传递（支配关系在"成本不增、覆盖不缩、系数不减、单独满足"下
传递）；② 候选只在 `B` 覆盖的**列数最少**的那一行里找，任何支配者必然出现在 `B` 的每一行，这既是剪枝也是正确性
的补集；③ 成本相等时用严格序——更便宜的必然支配，同成本要求覆盖严格更大或索引更小，否则一组相同的列会互相
删除（早期那个筛子就因此报出 100% 支配：`blp-ar98` 16021/16021、`50v-10` 2013/2013）；④ 模型有负成本、或有
一个变量能取 1 以上、或有非 `≥` 行时整条规则不启动，而不是"尽量做"。

实测（求解报告口径）：`30n20b8` 被化简掉 7282 个变量（18380 → 11098，内核行 18956 → 11591，降 39%），
之后 11591 行 16 秒解到最优；而集覆盖型的 `fast0507` 几乎没有可约的上界行（63009 → 63001 个变量）。

## 5. 割平面（混合整数舍入）

**一条割是"一行 + 它由哪一行舍入而来的证明"**，证明 = 模型行的组合（`rⱼ = Σ yᵢaᵢⱼ`、`β = Σ yᵢbᵢ`）。
混合整数舍入要求：基变量是整数且系数为 1、行内其余变量都由**有限界**写成非负变量、连续变量只能按
`ā/f₀` 或 `−ā/(1−f₀)` 进入（它不能当计数器）。

独立复核 `verify_cut` 把这一行**重算一遍**并逐条量：组合重现自称的行、基变量整数、有限界移位、小数
部分按 `combination_noise`（产生这一行的算术有多大）而不是绝对值判、**割必须大于产生它的算术**
（否则等于凭舍入噪声宣布"没有整数点存在"）、与交上来的行逐项相同。拒绝即停成 `Unverified`。

**为什么要这么多防线**：一条无效割会把整数点（可能是真最优）从它落地的节点起删掉，而现有的每条防线
都会继续点头——后续松弛被正确求解、证书拿带割的模型去校验、报告的点复核也拿带割的模型量。

**实测**：加割之后 `khb05250` 从"不加割要 7552 个节点（293.6 s）"变成 305 个节点证到 106940226，
`p0201` 从"20000 节点内证不出"变成 586 个节点证到 7615，`22433` 从 59 降到 33 个节点。
这三组数字测于原始启发式引入之前；当前报告口径下它们分别是 **107 / 609 / 33** 个节点
（见 [`../bench/mip-report-small.md`](../bench/mip-report-small.md)），割的影响方向不变。

**选择规则**：一轮里的候选割在违背量上完全并列（每个单行割在被导出的那个点上恰好违背一个自身尺度
单位，`markshare1` 根节点的 6 个候选实测全是 1），所以"按强度取上限"实际是按行序截断。量过五条规则
（efficacy、单条实测增益、联合增益贪心、上限翻倍、行序），**没有一条在"界"与"证明成本"两个轴上同时
赢过现状**：联合增益贪心让 `22433` 从 33 涨到 241 个节点、`gt2` 的界低 1161；把每条割的候选上限从 10
翻到 20 能把 `gt2` 的界推到那个轮次下的天花板，代价是 `p0201` 的证明从 586 涨到 1204 个节点。原因是**割的价值是"树"的
属性，不是"根松弛"的属性**：一条对根松弛毫无推动的割仍会割它下面节点的松弛，而任何以根松弛为判据的
选择规则都会正好丢掉那批割。整轮重解的迭代上限比常规松弛长 4 倍：一轮割的取舍全押在这一次重解上，
"没跑完"是关于上限的话——`mod010` 的第二轮重解跑不完曾让整轮被丢、界停在 6540.4（公开最优 6548），
上限抬到 4 倍后该轮被保留，该实例 31 个节点证到最优。

**割族边界（量过的死路，勿重走）**：除了混合整数舍入，试过且关闭的还有多行 MIR 聚合、{0,1} cover / 背包族、
节点上的割，以及**覆盖型 cover 割**——最后这条不是"弱"而是**数学上恒冗余**：对覆盖行 `Σ aⱼxⱼ ≥ d` 的
cover `C`，`Σ_{j∉C} aⱼxⱼ ≥ d − Σ_{j∈C} aⱼuⱼ` 是"原行 + cover 变量上界"的直接外推、**不含整数性**，所以对
LP 松弛永远冗余（改不了多面体）；二值 cover 割的强度来自"二值变量不能全取 1"这个整数性，把它丢掉之后 cover
割就退化回去了。它能前进的唯一方向是**把整数性搬回来的 flow cover / lifted cover**（λ 截断那一套），公式需要
可靠出处，属于研究项而非旋钮（探索轮与推导见 [`history.md`](history.md)）。

## 6. 分支定界

- **best-bound**：界是最好的剪枝依据（没有可比的最优解时，界剪不掉任何东西）。
- **节点 = 父节点 + 一条收紧的界**，沿链从根重建；子节点从父节点的最优基热启动。
- **incumbent 的 cutoff 花在盒子上，而不是加一行**：找到当前整数点之后，"值得找的点必须比它更好"
  就是一条关于目标的约束，于是把一项用 cutoff 与其余各项在各自盒子上的最小可能贡献夹住
  （`value_k·x_k ≤ cutoff − Σ_{j≠k} min_j`），整体 `O(n)`，空盒子直接剪掉、连一次求解都不花。
  它与"加一行 cutoff 约束"在剪枝上等价（一行只在松弛已经知道它能更好的地方活跃），但收窄的盒子还会
  收窄后续分支。报告口径实测：32 实例 300 节点口径只有 `gt2` 一行的界在 1e-15 相对量上动（舍入级），
  小规模口径里 `markshare2` 的当前解 `192.00000000369937 → 144.99999999986127`，已证最优的实例一字未动。
- **割只在根**：根的割被整棵子树继承，这样"节点 = 父节点 + 一条界"的形状与节点间热启动都保持不变。
  一轮割只有在其重解**给出结论且不变差**时才保留，否则整轮丢弃（`noswot` 上 20 条割曾让根重解跑不完，
  原始写法让整个运行在 3 个松弛后结束、界为 0，比不加割更差）。**切几轮按收益走**：前两轮无条件，
  之后只有上一轮把根界抬了至少 1.4% 才再开一轮，轮数上限由 `cut_rounds`（默认 4）界住。实测
  `khb05250` 每轮加 5.6 / 2.4 / 1.5 / 0.4%、证明成本 305 → 185 → 114 个节点（与上一段同一口径），
  而 `p0201` 第三轮只加 0.5% 却把证明从 586 拖到 1135、`flugpl` 第三轮加 0.02% 把 13806 拖到 14938。
- **原始启发式只提供当前解**：取整读出整点（松弛解出来之后把整数变量挪到整数，一遍 `O(nnz)` 扫描、
  零次求解，试就近 / 向上 / 向下三种取整以及按小数部分无偏采样的随机取整）、取整修复（三种取整都不
  满足模型时把整数固定在某个取整上重解）、可行性泵（取整 → 让松弛朝那个整点投影 → 再取整，最多 5 次
  投影）、下潜（走最分数变量较近的整侧、重解、往复）。四者都走与节点同一条求解 + 校验路径、计入
  `nodes` / `verified`、受同一预算约束，**永不主张最优**。
  实测：取整读出整点让 `blend2` 的当前解直接变成公开最优 `7.598985`、`p0201` 变成正好 7615、
  `50v-10` 从无解到有解；修复让 `markshare1` 138 → 112、`markshare2` 145 → 122、`pk1` 36 → 18；
  泵让宽口径的 `dcmulti`、`rout` 第一次拿到整数点；采样取整让 `noswot` 的当前解从 `-35.000000000009315`
  到 `-40`。限度：对"离可行很远"的实例（`gt2` / `dcmulti` / `rout`），两万次采样一个可行点都没采到——
  空间大不等于样本密度够。
  **口径提醒**：上面每一句都是**它被测那一版**的数字；这些机制都作用在同一条搜索轨迹上，所以换任何一版
  代码都要重新看报告，而不是沿用这里的话——第 4 节的整数界强化之后，同一清单上 `noswot` 是
  `-39.000000000007525`、`p0201` 是 7785。
- **下潜的启动条件按价格定**：每个未定整数按 5 步收费（`gt2` 落地那次 82 步 / 18 个整数），
  `dive_steps`（默认 150）是它的上限；`2×分数变量` 那条是**下界**而不是价格。被上限截断的走法既不报点
  也不报证明，树却为它付了预算。启动门槛有两条：`depth ≥ 分数变量个数`，以及"当前解离这次运行的开界
  很远"（差 ≥ 1/5，只花 `dive_attempts`、不动下潜储备）。另外还有一份**下潜储备**：一个跑掉半个预算
  还没有任何整数点的运行既没有东西可剪枝、也没有东西可报告，于是给它留 `max_nodes / 16` 的预算份额
  用于额外走法，条件是"过半仍无当前解"且"储备能负担一整次走法"。
- **树顶的分支按实测选，其余按小数部分选**（`strong_branching_depth = 2`：
  `strong_branching_choice`）。默认规则是"最分数的整数变量"，它的问题是**它可以是完全无用的分支**：
  `gt2` 的根（30 条根割之后）上，十个最分数的整数变量各自的两个子节点都把父节点的界原样还回来
  （`21099.97754330556`，十位有效数字相同），而 `x82` 的下侧子节点是 **21668.24** —— 高于模型最优值
  21166，那一侧直接被剪掉。固定选最分数变量于是把 `gt2` 卡在 `21099.98` 到 21166 之间的 66.02 上，
  2 万个节点只把界推动 7e-10。现在的做法分两步、按**便宜的那一步先做**：
  ① 先量调用方自己的候选（仍是最分数变量）的两个子节点，两次松弛；若它已经把"较差的那一侧"抬到节点自己
  的界之上，就用它、到此为止；
  ② 只有当它抬不动界时，才把测量扩到另外最多 4 个候选（`strong_branching_candidates`），按
  `min(sign·down, sign·up)` 取最好的（两侧都贵的分支才值钱）。
  测量的每次松弛**都计入节点预算、都过 `verify`**（未过校验的子节点不当证据用）；剩余预算不足 8 次
  （`strong_branching_budget_floor`）或调用方自带节点求解器时不做；从不越过预算。
  实测（报告口径）：`gt2` 从 `node-limit`（界 21099.98、gap 66.02）变成**331 个松弛证到最优**；
  `p0201` 555 → 577、`khb05250` 107 → 113、`22433` 33 → 39、`mod010` 31 → 21（都仍证到最优），
  代价是 `flugpl` 的界 −0.1%、`misc07` 的界 −0.4%；两份报告因此从 4/32、5/10 变成 **5/32、6/10**。
  **门槛本身就是量出来的**：不设门槛（树顶三层、每个节点无条件 `2×8` 次测量）时，`gt2` 一样变成
  证明，却把 `p0201` 的证明从 555 拖到 600 之外 —— 换一个实例丢一个实例，覆盖面不动、成本上升。
  这条规则的**边界也量过**：四个未证实例（`markshare1` / `markshare2` / `pk1` / `noswot`）的树顶
  两层，全部 228 个分数候选、456 个子节点里**没有一个**把较差一侧抬离父界（`markshare1` /
  `markshare2` 的子节点界精确为 0）—— 测量在这批实例上买不到分支，它们的缺口在别处
  （`markshare1` / `markshare2` 的缺口 ~99% 在整数解一侧，当前解离公开最优两个数量级；见
  [`history.md`](history.md)）。
- **`nodes` 永不超过 `max_nodes`**：每个"花掉一次松弛"的地方（节点松弛、割轮重解、修复、泵投影、
  走法的一步）都先问预算。测试是遍历式的（每个模型 × 预算 1..8 断言 `nodes ≤ budget`）。
- **预算的尾部围绕当前解再解一次邻域**（`neighbourhood_pass`，旋钮 `neighbourhood_passes`）：放开
  前 20 个整数变量、其余固定在当前解的取整值上，交给一次普通搜索。前提的两端都是量出来的：
  `markshare1` 的当前解是 **10 整数**邻域的局部最优（子问题 73 个松弛证空），**20 整数**邻域含 94
  （3 970 个松弛）。触发在尾部（`max_nodes / 8`），三道门（有当前解、离界"远"、整数够多）让要收口
  的运行分文不付——`p0201` 宽口径仍 577 个松弛证完。实测：`markshare1` 99 → 80（小规模）/
  257 → 105（宽口径）、`markshare2` 122 → 103；`pk1` 不变（邻域无猎物）、`noswot` 逐字不变
  （gap 过不了"远"门）。内层 `neighbourhood_passes = 0` 结构性不嵌套；尾部花完的那个迭代以
  `continue` 交回预算检查（第一版漏了它，宽口径每个触发的行都报 601/600）。
- **报告的界取在"开着的活"上**，不只是队列：一个松弛没有结论的节点被弹出后不会重新入队，但它的键是
  父节点的松弛目标值，对它整棵子树都有效；只遍历队列会把这份界连同子树一起丢掉，而 best-bound 弹出的
  正是键最小的那批，于是丢掉的方向固定是"界报得更好看、gap 报得更小"。现在取"队列的键 ∪ 被丢下节点的
  键"（节点本身仍不入队）。实测（小规模口径）：`blend2` 的界 `7.5784463643777125 → 7.399764899326714`，
  300 节点口径无一行变化。注意两类"没有结论"的分工：主循环的节点丢界所以要计进去，**下潜的一步不丢界**
  （出发节点有结论），它只体现在 `nodes − verified` 的差里。
- **整数无界性只在证明得了的时候主张**：内核报松弛无界时，检查松弛证书里的点与改善射线是否在**每个整数
  变量上都取整数值**（`integral_on_integers`，只读整数变量、按容差读）。两者都整数即 `x⁰ + k·d` 对每个
  整数 `k ≥ 0` 保持整数且可行——`d` 是已校验的回收方向、`x⁰` 是已校验的可行点——于是报
  `MipStatus::Unbounded`，`MipResult::values`（点）与新增的 `MipResult::ray`（射线）就是证明的两半；任一
  不是整数则仍报 `UnboundedRelaxation`（松弛无界、模型未知），因为内核给出的射线可能带分数（把它按分母
  缩放到整数是另一步）。报告口径下没有实例报无界，所以这是**能力补齐**而不是数字移动；白盒测试测"只读整数
  变量、容差内的值算整数"，黑盒测试测"分数点必须保守回退"。

## 7. 证书与校验

- **最优性证书** = 可行点 + 满足符号约定的行乘子 + 互补松弛 + 对偶间隙为零。
- **不可行证书** = 同一套式子取 `c = 0` 并要求严格为正（Farkas）。
- **无界证书** = 可行点 + 改善射线。

`verify` 复算全部项目并给出逐项测量，`Verdict::reason` 是第一处失败的原话。生产端在发不可行证书前
自己量校验器关于射线的三条测量（式子与尺度逐字取校验器）：

- `ray_sign_violation`：符号约定，按**射线自己的尺度**读——不可行证书的尺度是地板值 1
  （射线是关于行的证明、不含目标），不是运行自己的 `max|cⱼ|`；
- `ray_box_absorption`：某个变量的检验数（取 `c = 0`）指向一个无界方向，说明这条射线没有被盒子吸收；
- `farkas_margin`：`Σⱼ min over [lⱼ,uⱼ](rⱼxⱼ) + D`（取 `c = 0`）必须严格为正、按 `1 + |D|` 缩放；
  零边际是那条平凡组合，什么都不证明。

任一超容差就报 `NumericalFailure`（消息带三个实测量），不发出注定被拒的证书；这类状态按"没有结论的
松弛"计（`verified < nodes`），搜索继续。另有一条关于算术自洽的代理判据同时保留：人工和必须能吸收它
要解释的违反量（`Σ a ≥ max v`；`noswot` 节点 1558 上原始残差 1.94e-6 而人工和只有 1.2e-11）。
两者互不蕴含——一个问算术是否自洽，一个问射线是否是证明。

**无界证书**的生产端同样先量后发，而且**点的部分与射线的部分分别量**。点是"跑在这上面"的那个状态：
一条 `max_scaled_residual`（行残差，与校验器 `row feasibility` 同式）加一条 `max_bound_violation`
（模型变量自己的界，与校验器 `variable bounds` 同式）——后者此前只有最优性路径在量，无界分支漏了它，
而变量可以落在每一行之内却落在自己的界之外。射线由 `unbounded_ray_reading` 一次性给出校验器读它的四项：

- `row_block`：行不阻挡该方向——`≤` 行要 `aᵢ·d ≤ 0`、`≥` 行要 `≥ 0`、`=` 行要 `= 0`，按 `1 + |aᵢ·d|`
  缩放；`aᵢ·d` 由内核行内积除以 `row_sign`（那个因子是 `±1`，除法精确）得到，且只累加**结构列**——
  slack / surplus / 人工列是内核变量而不是模型变量；
- `bound_block`：变量自己的界不阻挡——两端都有界的变量一步也走不了、只有一端的只能朝有空间的那一侧走
  （`dⱼ ≤ 0` 配下界、`dⱼ ≥ 0` 配上界），按 `1 + |dⱼ|` 缩放；"这里有没有界"用的是校验器那条判据
  （`model_has_lower` / `model_has_upper`），不是本文件自己的一条；
- `magnitude`：`max|dⱼ|` 要**超过**容差——零向量满足上面两条且什么都不证明；
- `improvement`：`c·d / (1 + Σ|cⱼdⱼ|)` 要**严格为负**。成本按校验器的最小化口径读（`sense_sign · c`，就是
  `model_cost` 里那个数），所以最大化模型上"改善方向"同样是负的；用模型自己的优化方向读会把一个正确的
  无界结论判成失败。

四项里任一项不过、或点越出行残差 / 变量界，就报 `NumericalFailure` 并按"没有结论的松弛"计。
**实测（三份报告重生成）**：求解报告与两份整数报告**每一行数字逐字未变**，三份里各只有头部记录的 commit
一行变了 —— 清单里没有一个实例在报告口径下报 `Unbounded`（唯一的 `other outcome` 是 `fast0507` 的
`iteration-limit`），所以这条自检在这三份口径上是**零代价的保真改动**；它被真正走过的地方是证书语料
（200 个随机模型，`Unbounded` 一档非空且每份证书都被校验器接受）与差分测试（内核报 `NumericalFailure`
而参照实现报 `Unbounded` 会直接失败，因此"多拒了正确的无界结论"会被抓出来）。白盒测试把内核的四个数与
校验器的 `measured` 逐位对齐，并单独量四种失败形态（撞行、零向量、两端有界的变量、走错方向）。

**限度**：不可行射线的构造仍是"Phase I 的最优对偶解"，不是从 Phase I 状态显式导出的构造。

## 8. 数值策略摘要

- 容差感知比较（`approx_*`），绝不用 `==` 比较浮点；
- 所有多项累加走补偿求和（目标值、行内积、组合系数）；
- 每个"是否为零 / 是否为正"的决策都带尺度：残差按行尺度、非负性按逐变量、乘子符号按
  `raw · max|aᵢⱼ| / max|cⱼ|`、割的小数部分按产生它的算术规模；
- **自检的尺度必须与它所替代的那条检查一致**——生产者量的必须逐字是被评判者量的那一条；
- 任何可能数值失败的例程都必须显式报告失败，不许悄悄返回一个看起来合理的答案。