精读笔记
Problem Setting
这篇论文解决的不是传统意义上的 MIP 求解，也不是用 PDHG 替代 simplex / barrier 来获得完整的 LP relaxation 证书。它实际处理的是一个更窄但现实的问题：能否用 PDHG 快速产生的低精度 LP relaxation 解，驱动现代 MIP solver 的 root-stage primal heuristics，从而更快找到高质量 feasible incumbent。
真正困难点在于现代 MIP solver 对 LP relaxation 解的依赖是多语义的：同一个 LP 解既用于 lower bound，又用于 reduced cost fixing、cut separation、degenerate move、branching signal、heuristic neighborhood construction。PDHG 给出的解破坏了其中很多隐含契约：不够精确、非 basic、reoptimization 弱、不能可靠产生 bound。关键矛盾是：PDHG 的速度优势来自放宽精度和避免 basis，而 MIP solver 的强大性恰恰大量建立在高精度 basic solution 之上。
以前方法卡在“单一 PDHG-based heuristic”的层面：可以用低精度解做 rounding、fixing 或 propagation，但很难复用现代 solver 中几十个 heuristics 与 root cut loop 的系统协同。本文的任务不是发明一个更聪明的 rounding，而是测试低精度 relaxation signal 是否足以支撑整个 primal heuristic ecosystem。
Motivation
已有路线不够的原因是它低估了 MIP solver 的系统性。高质量 incumbent 往往不是某个 heuristic 单独找到的，而是 cuts 改变 relaxation、incumbent 触发 fixing、fixing 改变 sub-MIP、RINS / construction heuristics 再利用新 relaxation 的循环结果。单一 PDHG heuristic 即使在局部有效，也很难覆盖这种组合效应。
作者的核心观察很直接：root node 是高质量 primal solution 的主要来源，而 root cut loop 的主要成本又常常是反复解 LP relaxation。如果 PDHG 在某些大 LP relaxation 上显著快于默认 LP solver，那么把它放进 root loop 可能扩大 solution-quality/time 的 efficient frontier。
关键缺口是：社区知道 PDHG 低精度解快，也知道 MIP heuristics 需要 relaxation guidance，但不知道这种 guidance 到底需要多高精度、是否需要 basis、牺牲部分 solver 功能后还能不能保留足够 primal power。本文就是在测这个边界。
Core Idea
核心思想是把 PDHG 不是作为 MIP solver，也不是作为 standalone heuristic，而是作为现代 MIP solver 的低精度 relaxation-signal generator。它替换 root relaxation solve / reoptimization 的 LP engine，但目标只限于产生 primal heuristic 所需的搜索方向，而不是产生可信 lower bound 或完整 LP 证书。
理论直觉是：许多 primal heuristics 使用 LP relaxation 解时并不需要 1e-6 级别的逐约束可行性，也不需要 basis；它们更需要的是哪些变量接近整数、哪些变量在 incumbent 与 relaxation 中一致、哪些区域看起来有希望。也就是说，heuristic guidance 可能对 coarse geometry 敏感，而对 numerical certificate 不敏感。
与 prior 的本质区别在于，本文没有把 PDHG 解映射到一个手写启发式，而是把它注入已有 solver 的启发式网络。新增的信息不是一种新的 rounding rule，而是一种重新组织信息流的方式：让 PDHG 负责快速提供低精度全局 relaxation view，让 MIP solver 现有 heuristics 负责把这个 view 转化为 feasible incumbent。
Method
方法的核心不是实现细节，而是角色切分。
第一，作者明确把 PDHG-root solve 的输出限定为 heuristic guidance。由于 PDHG 解不能可靠提供 lower bound，相关 bound-based claims 被主动放弃。这一步解决的是 validity 问题：可行解可以事后严格检查，但错误 lower bound 会破坏求解正确性。
第二，保留那些只需要 relaxation vector 的机制，关闭那些需要 basis、精确最优性或高效 reoptimization 的机制。Gomory cuts 需要 basis，degenerate moves 需要明确的 optimal face，fix-and-dive 类 LP-heavy heuristics 会被 PDHG reoptimization 拖垮，多 root thread 与 PDHG 的资源占用冲突。这些不是小的 implementation tradeoff，而是 PDHG 与 simplex 解语义差异导致的结构性删减。
第三，sub-MIP heuristics 仍使用默认 LP solver。这个设计把 PDHG 的低精度风险限制在“选 neighborhood / 给 hint”的阶段，而把最终 feasibility 和 refinement 交给成熟求解器。没有这一步，低精度 PDHG 解很容易把启发式结果质量问题转化为 infeasible-solution 噪声。
第四，cut loop 仍被保留到一定程度，因为 root 后 solution quality 明显优于只做 preprocessing 或单 pass。也就是说，作者并不把 PDHG 当作一次性 relaxation oracle，而是试图保留 root loop 的交互式改进机制，只是接受其 degraded form。
Key Insight / Why It Works
最重要的 insight 是：LP relaxation 解在 MIP primal heuristics 中的“搜索导向价值”和它作为优化证书的“数值精度价值”可以部分解耦。传统 solver 默认把这两者绑定在 basic optimal solution 上；本文证明至少在 root heuristic 场景下，前者并不总是需要后者。
真正有效的原因大概率不是 PDHG 解更准确，而是它更快地产生了足够好的全局 continuous signal，使得 existing heuristics 能提前启动。RINS、sub-MIP heuristics、construction heuristics 等并不是在读取精确 dual certificate，而是在利用 relaxation/incumbent 之间的结构关系构造 neighborhood。只要 PDHG 解保留了变量层面的粗粒度结构，这些 heuristics 就还能工作。
核心贡献在于这个负面边界的定量化：PDHG 会破坏很多强机制，但破坏之后的 solver 仍然能找到不错 incumbent；低精度本身造成的 solution-quality 损失小于很多人直觉预期。这个判断比“PDHG 在某些模型上更快”更有迁移价值。
哪些部分可能只是辅助：rescaling、feature disabling、sub-MIP 回退默认 LP solver 都是必要工程，但不是核心算法 insight。哪些部分可能主要来自 scaling：成功案例很可能依赖 PDHG 在大 LP relaxation 上的硬件加速，尤其 GPU 场景。若 relaxation 不够大、cut loop reoptimization 次数多、或 simplex warm start 很强，PDHG 的优势会被迅速吃掉。
这不是 retrieval、data coverage 或 benchmark memorization 类型的工作；更接近 test-time compute reallocation 和 representation alignment：把一个低精度 continuous representation 对齐到 MIP solver 的 primal heuristic interface。所谓“泛化”也不是学习意义上的泛化，而是 solver architecture 对 relaxation noise 的鲁棒性。
Relation To Prior Work
最接近的路线是用 first-order / PDHG low-precision LP solution 来指导 MIP heuristics，尤其 fix-and-propagate、rounding、neighborhood search 一类方法。那些工作通常把 PDHG 作为一个单独 heuristic 的前端，本文则把 PDHG 嵌入完整 commercial MIP solver 的 root machinery。
与传统 simplex / barrier-based MIP root processing 的差异也很本质。传统路线依赖高精度 basic solution，尤其重视 basis、dual feasibility、reoptimization 和 cut/bound 的可靠性。本文主动放弃这些能力，把 LP solve 的目标从“为全局证明服务”改成“为 primal search 提供 hint”。
看似新的部分中，利用 relaxation 解指导 heuristics 并不新，sub-MIP heuristics、RINS、cut loop 协同也都不是新东西。实质创新在于系统层面的重组：检验一个现代 MIP solver 在失去 basis 与高精度证书后，还能保留多少 primal heuristic 能力；并把 PDHG 的低精度速度优势放在这个 degraded solver 中使用。
它属于 MIP solver hybridization 的技术谱系，而不是纯 first-order optimization 或新 heuristic 设计。更准确地说，这是把一阶 LP 方法作为 MIP root-stage primal accelerator 的系统实验。
Dataset / Evaluation
评估主要基于 MIPLIB 2017，并补充若干客户模型案例。MIPLIB 覆盖面较广，但它未必是 PDHG 最有优势的 regime，因为很多实例的 root LP 并没有大到足以体现 PDHG 相对 simplex / barrier 的优势。作者也承认平均表现不优，这反而让论文的 claim 更窄、更可信：不是全面替代默认 Gurobi，而是在特定大规模 relaxation-heavy 场景扩展 efficient frontier。
实验真正支持的 claim 是：低精度 PDHG 解可以在部分实例中足够好地驱动 primal heuristics，并且相对于禁用相同功能的 degraded default solver，solution quality 没有显著崩坏。这个证据比单纯展示几个 winning plots 更关键。
明显 limitation 是评估偏 anecdotal：最终性能优势主要通过若干 MIPLIB winning cases 和客户模型描述呈现，缺少对“什么结构的模型会赢”的系统分类。客户模型很有真实部署价值，但不可复现，增益来源不清。GPU PDHG vs CPU default 的比较也混入 hardware regime 差异；这不一定不公平，因为部署时硬件就是方法的一部分，但对算法归因不干净。
Limitation
第一，方法不能用于可靠证明。PDHG 解缺乏足够精度，不能安全提供 lower bound、reduced-cost fixing 证书或完整 branch-and-bound 所需的 relaxation validity。它本质上是 heuristic accelerator，不是 solver replacement。
第二，scalability 上限由 reoptimization 决定。PDHG 初始 solve 可能很快，但 root cut loop 需要多次加入 cuts 后 reoptimize；文中显示 PDHG warm start / reoptimization 相对 simplex 弱很多。这会把初始速度优势稀释掉，甚至反转。
第三，basis 缺失是结构性损失，不是调参能解决的问题。Gomory cuts、degenerate moves、concise solution representation、dual simplex reoptimization 都依赖 basic solution 语义。PDHG 若不经过 crossover，很难自然恢复这些能力；若加 crossover，又可能失去速度优势。
第四，增益归因不清。成功可能来自 PDHG 的低精度解足够好，也可能主要来自 GPU 对少数大 LP 的加速，或者来自默认 Gurobi 在这些实例上的 crossover / root processing 开销。文中未充分说明如何区分这些因素。
第五，方法把问题转移到实例选择上。它不是平均更强，而是需要识别哪些模型处于 PDHG sweet spot：LP relaxation 大、默认 LP solve 昂贵、heuristics 对粗粒度 signal 鲁棒、reoptimization 不至于吞噬收益。这个选择器本身是未来部署中的关键问题。
Takeaway
- 1. 最值得记住的是 LP relaxation solution 在 MIP 中的多重角色可以拆开：作为 proof certificate 需要高精度，但作为 primal heuristic guide 可能只需要粗粒度结构。
- 2. PDHG 在 MIP 中最自然的位置不是完整求解器，而是 root-stage primal accelerator。
- 它适合扩展 solution-quality/time frontier，不适合替代 branch-and-bound 的证书机制。
- 3. 现代 MIP solver 的强项是 heuristic ecosystem，而不是某个单点 heuristic。
一句话总结
这篇论文把 PDHG 从“低精度 LP 求解器”重新定位为现代 MIP root heuristics 的快速 relaxation-signal generator，贡献不在新启发式本身，而在证明低精度非基 LP 解仍可在特定大规模场景中驱动现有 MIP heuristic ecosystem。