问题标签 [branch-and-bound]

我正在使用我现在正在研究的分支定界算法来解决背包问题。在算法中，我想开始选择密度（值/重量）最高的项目。我创建了一个名为“密度”的列表并进行了必要的计算。我每次都需要从该列表中选择最大值。但是每次我尝试时，订单都会变得混乱。我需要更新变量“a”，因为每次我删除一个项目时，列表都会变小。但是不知道怎么更新。我需要帮助以正确的顺序选择项目。

重量、价值、密度是列表。capacity 和 room 是问题中给出的整数值。这是密度列表。

我想要的是，获取此列表中最大项目的索引。然后，从“容量”中减去它的“重量”，以找出还剩下多少“空间”。并将“价值”添加到“最高”，以便达到最高价值可以添加到背包中。在我为第一个项目执行此操作后，然后对其进行迭代，直到没有或只剩下很少的空间。

I want to find minimum vertices that connect certain vertices to each other. For example, assume list of edges is connections = [(2,0),(0,5),(2,3),(3,4),(0,4),(4,1),(5,1)] and the graph will be like below:

Then I want to know how to connect vertices 2, 4, 5 together with minimum number of vertices. Which in this case is vertex 0.

Therefore the output should be [0,2,4,5] which means 4 vertices needed. I tried to implement the algorithm with brute force since there would be more complicates cases but I am not sure how to find the best answer from all possible combinations.

我在过去的考试中遇到了这样一个问题：

令 X 是一个有序（递增）整数的数组。我们希望将这些整数分组到 k 个连续的子序列中，即 k 路分区。我们希望每组最小化一个质量函数，定义为每组元素与该组平均值之间差异的总和。根据定义，我们需要一种回溯算法，该算法可以修剪非最优解决方案分支并返回最小化总成本的 k 路分区。

但是，这就是我感到困惑的地方：

• 我为这个问题找到了这个漂亮的解决方案（嗯，几乎是一个完整的解决方案，我只需要完成成本函数）：用于解决分区问题的递归回溯算法。但我想，回溯算法不应该检查每个解决方案的可行性吗？根据我对 Antti 的回答的理解，所有可能性都被计算出来（从最后一个具有最大大小的分区开始，然后从右到左将元素杂耍到其他分区）。
• 我的另一个疑问与问题的规格有关，不是要求回溯解决方案修剪非最佳分支与要求分支和绑定解决方案相同吗？我可以使用回溯解决方案，当找到不正确的解决方案时回溯，但我认为修剪非最优性太多了。

也就是说，我对 Antti 的 ideia 的 pythonic 实现是这样的：

它确实有效（至少在某些边界条件下它确实有效），但我不确定为什么这是回溯，它对我来说确实像是详尽的搜索。我想就是这样。

非常感谢，社区。

我想使用分支定界解决以下类型的整数线性规划问题：
max(Ax)
st Cx<b
下面给出了一个示例，使用 Pyomo 解决。非常坦率的 -

如何使用 Pybnb 包而不是使用 Pyomo 解决相同的问题？
这个想法是解决线性问题，在上面的例子中，x[1]=2.22 和 x[2]=5.55 并以 x[2]=<5 或 >=6 等开始分支。但是通过实现pybnb 我不清楚。
谢谢您的帮助

我想知道为什么如果我们在 Cbc Coin 中运行多次完全相同的实例 - 或者，我们总是得到相同的解决方案，但不是在相同的解决时间。是因为在分支和切割过程中随机选择吗？是因为线程问题吗？

如果有人有想法请告诉我。

我尝试将以下约束添加到我的模型中。我的问题：函数 g() 期望 x 作为二进制 numpy 数组。所以结果 arr_a 取决于优化的每一步中 x 的当前值！之后，我希望这个数组乘以 x 的最大值小于 50。

