# 算法说明

本文件写**实现里真正在跑的是什么**，以及每个策略背后那条实测数字。数字的出处是
[`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` 的状态。
- **定价**：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。
- **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` 不交回。

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

## 4. Presolve 与 postsolve

归约：空行 / 空列、冗余行、singleton 转界、隐式界收紧、固定变量消元（含目标偏移）。**每条归约先证明
再触发**；化简自己证出的 `Infeasible` / `Unbounded` 直接作为结论上报，不交给内核。

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

实测（求解报告口径）：`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 个节点证到最优。

## 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`），两万次采样一个可行点都没采到——
  空间大不等于样本密度够。
- **下潜的启动条件按价格定**：每个未定整数按 5 步收费（`gt2` 落地那次 82 步 / 18 个整数），
  `dive_steps`（默认 150）是它的上限；`2×分数变量` 那条是**下界**而不是价格。被上限截断的走法既不报点
  也不报证明，树却为它付了预算。启动门槛有两条：`depth ≥ 分数变量个数`，以及"当前解离这次运行的开界
  很远"（差 ≥ 1/5，只花 `dive_attempts`、不动下潜储备）。另外还有一份**下潜储备**：一个跑掉半个预算
  还没有任何整数点的运行既没有东西可剪枝、也没有东西可报告，于是给它留 `max_nodes / 16` 的预算份额
  用于额外走法，条件是"过半仍无当前解"且"储备能负担一整次走法"。
- **`nodes` 永不超过 `max_nodes`**：每个"花掉一次松弛"的地方（节点松弛、割轮重解、修复、泵投影、
  走法的一步）都先问预算。测试是遍历式的（每个模型 × 预算 1..8 断言 `nodes ≤ budget`）。
- **报告的界取在"开着的活"上**，不只是队列：一个松弛没有结论的节点被弹出后不会重新入队，但它的键是
  父节点的松弛目标值，对它整棵子树都有效；只遍历队列会把这份界连同子树一起丢掉，而 best-bound 弹出的
  正是键最小的那批，于是丢掉的方向固定是"界报得更好看、gap 报得更小"。现在取"队列的键 ∪ 被丢下节点的
  键"（节点本身仍不入队）。实测（小规模口径）：`blend2` 的界 `7.5784463643777125 → 7.399764899326714`，
  300 节点口径无一行变化。注意两类"没有结论"的分工：主循环的节点丢界所以要计进去，**下潜的一步不丢界**
  （出发节点有结论），它只体现在 `nodes − verified` 的差里。

## 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）。
两者互不蕴含——一个问算术是否自洽，一个问射线是否是证明。

**限度**：射线的构造仍是"Phase I 的最优对偶解"，不是从 Phase I 状态显式导出的构造；
**无界主张**的射线只自检了"点可行"，没有自检校验器审的另两项（行不阻挡该方向、目标严格改善）。

## 8. 数值策略摘要

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