问题标签 [branch-and-bound]

我有一些学生的个人资料，其中包含物理、化学和数学等几个学科的价值观。我需要根据个人在科目上的分数找到一个优势学生的名单。例如：

如果一个学生满足以下两个条件，他将优于另一个学生。1. student_1 >= student_2 对于所有参数 2. student_1 > student_2 对于至少一个参数

我试过使用嵌套循环。可能是蛮力算法。我添加了另一个名为“passed”的参数来跟踪它是否优于其他参数。这是代码：

我发现预期的结果是学生 A & D 的标志“通过”== false。现在我需要通过使用不同的算法（如分治法、最近邻法、分支定界法等）或任何其他有效方式来获得相同的结果。我需要比较大型数据集的时间和空间复杂度算法。

和标题说的差不多。

这是在分支定界问题中完成的，特别是旅行推销员。

我了解矩阵缩减的工作原理，但我真的不明白你为什么需要这样做。

谢谢。

我有一个我想解决的问题，但我不知道如何对其建模在问这里之前，我进行了研究并找到了一些有用的东西，但我无法理解它。我在下面遇到的问题示例

所以我有很多项目，比如说 40 个，每个项目都有 2 或 3 个功能，每个功能只有在有 3、4、5、...时才有用，具体取决于功能。

目标是通过 10 个不同的项目获得最大数量的不同有用功能

示例（如果 3 个或更多不同的项目包括 a，则特征 a 很有用，如果 5 个或更多不同的项目包括 b、c 8 个或更多项目等，则特征 b 很有用）

一个示例组合

所以 a 和 b 有用的特性（c 没有用，因为有 5 个我们需要 8 个才能使它有用）

我想我想建模一个混合整数线性程序并用分支定界求解器解决它目标是每个项目和每个特征的特征权重的数量（？）我考虑将其建模为背包问题，但后来我想不出出如何应用这个像容量是 10 但价值和重量？对有用的功能有最低要求，我需要一些指导或通用算法来解决这个问题，如果我有什么要开始的，我可以进一步调查

我正在通过 CPLEX 12.10 的 C API 使用通用回调框架设置分支和切割算法。

在每个节点，分离问题基于当前节点 LP 并检测本地有效切割，如果违反，则为当前节点的每个子节点添加。

据我了解，当前节点 LP 的信息在通用回调中并不容易获得。但是，我想使用为父节点生成的切割来在子节点中生成更好的切割。

是否有必要记录在所有节点上生成了哪些剪辑，或者是否可以使用 CPLEX 功能以某种方式传递此信息？如果唯一的可能性是跟踪所有生成的剪辑，那么如果 CPLEX 从不同线程和不同节点中调用回调，如何使这种簿记成为线程安全的？

我按照示例在 MIP 的 control(branch) 回调中使用make_branch()进行分支。但我注意到，在变量选择策略的不同设置下，求解过程出人意料地不同。自从我用自己的决定替换了所有 CPLEX 的决定后，这怎么可能？

有人可以向我解释一下，变量分支和约束分支（Ryan 和 Foster）有什么区别？

我正在阅读这篇文章：

DM Ryan (J. Op1 Res. Soc. Vol. 4) 的“Aircrew Rostering 中大规模广义集分区问题的解决方案”

在我看来，这与作为集合分区问题的工作人员调度或护士排班问题完全相同。

两种分支方法都在 1 个变量上分支，有什么区别？

我正在尝试使用 SCIP 在 Python 中实现 Branch-and-Price。

我了解 FIFO B&B、LIFO B&B 和 LCBB 之间的区别，但我只是想不出你为什么要进行 FIFO，因为它会导致广度优先搜索而不是深度优先搜索。毕竟，如果您可以快速找到更好的解决方案并更新您的 BSSF，您还可以进行更多的修剪——因此 FIFO 应该比 LCBB 生成更多的状态，并且比 LCBB 更慢。而且由于分支定界的目的是找到最佳解决方案，我不明白为什么你会想要额外的状态。

我的想法正确吗？LCBB 不是总是比 FIFO 分支定界好吗？

我在 python 中实现了一个分支和价格树。

我想在 5 小时后停止该过程，并返回到目前为止找到的最佳整数解决方案与最佳解决方案之间的差距（百分比）。

如何给 SCIP 一个值并要求它返回输入和最佳值之间的差距？

编辑：我在 beta 站点 Operation Research 上询问了这个问题，并建议将其发布在堆栈溢出上：

https://or.stackexchange.com/questions/4015/branch-and-price-return-gap-using-scip

编辑编辑：我找到了一个函数 SCIPgetGap ，它返回：

但我对双重差距感兴趣：

如何获得 SCIP 中的双重差距？

我了解分支定界算法如何解决旅行商问题，但我无法理解该算法如何比蛮力更快。在我看来，你最终会走过所有的道路。有人可以举一个例子，说明 B&B 算法比暴力破解所有路径更快吗？

空间分支定界的时间复杂度是多少？我对复杂性如何取决于变量的数量及其维度感兴趣。

谢谢！