如何动态添加此约束，以便在每次迭代时始终使用 x 的值正确计算 arr_a ，同时告诉模型保持约束 arr_a * x <= 50 ？目前我在向模型添加约束时遇到错误，因为 g() 期望 x 作为 numpy 数组来计算 arr_a、arr_b、arr_c （ g 在其计算中使用 np.where(x == 1) ）。

之后我添加了自然也依赖于 x 的目标函数。

编辑：

我的问题发生了一些变化，我设法让它毫无问题地工作。然而，我体验到约束从未真正得到满足！自定义函数是一个高度非线性函数，它需要 x==1 和 x == 0 的索引，并返回一个 numpy 数组。此外，无法使用 sat.solver 的预定义函数重新构建它。

即使我应用了更简单的功能，它也无法正常工作。

我还尝试了以下方法：

自定义函数的一些最小示例，我只是尝试说 n_closed 应小于 10。即使求解器不满足该条件：

我使用 Branch and Bound尝试了这里给出的背包问题的实现。

该解决方案似乎很好，但它并没有使最终选定的项目达到最佳值。有没有办法通过最低限度地更改以下代码来实现这一点？

假设我们有一个包含以下内容的输入文件

我期待如下结果

我编写了自己的实现，它提供了上述所需的输出，但是对于像这样的大问题，它花费的时间太长了

我通常不会就 SO 提出问题，所以如果这个问题似乎不适合 SO，请告诉我（当然，我们仍然会感谢您的帮助）。

我还是一名学生，目前正在学习算法课程。我们最近了解了分支定界范式，由于我没有完全理解它，所以我尝试在我们的课本中做一些练习。我遇到了一个特殊的 Set Cover 问题实例：

令 U 是一组元素，S = {S1, S2, ..., Sn} 是 U 的一组子集，其中所有集合 Si 的并集等于 U。概述分支定界算法以找到最小S 的子集 Q，因此对于 U 中的所有元素 u，Q 中至少有两个集合，其中包含 u。具体来说，详细说明如何将问题分解为子问题以及如何计算上限和下限。

我的第一个想法是按降序对 S 中的所有集合 Si 进行排序，根据它们包含的元素数量，这些元素还没有被当前选择的 S 的子集覆盖至少两次，所以我们当前的 Q 实例。考虑递归解决这个问题，我按排序顺序选择第一个集合 Si 并进行一次递归调用，在其中我取这个集合 Si 和一个我没有的地方（意味着从那些递归调用开始，不再考虑子集） . 如果我选择它，我将遍历这个所选子集 Si 中的每个元素并为其所有元素增加一个计数器（在递归调用之前），这样我最终会知道，当一个元素已经被两个或更多选择的元素覆盖时子集。由于我为每个递归调用对未选择的集合 Si 进行排序，理论上（至少在我看来）我会一直做出目前最好的选择。而且由于我基本上创建了递归调用的二叉树，因为我总是使用当前选择的最佳子集进行一次调用，而我最终会覆盖所有 2^n 的可能性，这意味着最终我会找到最佳的解决方案。

我现在的问题是我不知道或者更确切地说我将如何实现上限和下限的启发式算法，因此算法可以丢弃二叉树中的一些路径，这永远不会比当前最好的 Q 更好。将不胜感激我能得到的任何帮助。

我读过分支定界范式是近似的。有人可以解释为什么这种方法是近似的而不是精确的吗？它的近似值是什么意思？我为背包问题实现了它，并且总是在我运行这个算法时，它给了我准确的答案。

我想解决 Cplex 中的 MIP（使用 IloCplex for C++）仅使用分支和绑定功能（即没有所有加速解决的增强功能，如探测、在每个节点上运行启发式、添加切割等）。这个想法是能够测试我自己的削减的影响，而不会因为削减和 Cplex 对分支和边界的各种改进而模糊结果。

我已经禁用了许多方法，但根松弛仍然比我在运行 MIP 时得到的目标值要好，所有完整性约束都放松了，这意味着 Cplex 仍在以任何方式改进分支和边界。

我设置了以下参数：

我通过以下方式停用所有削减：

我错过了什么？