精读笔记
Problem Setting
这篇论文处理的是 PCKP 自然 ILP 的 LP relaxation，而不是 NP-hard 的整数问题本身。具体目标是：当容量 c 变化时，如何完整刻画 LP 最优解、Lagrangian dual multiplier、以及对应 dual 解的组合结构。
真正困难点在于 precedence constraints 破坏了 classical knapsack 中“单 item 边际效率可排序”的结构。一个 item 能否被选、以什么边际价值进入解，取决于它必须携带的 predecessors / closure，因此 item ratio p_i/w_i 本身不再是可排序对象。以前 parametric MCP / max-flow 方法可以算出 value function u(λ) 的断点，但它更像黑箱地枚举 closure；它没有解释这些断点之间的差分块是否构成类似 knapsack 的有效排序单位。
关键矛盾是：LP relaxation 允许 fractionality，但 precedence 是离散 closure 结构；如果不能找到合适的“分数化单位”，LP 解看起来仍像网络流/闭包问题，而不是 knapsack 问题。本文的目标就是找出这个单位。
Motivation
已有路线的不足不是不能求解，而是缺少结构解释。Parametric maximum closure 已经给出一种成熟方案：对不同 λ 求解 closure，得到分段线性凸函数 u(λ)，再由 Lagrangian relaxation 读出 LP 上界。但这个视角把信息留在 value function 和 cut sequence 中，没有形成一个像 KP 中 ratio-sorted items 那样直接可用的对象。
作者的核心观察是：相邻 parametric closure optimal solutions 的差分，可能正是 PCKP 中替代 item 的基本单位。换言之，precedence 不是让 ratio ordering 消失，而是把排序对象从 item 提升为某些 closure-compatible blocks。
关键缺口在于：这些 blocks 是否唯一、是否按 ratio 递减、是否真的决定 LP primal/dual 解、是否能在有结构图类上比一般 parametric flow 更快算出。论文围绕这四个问题展开。
Core Idea
核心思想是把 PCKP-LP 重新写成“macroitem 版本的 fractional knapsack”。macroitem 是 item set，但不是任意聚类；它来自 parametric MCP 断点处极小/极大最优 closure 的差分。这个构造把 precedence 依赖全部封装在 macroitem 内部，使 macroitem 之间满足可行前缀性质：按序取前若干 macroitems 一定是 precedence-feasible closure。
理论直觉很清楚：在 classical KP 中，Lagrangian multiplier λ 扫描 item ratio；在 PCKP 中，λ 扫描的是 closure 的最优 affine envelope。每个 breakpoint 是两个 closure 解交换最优性的地方，其斜率差对应新增集合的 weight，截距差对应新增集合的 profit，因此 breakpoint 自然等于该新增集合的 ratio。论文的关键贡献是证明这些新增集合不是偶然差分，而是唯一 optimal macroitem sequence。
和 prior 的本质区别在于，它不只是用 parametric MCP 求 LP，而是把 parametric MCP 的输出解释为一个新的 ordered partition。这个 partition 是比 cut sequence 更接近 knapsack 的 representation，也更适合迁移到算法设计、dual interpretation 和 ratio optimization。
Method
1. Lattice / extremal closure：作者利用 closure feasible set 在 ∧/∨ 下封闭的 lattice 性质，说明 breakpoint 处的 optimal closures 也形成 lattice，因此可以定义极小和极大 optimal solution。这一步解决的是“差分块是否定义良好”的问题；没有 extremal solutions，macroitem sequence 会依赖 tie-breaking。
2. Breakpoint-as-ratio：相邻 extremal closures 的差分 x_r - x_{r-1} 被证明是一个 precedence-constrained fractional ratio problem 的最大支持最优解，其 ratio 正好是 λ_r。这一步解决的是“macroitem 为什么应该按 profit/weight ratio 排序”的问题；它把 parametric value-function 的几何断点转成组合效率。
3. Optimal macroitem sequence：将 M_r \ M_{r-1} 组成 ordered partition，并用 lexicographic maximality 处理同 ratio / 支持大小问题。核心变化是把 LP 解空间压缩成一个唯一序列：给定容量，只需找 split macroitem。
4. Primal-dual construction：primal 解对 split 前 macroitems 取 1，对 split macroitem 统一取同一 fraction，对之后取 0；dual 中 λ 等于 split macroitem ratio，μ 类似 KP 的 reduced cost，而 α 是 macroitem 内部满足 balance 的非负 flow。这一步说明 macroitem 内部的 precedence 张力被 flow 消化，macroitem 之间不需要额外耦合。
5. Forest algorithms：对 directed forests，作者利用 preceding set / succeeding set 的可分解性，反复比较 final nodes 与 minimal preceding sets 的 ratio；若 arc-based set 最优则 contract arc，若 final nodes 最优则输出 macroitem。它解决的是特殊图类上如何避免通用 parametric pseudoflow 的问题；但这部分是结构特化算法，不是一般 DAG 的突破。
Key Insight / Why It Works
最核心 insight 是：PCKP-LP 的 fractionality 不是发生在任意 item 上，而是发生在一个由 parametric closure 自动诱导出的 block 上。换句话说，precedence constraints 没有摧毁 fractional knapsack 结构，只是把“item”替换成了“closure-difference macroitem”。这是本文最值得记住的理论贡献。
方法成立的原因有三层。第一，closure feasible set 的 lattice 结构保证了 breakpoint 处可以谈极小/极大 optimal closure，从而差分块稳定。第二，u(λ) 是 feasible closures 的 upper envelope，相邻 affine pieces 的交点必然等于新增块的平均 ratio；这给了 macroitem ratio 的几何来源。第三，optimal sequence 的前缀 closure-feasible 性保证按 macroitem 顺序装入不会违反 precedence，因此 LP 解退化为 fractional knapsack。
dual flow characterization 是重要但偏解释性的贡献。它说明每个 macroitem 内部必须能够把 item-level profit deviation p_i - w_i(P_r/W_r) 通过 precedence arcs 重新平衡；这本质上是一个 certificate，证明 macroitem 的 aggregate ratio 可以合法分摊到 item 级 dual constraints。它强化了结构闭合性，但对 primal ordering 的核心发现不是必要前提。
森林算法的有效性主要来自强 inductive bias：在 forest 中，任何 closed subset 可分解为 minimal preceding sets 加 final items，因此最大 ratio block 可以通过局部 contraction/removal 找到。这里的性能增益不是 scaling 魔法，也不是更强 general solver，而是利用了图拓扑的低树宽/无共享依赖结构。对 general DAG，这个优势大概率会消失。
实验中的 HFMA 快于 bounded-precision pseudoflow，不能过度解读。它更像 specialized combinatorial algorithm 对 general parametric flow 的胜利，而且 pseudoflow baseline 还受 precision/overflow 限制。真正的贡献不在 benchmark，而在把 parametric closure 的隐含结构显式化。
Relation To Prior Work
最接近的技术谱系是三条：classical fractional knapsack 的 ratio ordering、maximum closure / open-pit mining 中的 parametric closure 方法、以及 PCKP polyhedral / separation 文献。本文不是在 polyhedral strengthening 线上推进，也不是给整数 PCKP 新 cut；它是在 LP relaxation 的 parametric structure 上做重新解释。
和 Lerchs-Grossmann / Chicoisne 等 parametric MCP 路线相比，本文新增的信息是 macroitem sequence 的组合语义。已有方法知道 breakpoints 和 optimal closures，但没有把相邻 closure 差分解释为唯一的“可排序 macroitems”，也没有把 LP primal/dual 解写成 knapsack analogue。
和 classical KP 相比，本文的创新是证明 ratio greedy 结构在 precedence 下仍存在，但排序对象必须内生生成，而不是原始 items。这个提升不是简单 regrouping；macroitem 由 ratio optimization 和 closure lattice 决定，带有全局依赖。
和 general parametric max-flow/pseudoflow 相比，森林算法是实质性的结构特化：它用 contraction/removal 替代全局 flow recomputation。但它不是通用算法突破；在 general DAG 上仍回到 parametric flow 框架。
Dataset / Evaluation
实验覆盖了 synthetic forest instances：不同 size、density、orientation pattern、profit-weight correlation，并比较了 heap-based forest algorithm、非 heap variant、in/out-tree specialized variants 和 bounded-precision parametric pseudoflow。任务覆盖对“森林算法在森林上快”是足够的，但对真实 PCKP/open-pit/network design 场景的代表性有限。
evaluation 支持的 claim 是有限且明确的：在生成的 forest instances 上，利用 forest 结构的算法有更好 runtime，in-tree/out-tree specialization 符合 O(n log n) 行为。它没有验证 general DAG 上 macroitem computation 的 practical advantage，也没有说明该 LP structure 对整数 PCKP 求解是否带来实际收益。
对 BPPF 的比较有参考价值，但不是决定性证据。baseline 是 bounded-precision implementation，且作者自己指出 ratio 接近时会 merge macroitems、提高精度会导致 overflow。这意味着部分差距来自数值实现限制，而非纯算法复杂度优势。文中未充分说明这些 synthetic distributions 与实际应用图结构之间的对应关系。
Limitation
最大限制是贡献边界在 LP relaxation。自然 LP 的结构再漂亮，也不等于整数 PCKP 变容易；integrality gap、rounding、branch-and-bound impact 都没有被实质解决。若目标是 exact PCKP，本工作目前更像一个强 structural primitive，而不是完整算法。
第二，efficient computation 的上限主要卡在图类。森林中的 decomposition proposition 是算法成立的核心；一旦进入一般 DAG，minimal preceding sets 会重叠，局部 contraction 的正确性不再直接成立，可能仍需 parametric max-flow。也就是说，方法把一般复杂性转移到了“如何计算 macroitem sequence”。
第三，实验泛化有限。benchmark 是合成森林，且与通用 pseudoflow 的比较受到 bounded precision 影响。增益来源很大一部分是 topology specialization 和 implementation choices；不能推出在真实大规模 DAG 或 mining instances 上同样成立。
第四，optimal sequence 的唯一性依赖 lexicographic maximality 和 ratio tie handling。理论上处理干净，但实践中如果 ratio 极接近，会出现数值不稳定；这恰好也是 pseudoflow baseline 暴露的问题。作者的 integer cross-multiplication 避免了自身算法的该问题，但 general flow approach 中仍会存在。
第五，dual flow characterization 虽然优雅，但文中未充分说明它能否导出新的 cuts、bounds 或 decomposition。当前更像 certificate / interpretation，而不是已经转化为求解整数问题的工具。
Takeaway
- 1. 最值得迁移的 insight：当 precedence / closure 破坏 item-level ratio ordering 时，不一定要放弃 greedy LP structure；可以寻找由 parametric dual variable 扫描出的 endogenous blocks。
- 2. 这篇真正推动的是 representation：把 parametric closure 的 breakpoint sequence 解释为 macroitem partition，使 PCKP-LP 重新获得 fractional knapsack 的可读结构。
- 3. 对算法设计的启发是：如果图类允许 closed sets 分解为少数局部 primitive，那么 macroitems 可以通过 contraction/removal 计算，而不必调用通用 parametric flow。
- 4. 未来真正值得做的是把 macroitem structure 接到整数 PCKP：例如作为 branching unit、aggregation unit、cut separation guide，或用于解释/控制 LP gap。
一句话总结
这篇论文把 PCKP 自然 LP relaxation 从 parametric maximum-closure 的黑箱断点序列，重解释为一个由 endogenous macroitems 构成的 fractional-knapsack 结构，是一次结构表示层面的推进，而不是通用整数求解算法的突破。