一种基于容忍度的定价证书，用于稳定化的Dantzig-Wolfe分支定价方法在单位承诺情形下的应用

《Algorithms》：A Tolerance-Aware Pricing Certificate for Stabilized Dantzig–Wolfe Branch-and-Price in Unit Commitment

　　

)

摘要

稳定化的提案定价可以减少具体的子问题工作量，但它本身无法确保分支定价（branch-and-price）节点的终止。为此，针对确定性单元承诺（deterministic unit commitment）提出了一种基于条件调整的节点定价界限。在非稳定的受限主节点对偶（unstable restricted-master dual）情况下，CSDW-S采用了第二阶段的级联方法，该方法包括一个可分离的时间段的运营包界限（Tier E）、一个保持时间顺序的渐进式放松的动态规划界限（Tier D），以及精确的混合整数规划定价方案作为备用方案。CSDW-X会为每一个第二阶段的单元精确地定价。该机制在一个预先指定的、包含79个任务的研究中进行了评估，每个任务的科学截止时间为600秒。在主要的24对、24小时时间范围内，CSDW-S和CSDW-X分别在15种和24种条件下返回了被接受的根节点结果。在15组共同被接受的结果对中，两者之间的最大绝对界限差异为。在所有15组结果对中，CSDW-S均减少了精确的真对偶单元解决方案的数量（中位数对差异为），尽管在14组结果对中CSDW-S的运行速度较慢（中位数对差异为秒）。之前提出的10个单元的评估结果不符合主要 acceptance criteria（接受标准），因此将其作为历史数据单独保存，CSDW-S的完成标志为0/10，CSDW-X的完成标志为9/10，并未与新研究的结果合并。该机制的有效性、容错性、时间范围压强以及两个小型全树对比结果都支持了这一机制的合理性。当某个节点完成时，通过选择性的级联流程可以减少精确定价的工作量。