问题标签 [branch-and-bound]

我的程序有问题，因为我得到了错误的输出。我已经从我在网上找到的另一个程序从 C++ 转换并且它工作正常。

输入：

4

6

2 10

3 12

4 5

3 15

输出应该是：

22

获得的输出：

12

我正在尝试对edit distance算法实施分支定界方法。我在互联网上找不到任何提示。谁能帮我进入算法的轨道。

我想知道如何做 BOUND 因为我生成了所有可能的解决方案矩阵 tsp 但没有生成边界。问题是旅行推销员。是否有可能做到这一点？

这个问题的想法是探索无向图的所有节点及其所有邻居。

每个联合都有一个相关的权重。这个想法是用最小的重量进行最大可能的配对。

考虑到一旦结对，就不能再加入了。为了实现这个算法，使用分支定界，我必须找到一个上限和一个下限。

我的想法是有一个解决方案列表和一个部分列表，其中我介绍了所有可能的邻居对。

然后比较成本是否更低，添加到解决方案列表中。

问题是我不知道用来实现这些界限的启发式方法

伪代码有什么想法吗？

真挚地

编辑

对不起，我留下了这么开放的问题。让我用图像来解释问题。

在图像中，观察到三个联合。(1,3), (2,5), (6,4)。

这些是最佳工会。

对于最优解，必须满足一对(x,y)的并集的权重最小且“x”和“y”永远不会再匹配

我认为的一个条件是：返回列表解决方案，如果满足以下条件，则所有匹配项：

我使用贪心算法做到了这一点。

在所有节点上迭代并加入尚未访问且权重最小的邻居。

但是这样，我不能保证最优性。

好吧，我有这张图：

我必须制作一个基于 Branch and Bound 并使用回溯的代码，它必须显示匹配图形节点的最佳方式。所以在这个例子中，最优解必须是>> [(1,4),(2,3)]。但是我的算法显示了这个可能的解决方案，这不是最佳的>> [(1,2),(3,4)]。我认为问题可能出在“撤消”行，但我不确定......如果有人可以帮助我解决这个问题，我将非常感激！

这是我的代码：

这可能是一个有点愚蠢的问题，但解决 TSP 和 ATSP 的确切区别是什么。

我一直认为在 ATSP 中你需要计算返回的路径（因为输入矩阵是不对称的）。

所以 ATSP 的路径是 TSP 的两倍。我对么？

我明白这是一个非常简单的问题，但我的脑海里已经有了疑问。谢谢你。

我正在尝试使用 Koert Kuipers 的 matlab 代码进行分支和绑定：BNB20。我不断得到

这是主代码下方带有 mofitness 功能的主脚本：

功能适应性：

希望有人可以帮助我，谢谢。

我必须为最好的第一、分支和绑定背包问题实现一个算法。但是，我的算法没有给我正确的答案。我的 KWF2 函数找出上限有效，但调用 knapsack(0,0,0,n) 给了我一个非常离谱的答案 5，而它应该是 90。

我有一个有向无环图，弧是实体，每个弧关联的权重是 PlanningVariables。我用：

为我的变量赋值。另外，我遇​​到了这个问题： OptaPlanner 中的详尽搜索不适用于非常简单的示例，现在可以通过设置变量 from inttoInteger并检查null分数计算中的值来解决。

现在的问题是求解器在分配值时似乎没有回溯。我使用打印来检查归因于每个弧的值。在求解过程的开始，我可以看到值被设置为不同的弧。但是经过一段时间的归因后，求解器坚持将值分配给同一弧。检查打印我看到属性从 1 到 1000，然后重新开始。既然域中的所有值都经过一次测试，为什么求解器不回溯而是再次分配相同的值？

我测试了所有<nodeExplorationType>选项并创建了一个类来使用<entitySorterManner>具有相同结果的类。

提前致谢。

当我们使用 cplex 解决最大化 mip 问题时，cplex 启发式会影响目标值的上限吗？

据我了解，cplex 启发式可以提高最佳值的下限，但不能提高上限。但在我的测试中，如果我关闭 cplex 启发式，它会给出非常差的上限。上限（启发式开/关）的差异非常大，不容忽视。帮我 ：-（