c++ - COIN BCP框架中如何获取全局下界

Question

我目前正在使用 COIN OR BCP 框架研究分支和价格 (BAP) 算法。这是一个不错的框架，但有点旧，而且文档也不好。我希望这里有人能够回答我的问题。

我的 BAP 算法运行良好，但我注意到，我认为的全局下限实际上只是分支和价格树中特定节点的下限。有时我会得到轻微的负间隙 :)

因此，我深入研究了框架的内部部分，寻找如何检索全局有效的下限。奇怪的是，这似乎不是框架的功能!

我需要的是在我的树类(派生自 BCP_tm_user)中获取下界，以便报告解决方案差距。

Answer 1

我一直无法使用简洁明了的方法获得全局边界。然而，我能够使用间接方法获得这些值。我将在下面分享一些见解。

下界

看起来 BCP 树管理器跟踪标准多集数据结构中树节点的下限。令我困惑的是，为什么他们跟踪的不仅仅是最低的，因为他们在任何时候只需要最好的下限。可以访问 *BCP_tm_user* 中的多集数据结构，但是这些值不是全局下限。因此，我确实尝试通过覆盖 *BCP_tm_user* 中的每个可能的虚拟函数(尤其是 *display_node_information*)来获取根 LP 绑定(bind)。这个想法是在根节点被解决后立即读取最佳下限。不幸的是，这是一种不成功的方法，多重集中的最佳值(value)不是 LP 根边界。

上限

同样，我无法在 *BCP_tm_user* 中找到提取最佳上限(即可行解)的好方法。获取上限的明显方法和简单方法是覆盖 *display_feasible_solution* 并在此处提取值。但是，此方法有一个警告，如果您决定删除所有(或大部分)BCP 输出，则不再调用 *display_feasible_solution*!

我的解决方案

如果您覆盖 *select_branching_candidates*，这两个边界都可以在 *BCP_lp_user* 类中访问。在这里调用 *upper_bound()* 将为您提供最佳上限!并且生成的 LP 松弛解值(一旦不存在具有负降低成本的列)是根节点中的全局下界。如果 *this->current_level()==0* 成立，你知道它是根节点。如果您需要树管理器中的边界，我建议您将它们与您发送的解决方案一起传输(打包/解包)。