1

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

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

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

我需要的是在我的树类（从 BCP_tm_user 派生）中获取下限，以便报告解决方案差距。

4

2 回答 2

0

我一直无法使用一种漂亮而干净的方法来获得全局边界。但是，我能够使用间接方法掌握这些值。我将在下面分享一些见解。

下限

似乎 BCP 树管理器跟踪 std 多集数据结构中树节点的下限。这让我感到困惑，为什么他们要跟踪的不仅仅是最低的，因为他们只需要任何时候最好的下限。可以访问 *BCP_tm_user* 中的多集数据结构，但是这些值不是全局下限。因此，我确实尝试通过覆盖 *BCP_tm_user* 中的每个可能的虚函数（尤其是 *display_node_information*）来获得根 LP 绑定。这个想法是在解决根节点后立即读取最佳下限。不幸的是，这是一种不成功的方法，multiset 中的最佳值不是 LP root bound。

上限

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

我的解决方案

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

于 2013-11-04T09:42:06.237 回答
0

您可以遍历树，并找到活动节点中的最低下限：

BCP_tree &search_tree = getTmProblemPointer().search_tree;
double global_lower_bound = BCP_DBL_MAX;
for (auto itt = search_tree.begin(); itt != search_tree.end(); itt++) {
    BCP_tm_node *tm_node = *itt;
    if (tm_node == NULL || tm_node->status == BCP_ProcessedNode) continue;
    double trueLB = tm_node->getTrueLB();
    global_lower_bound = min(global_lower_bound, trueLB);
}
于 2015-04-01T23:30:30.743 回答